Problem-1
Using Backtracking algorithm
N-Queens problem
The problem is to place n queens on an n × n chessboard so that no two queens attack each other
by being in the same row or in the same column or on the same diagonal.
Solution:
So let us consider the four-queen problem and solve it by the backtracking technique. Since each
of the four queens has to be placed in its own row, all we need to do is to assign a column for
each queen on the board presented in figure.
We start with the empty board and then place queen 1 in the first possible position of its row,
which is in column 1 of row 1. Then we place queen 2, after trying unsuccessfully columns 1 and
2, in the first acceptable position for it, which is square (2, 3), the square in row 2 and column 3.
This proves to be a dead end because there is no acceptable position for queen 3. So, the algorithm
backtracks and puts queen 2 in the next possible position at (2, 4). Then queen 3 is placed at (3,
2), which proves to be another dead end. The algorithm then backtracks all the way to queen 1 and
moves it to (1, 2). Queen 2 then goes to (2, 4), queen 3 to (3, 1), and queen 4 to (4, 3), which is a
solution to the problem. The state-space tree of this search is shown in figure.
The solution of 8 queens problem can be obtained similar to the solution of 4 queens.
problem.X1=3, X2=6, X3=2, X4=7, X5=1, X6=4, X7=8, X8=5, the solution can be shown as
Problem-2
Apply backtracking to the problem of finding a Hamiltonian circuit in the following graph
Solution:
By backtracking yields the following state-space tree:
Problem 3
2. Color the Following graph with minimum number of distinct colors using backtrack
technique.
Solution: