The n-queen problem

Given a chessboard of n x n, the n-queen problem involves placing $n$ queens in such a way that they cannot attack each other.

The queens can attack each other if they are placed in:

• the same column
• the same row
• the same diagonal

No valid solution exists for a 2 x 2 or a 3 x 3 chessboard.

Algorithm

Backtracking can be used to solve this​ problem.

1. Begin with the left-most column.

2. For every row in the column:

   2.1. Try placing the queen such that it cannot attack the queen in the previous columns.

   2.2. If such a placement is possible, add this cell to the solution set and recursively check if this leads to a solution by calling the function on the subsequent column. If it does, return one.

   2.3. Else, remove this cell from the solution set.

3. Backtrack to the previous column by returning zero if no solution exists after the completion of step 2.

4. Stop the recursion when all the queens are placed.

Dry run

The following illustration shows the algorithm in action on a 4 x 4 chessboard: