Skip to content
doubtly

1 answer

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.

  1. Place a queen in row 1, column 1.
  2. Move to the next row and place the queen in the first safe column.
  3. If no column in a row is safe, go back to the previous row and move that queen to its next safe column.
  4. 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.
Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.