[Backtracking] place N queens on NxN chess board | PROGRAMMING INTERVIEWS

[Backtracking] place N queens on NxN chess board | PROGRAMMING INTERVIEWS

Question: N queen problem is a very famous problem in computer science. This problem ask user to place N chess queens on a NxN chessboard so that no two queens attack each other.

Answer: As the queen can move in any of the eight directions and any number of steps in a single move, there are few solutions, which fit the bill. For N=8, there are 92 distinct solutions. And if solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has only 12 solutions.

Lets assume that we already have some queens placed on the chess board so that no queen can attack each other. Now if we need to place another queen on the board, how will we go about it? Please note that a queen is safe if:

Read full article from [Backtracking] place N queens on NxN chess board | PROGRAMMING INTERVIEWS