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 ;)