Backtracking and game solvers

Backtracking is the design technique of algorithms
which is used in solving game problems or you
can say searching the solutions for the problem
in games.
how is backtracking works??

the tree of backtracking is shown as follows:-

well this algorithm is DFS and uses recursion for
solving the problem

1) MaZe SoLver

According to algorithm of backtracking the
terminating condition of maze is [row,col]
there are 3 possible moves at each direction
and we have to select one of the three and
again iterate the 3 till we reached at the goal
state if the path is not a valid move then
backtrack it and select the remaining 2 path
which has left behind in this way we can
explore the whole path if no path is ever
reached then we return 0;
the code is given in C and the maze is
taken as 0's(path) and 1's (wall)and 101 as destination.

you can test this code @ mazesolver

2) KnIgHT TouR

Applying the above algorithm the terminating
condition is that the knight visited all the
squares of the chess board =64 .
There are total eight moves of knight
For each move select one of the valid moves
out of 8 then place and select the move and
again iterate the moves if there is no valid
move then backtrack it .and choose the
remaining 7 moves do till the goal state
is reached if no path is avilaible then
return 0;

you can test this code @ knighttour

3) EigHT PuZZle
Applying the algorithm:
Terminating condition: place 8 queens such
that no queen intersect eachother.
for each row in board select the valid
column position and place it .
if no valid move is there then backtrack it .
And select other columns in the row
do it till the goal state is reached

you can test this code @ 8puzzle

4)PeNTomINo

Terminating Condition:
if all pieces are fit completly in to the board
for each 12 pieces 63 orientations we have
to select one and place and then iterate
againif any piece not fit at its location
then Backtrack it and try the remaining
pieces and do it till the goal state is reached
or all the pieces fit into 6 * 10 board

you can test this code @ pentomino

5)pEg sOlitAiRE

Applying algorithm Terminating Condition:
only one peg is left in the board.
there are four possible jumps and their is the condition for the jump as shown in figure

* * o  →  ¤ o * Jump to right

o * *  →  * o ¤  Jump to left 

*     ¤
*  →  o  Jump down
o     *

o     *
*  →  o  Jump up
*     ¤

In the diagrams
1) * indicates a peg in a hole.
2) * emboldened indicates the peg to be moved.
3)o indicates an empty hole.
4) ¤ is the hole the current peg moved from.
5) * is the final position of that peg
6) o is the hole of the peg that was jumped
and removed.

For each jumping for the pegs select the valid
one and place on the board then again iterate
the board till no valid moves are left and then
backtrack and unplace the move increment
the next move and again call iteratively
till the goal state is reached else
return 0;

you can test this code @ pegsolitare

6) BoGGle (a word game)

this game not only requires algorithm but also
requires knowledge of words which it can
obtain from the dictonary file dictionary.txt
we have to find the maximum meaningful
sentences from given matrix of words

Termination condition :
till the dictonary finds searching and every
word match.
Applying algorithm :take any word from dictionary
check it from matrix any letter .a letter corresponds
to its 8 edges check it on 8 edges recursively
if no valid match is found backtrack on other
edges in till the word is not found in the matrix.
In this way you can traverse whole dictionary
and find maximum counting words

you can test this code @ boggle

no promises simply enjoy and if you find mistakes do comment ;)

PRIMES

There are many techniques through which we detect the prime numbers

1. dividing the number by each numbers upto
2. sieve of erathoses (linear method).
3. fermath detection (probabilistic method).
4. miller rabin prime detection (probabilistic method).

so today we discuss these probabilistic method let's
first discuss fermat's prime test fermats primilarity
for the fermats little theorm there must be a and p
and such that they are coprimes then

so we to solve that

then the number is prime.
for solving this equation you get to know modular
exponential which is shown by example:-

now this technique is called modular exponential
in the fermats primilarity if you get the 1 after solving .
Then the number is prime else not
you can check and test the code here fermaths primilarity test
testing can be done at here see the
1 )upload with new input option click on it
2)inset the prime number enter submit

i have also implemented big integer multiplication similar
to modular exponential to multiply big numbers now you
think that we met the god of prime tester but it is not
there are numbers which act like prime but are not prime called carmichael number for example
test of 4903921 revels it is prime but it is not
here comes the concept of miller rabin
it says of a prime number would be two trivial
square roots 1 and -1(mod n).-1(mod n) = n-1(mod n)
more elegently described pseudocode described at
pseudocode of miller rabin test my job of implementation
here test the code with more inputs miller rabin test

