What is the N-Queens Problem?
The N-Queens puzzle is the problem of placing $N$ chess queens on an $N \times N$ chessboard so that no two queens threaten each other. According to chess rules, a queen can attack another piece if it shares the same row, column, or diagonal.
Therefore, a valid solution requires that:
- No two queens share the same row.
- No two queens share the same column.
- No two queens share the same diagonal (both major and minor diagonals).
The Backtracking Strategy
Backtracking is a systematic way to search for solutions by trying to build a solution incrementally, one step at a time, and removing choices (backtracking) that fail to satisfy the constraints.
For N-Queens, we place queens column by column:
- Start in the leftmost column (column 0).
- For the current column, try placing a queen in row 0, 1, ..., $N-1$ and check if the position is safe.
- If placing a queen in row $R$ is safe, record the choice and recursively move to the next column.
- If we successfully place a queen in the last column ($N-1$), a solution is found!
- If we find that no row in the current column is safe, we backtrack: return to the previous column, remove the queen placed there, and resume trying the next row candidates.
Checking If a Position is Safe
Since we place queens column-by-column (from left to right), we only need to check for attacks on the left side of the current position:
- Horizontal row: Check if any queen is already in the same row to the left.
- Upper-left diagonal: Check if any queen is in the diagonal going up and left.
- Lower-left diagonal: Check if any queen is in the diagonal going down and left.
Note: We do not need to check columns to the right, because we haven't placed any queens there yet.
Complexity Analysis
Time Complexity: O(N!)
There are $N$ choices for placing the first queen, at most $N-2$ choices for the second, $N-4$ for the third, and so on. In the worst case, the backtracking search tree generates $O(N!)$ states.
Space Complexity: O(N)
The auxiliary space required consists of the recursion stack ($O(N)$ depth) and the board array ($O(N)$ size to record the row positions of the queens).