Skip to content
doubtly

1 answer

Backtracking places queens one row at a time and undoes (backtracks) a placement as soon as no safe column is left for the next row.

Problem. Place \(n\) queens on an \(n\times n\) board so that no two share a row, column or diagonal.

Idea. Let x[k] = column of the queen in row k. A queen at \((k, x_k)\) is safe from an earlier queen at \((i, x_i)\) if

\[x_i \ne x_k \quad\text{and}\quad |x_i - x_k| \ne |i - k|.\]

NQueens(k, n):
  for col = 1 to n:
    if Place(k, col):        // safe from rows 1..k-1
      x[k] = col
      if k == n: print x
      else: NQueens(k+1, n)

Trace for 4 queens (columns listed row by row):

  • Q1 = 1, Q2 = 3 → no safe column for Q3 → backtrack.
  • Q2 = 4, Q3 = 2 → no safe column for Q4 → backtrack; Q3 has no other choice → backtrack; Q2 has no other choice → backtrack to Q1.
  • Q1 = 2, Q2 = 4, Q3 = 1, Q4 = 3 → solution (2, 4, 1, 3).

State space tree (part):

              root
          /          \
       Q1=1          Q1=2
       /   \            \
    Q2=3   Q2=4         Q2=4
     X       |            |
           Q3=2         Q3=1
             X            |
                        Q4=3  (solution)

X marks a dead node (no safe column for the next queen), where the algorithm backtracks. Continuing the search gives the second solution (3, 1, 4, 2), the mirror image.

Without pruning, there would be \(4^4 = 256\) leaf placements; backtracking visits only a small part of the tree because unsafe branches are cut immediately.

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.