i want to come up with more interesting algorithms till then NJOY

Euclid algorithm and its applications

we have used this algorithm in our elementary classes for finding out
the remainder no big deal !!! ; but let take this equation
1353x + 23y = 1 can you find out values of x and y without hit and trial method
yes we can how i am googling and find out numerical recipes and yeahh it
uses the gcd algorithm to find out the values of  x and   y it is called Extended_Euclidean_algorithm  today we will discuss its types and its three methods to solve this equation.As discussed in the wikipedia if we follow
Bézout's identity which says if the equation is written in the ax + by = 1
where a and b are the Bézout's coefficiants then we can write this equation
by maintaining  a and  b as it is and changing values of  x and  y
which is equal to  1;question arises why 1 here comes the existence of gcd
can we write this equation as

so i can write as

now we have to calculate the values of  x and  y without changing the values
of  a  and  b; but there is the condition i.e. you can only calculate correct
values of  x  and  y whose gcd is 1 as seen in the equation question arises
how do we calculate the values of  x and y  without changing the values
of  a  and  b this can be done with the help of three methods
1)substitution
2)recursion
3)table method
as given in the wikipedia the codes of three are availaible here and
also you can test any values

1)substitution Iterative_method(substitution)
(please test values only for those gcd of them is 1)

you can test by giving input parameters a and b at extended euclid algorithm by substitution

2) recursion recursive
(please test values only for those gcd of them is 1)

you can test by giving input parameters a and b at extended euclid algorithm by recursion
3) table method table
(please test values only for those gcd of them is 1) you can test by giving input parameters a and b at extended euclid algorithm by table

another application of the euclid algorithm is to find the
modular inversethe best explanation i would give is

we have given a and m and we have to find the value of x such that
their multiplication (a*x) bring 1 mod m
solving:if somehow we can write this in the form
extended euclid equation then we can solve it yes we can equation

where q is the qutionent of a and m as we can write

as we cannot write a and m as negative therefore x and q be negative

in the form of  ax + by  as in extended euclid algorithm
solve it for q and x and then modulus by m therefore
we are left with

here is the code

you can test by giving input parameters a and m at multiplicative inverse

i come with something more interesting in number theory till then enjoy

Fibonacci (log n)

you have done the fibonacci series with 
1) recursion with O(n-1)+O(n);
2) linear dynamic programming c=a+b; a=b; b=c; in looping to n with O(n);			            
3) with matrix exponential O(log n);
so we are intesesting how the order log n is justified with matrix exponential;
here are the observations comeoncodeon-fr0ddy related to it i concluded that
if we represent the fibonacci as the matrix than 

here first element of fibonacci series is 1 the matrix fib[0][0]
if we have to find out fibonacci series at n then fib[]n
n can be odd or even.
if it is even n= 2 * k  "k" be any integer then the matrix next element 
is found by repeated squaring i.e. 
else multiply by its previous matrix i.e. fib[]n=fib[] * fib[]n-1
and loop till goal state is achieved
here is the code given explore it

you can also test its speed by testing cases at fibonacci(log n) code
see how fast it is running from your recursive fibonacci.

Gaussian Elimination and its applications

solving set of equations
we can solve the set of equations by applying gaussian elimination
for details of gaussian elimination algorithm see the following link gaussian elimination
gaussian elimination is the technique for solving
equations for more than two variables for details see Wikipedia here are the linear equation are as follows

x + 2y - z - 2e = -6
x + 3y - z - 2e= -4
2x + y + z + e= 11
3x + y + 2z + e=15

the echelon form is given by floating point numbers

the code first asks input row and colums including the augmented matrix
then ouputs each of the particular answers

the output i.e. 
1st variable is 
x = 1.000000 
2nd variable is
y = 2.000000 
3rd variable is
z = 3.000000 
4th variable is
e = 4.000000 

here is the link you will try more test cases with my code gaussian elimination code in c
there at particular point in this site written upload with new input click on it and enter the
1) row including the echelon form of the matrix
2) column including the echelon form of the matrix
3) matrix including echelon form
and click on submit and see results
i will come up with more applications of the gaussian eliminations soon...

Hello World