Given a chessboard of n x n, the n-queen problem involves placing queens in such a way that they cannot attack each other.
The queens can attack each other if they are placed in:
No valid solution exists for a 2 x 2 or a 3 x 3 chessboard.
Backtracking can be used to solve this problem.
Begin with the left-most column.
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.
Backtrack to the previous column by returning zero if no solution exists after the completion of step 2.
Stop the recursion when all the queens are placed.
The following illustration shows the algorithm in action on a 4 x 4 chessboard:
View all Courses