1. N-Queen problem is based on chess games.
2. The problem is based on arranging the queens on chessboard in such a way that no two queens can attack each other.
3. The N-Queen problem states as consider a n x n chessboard on which we have to place n queens so that no two queens attack each other by being in the same row or in the same column or on the same diagonal.
4. 2 – Queen’s problem is not solvable because 2 – Queens can be placed on 2 x 2 chess board as shown in figure 9.

1. But 4 – Queen’s problem is solvable.

How to solve N – Queen Problem:

i. Let us take the example of 4 – Queens and 4 x 4 chessboard.

ii. Start with an empty chessboard.

iii. Place queen 1 in the first possible position of its row i.e. on 1st row and 1st column.

iv. Then place queen 2 after trying unsuccessful place (1, 2), (2, 1), (2, 2) at (2, 3) i.e. 2nd row and 3rd column.

v. This is a dead end because a 3rd queen cannot be placed in next column, as there is no acceptable position for queen 3. Hence algorithm backtracks and places the 2nd queen at (2, 4) position.

vi. Then place 3rd queen at (3,2) but it again another dead lock end as next queen (4th queen) cannot be placed at permissible position.

vii. Hence we need to backtrack all the way up to queen 1 and move it to (1, 2). viii. Place queen 1 at (1, 2), queen 2 at (2, 4), queen 3 at (3, 1) and queen 4 at (4, 3).

ix. Thus the solution is obtained (2, 4, 1, 3) in row wise manner. x. The one of the solution to 8 – Queen Problem is shown below.

xi. The solution is obtained (6, 4, 7, 1, 3, 5, 2, 8) in row wise manner.