The 8-queen problem is to place 8 queens on an 8×8 chessboard so that no two queens attack each other; it is solved by backtracking.
Constraints. No two queens in the same row, the same column or the same diagonal. Since there are 8 rows and 8 queens, exactly one queen goes in each row, so the solution is written as a tuple \((x_1, \dots, x_8)\), where \(x_k\) is the column of the queen in row \(k\).
Safety test. A queen at \((k, x_k)\) clashes with an earlier queen at \((i, x_i)\) if \(x_i = x_k\) (same column) or \(|x_i - x_k| = |i - k|\) (same diagonal).
Backtracking method.
- Place a queen in row 1, column 1.
- Move to the next row and place the queen in the first safe column.
- If no column in a row is safe, go back to the previous row and move that queen to its next safe column.
- When all 8 rows are filled, a solution is found (record it and continue if all solutions are needed).
Place(k, c):
for i = 1 to k-1:
if x[i] == c or abs(x[i]-c) == abs(i-k): return false
return true
Facts to remember.
- The 8-queen problem has 92 solutions (12 distinct ones if rotations and reflections are treated as the same).
- One solution: (1, 5, 8, 6, 3, 7, 2, 4).
- The state space tree has \(8^8\) leaves without pruning; backtracking cuts unsafe branches early, so only a small fraction is explored. The worst-case time is still exponential, roughly \(O(n!)\) for \(n\) queens.