N-Queens via Backtracking — Pseudocode

Problem

Place $N$ queens on $N×N$ chessboard so no two attack (no same row, column, diagonal).

State & Constraints

• Row $r$ gets one queen in column $col[r]$ ($0..N-1$).
• Explicit: $col[r] \in \{0..N-1\}$
• Implicit: $col[i]
  eq col[j]$and$|col[i]-col[j]|
  eq |i-j|$for$i
  eq j$.

Helper

IsSafe(row, col):
  for i=0..row-1:
    if col[i]==col or abs(col[i]-col)==row-i:
      return false
  return true

Backtracking Pseudocode

Global col[0..N-1], solutions=[]

SolveNQueens(row):
  if row==N:
    solutions.append(copy(col))  // found one
    return // or return true if only one needed
  for c=0..N-1:
    if IsSafe(row,c):
      col[row]=c
      SolveNQueens(row+1)
      // backtrack implicit: next iteration tries next c
      // col[row] overwritten
  // no c works → backtrack to previous row

Main: SolveNQueens(0)

Iterative version uses stack; optimized uses boolean arrays colUsed, diag1, diag2 for $O(1)$ safe check:

colUsed[c] && diag1[row+c] && diag2[row-c+N]

Trace $N=4$ (first solution)

Row0 → c0? conflict? Try c0 safe → [0,]
Row1 → c0 attack col, c1 diag, c2? diag? Actually 0-2 diff2 vs row diff1 no, col2≠0 → safe → [0,2,]
Row2 → c0 attack?,c1 safe? [0,2,?] c1? Check vs row0: |0-1|=1 diag vs |0-2|=2 no, vs row1 |2-1|=1 vs1 yes diag → unsafe; c3? |0-3|=3 vs2 no, |2-3|=1 vs1 yes? Actually row1 col2 vs row2 col3 diff1 row1 → diagonal → unsafe → backtrack
Row1 next c3 safe → [0,3,] → Row2 c1 safe → [0,3,1,] → Row3 c? no → backtrack ... eventually finds [1,3,0,2] → queens at (0,1),(1,3),(2,0),(3,2).

Complexities

• Worst $O(N!)$ (branching reduces), $N=8$ has 92 solutions.
• Space $O(N)$ recursion.
• With pruning via forward checking, feasible up to $N≈30$ for enumeration, larger via heuristics.