N-Queens Problem
What you'll learn: How to place N chess queens on an N×N board so that no two queens attack each other, using recursion and backtracking.
The Classic Puzzle
The N-Queens problem asks: can you place N queens on an N×N chessboard so that no queen can attack another? Remember, queens move horizontally, vertically, and diagonally, so no two queens can share the same row, column, or diagonal.
Row-by-Row Strategy
The key insight is to place one queen per row. Start at row 0 and try each column. For each valid placement:
- Place a queen in the current row
- Recursively try to place queens in remaining rows
- If you successfully fill all rows, you've found a solution!
- If you get stuck (no safe column exists), backtrack: remove the last queen and try the next column
This is exactly like generating permutations or subsets, but with an extra constraint check—is this position safe from all previously placed queens?
Checking for Conflicts
Before placing a queen at row r, column c, verify:
- No queen already exists in column
c(check all previous rows) - No queen on the diagonal going up-left (row - i = col - previous_col)
- No queen on the diagonal going up-right (row + col = previous_row + previous_col)
We only check upward because we place queens top-to-bottom, so no queens exist below yet.
Why Backtracking?
Without backtracking, you'd have to try all possible placements exhaustively. Backtracking prunes entire branches: if row 2's placement makes row 3 impossible, you abandon that branch immediately rather than exploring billions of dead-end arrangements.
Key Takeaway: The N-Queens problem demonstrates backtracking's power: place queens row-by-row, validate each placement against previous queens, and backtrack when conflicts arise—pruning the search space efficiently.