learn.aathan.in

4-Queens and 8-Queens: Backtracking and Constraint Search

Place N queens on an N×N board so none attack each other. The full 4-queens backtracking trace, why the naive space is 16 million and the smart one is 40,320, plus hill climbing and min-conflicts.

Place NN queens on an N×NN \times N chessboard so that no two attack each other. A queen attacks along its row, its column, and both diagonals.

This is the first problem on these pages where the goal is not a path. You don’t care how you got to a valid arrangement — only that you have one. That changes everything about how you search, and it introduces a family of techniques (constraint satisfaction) that runs half of modern scheduling and verification software.

The problem

Q A queen attacks along: — its row — its column — both diagonals Place N of them so no two share any row, column or diagonal. One queen on an empty 8×8 board covers 27 of the other 63 squares.

The representation that shrinks the problem by 400×

Start with the obvious encoding: an 8×88 \times 8 grid of booleans, choose 8 squares. That gives

(648)=4,426,165,368\binom{64}{8} = 4{,}426{,}165{,}368

placements. Four billion. But almost all of them are trivially invalid, and you can eliminate whole classes of them by choosing a better representation rather than by searching harder.

Observation 1: exactly one queen per column. If two queens shared a column they’d attack; and with NN queens on NN columns, the pigeonhole principle says each column gets exactly one. So represent the board as an array where board[col] = row:

board = [1, 3, 0, 2]   # 4-queens: col 0 → row 1, col 1 → row 3, ...

Space drops to NN=88=16,777,216N^N = 8^8 = 16{,}777{,}216.

Observation 2: exactly one queen per row, too. Same argument. So the array must be a permutation of 0…N−10 \dots N-1:

Space drops to N!=8!=40,320N! = 8! = 40{,}320.

4,426,165,368 16,777,216 40,320 C(64,8) — any 8 squares 8⁸ — one per column 8! — a permutation A 110,000× reduction — from thinking about the problem, not from faster code.

This is the most transferable idea on the page. Before you optimise a search, ask whether the representation is throwing away work. Encoding a constraint into the data structure eliminates violations for free, at zero runtime cost. Searching harder can never beat not having to search.

With the permutation encoding, only diagonals remain to be checked. Two queens at columns c1,c2c_1, c_2 and rows r1,r2r_1, r_2 share a diagonal exactly when

∣c1−c2∣=∣r1−r2∣|c_1 - c_2| = |r_1 - r_2|

def safe(board, col, row):
    """Can we put a queen at (col, row) given queens already in 0..col-1?"""
    for c in range(col):
        r = board[c]
        if r == row or abs(col - c) == abs(row - r):
            return False
    return True

Backtracking, traced on 4-queens

Backtracking is depth-first search with one addition: check constraints as you go, and abandon a branch the moment it’s violated. Don’t build a complete board and then test it — test after every single placement.

The 4-queens board has 4!=244! = 24 permutations and exactly 2 solutions. Here’s the search finding the first one.

Q 1. col 0 → row 0 Q Q 2. col 1 → row 2 (rows 0,1 unsafe) Q Q 3. col 2 — every row unsafe DEAD END → backtrack undo col 1, try the next row Q Q 4. col 1 → row 3 Q Q Q 5. col 2 → row 1 (only option) QQQQ 6. col 3 → row 2 ✓ SOLUTION [0, 3, 1, 2] Backtracking checks constraints after every placement — it never builds an invalid board. Plain generate-and-test would build all 24 permutations before testing any of them. The other 4-queens solution is its mirror: [2, 0, 3, 1]

Notice step 3. With queens at (col 0, row 0) and (col 1, row 2), column 2 has no safe square: row 0 shares a row with the first queen, row 1 is on a diagonal from it, row 2 shares a row with the second, and row 3 is on a diagonal from the second. All four ruled out. The search doesn’t need to place a fourth queen to discover that this branch is doomed — it can tell after two placements.

That early detection is the entire value of backtracking. Generate-and-test would build all 24 permutations and test each; backtracking on 4-queens examines just 8 partial boards.

The backtracking solver

def solve_n_queens(n, all_solutions=True):
    """board[col] = row. Returns a list of solutions."""
    solutions = []
    board = [-1] * n

    def safe(col, row):
        for c in range(col):
            r = board[c]
            if r == row or abs(col - c) == abs(row - r):
                return False
        return True

    def place(col):
        if col == n:
            solutions.append(board.copy())
            return not all_solutions            # stop early if we only want one
        for row in range(n):
            if safe(col, row):
                board[col] = row
                if place(col + 1):
                    return True
                board[col] = -1                 # undo — this is the backtrack
        return False

    place(0)
    return solutions


def render(board):
    n = len(board)
    for r in range(n):
        print(' '.join('Q' if board[c] == r else '.' for c in range(n)))


if __name__ == '__main__':
    for n in (4, 6, 8):
        sols = solve_n_queens(n)
        print(f'{n}-queens: {len(sols)} solutions')
    print()
    render(solve_n_queens(8)[0])

The faster version: O(1) safety checks

The safe function above is O(n)O(n) per check. You can make it O(1)O(1) by tracking which rows and diagonals are already occupied in three sets.

The trick is the diagonal identity: on a \-diagonal, row - col is constant; on a /-diagonal, row + col is constant.

def solve_fast(n):
    """Same result, O(1) constraint checks via three occupancy sets."""
    solutions, board = [], []
    rows, diag1, diag2 = set(), set(), set()

    def place(col):
        if col == n:
            solutions.append(board.copy())
            return
        for row in range(n):
            if row in rows or (row - col) in diag1 or (row + col) in diag2:
                continue
            board.append(row)
            rows.add(row); diag1.add(row - col); diag2.add(row + col)

            place(col + 1)

            board.pop()
            rows.remove(row); diag1.discard(row - col); diag2.discard(row + col)
    place(0)
    return solutions

The three lines after the recursive call are the backtrack. Every state change you make going down must be exactly undone coming back up. A forgotten discard is the classic N-queens bug: the solver works for n=4n = 4, silently misses solutions for n=8n = 8, and you spend an evening finding it.

How many solutions are there?

nnSolutionsUnique up to symmetryNodes explored
1111
2003
3006
42117
510254
641153
7406552
892122,057
107249235,539
1214,2001,787856,189

n=2n = 2 and n=3n = 3 have no solutions at all — the board is too cramped for the diagonals to avoid each other. Every n≥4n \ge 4 has at least one.

The “unique up to symmetry” column divides out the 8 symmetries of a square (4 rotations × 2 reflections). The 92 solutions for 8-queens are really 12 distinct patterns; one of them is symmetric under 180° rotation, so it only generates 4 copies instead of 8, which is why 12×8≠9212 \times 8 \ne 92.

Note that the solution count grows but the node count grows faster — this is still exponential. Backtracking makes 8-queens instant and 20-queens hard.

Backtracking builds a solution incrementally. Local search does the opposite: start with a complete but broken board, and repair it.

Hill climbing with the min-conflicts heuristic

  1. Place one queen in every column, at random.
  2. Count conflicts — pairs of queens attacking each other. That’s your heuristic hh; the goal is h=0h = 0.
  3. Pick a queen that’s in conflict. Move it, within its column, to the row that minimises total conflicts.
  4. Repeat.
QQQQ h = 6 conflicts all four on one diagonal min-conflicts move within column QQQQ h = 0 — solved [1, 3, 0, 2] Local search doesn't build a solution — it repairs one. Scales to n = 1,000,000 in about 50 moves. Risk: local minima where no single move improves h. Fix: random restart, or sideways moves. 
import random

def min_conflicts(n, max_steps=100_000):
    """Local search. Solves n = 1,000,000 in seconds; backtracking cannot."""
    board = list(range(n))
    random.shuffle(board)

    def conflicts(col, row):
        return sum(1 for c in range(n)
                   if c != col and (board[c] == row or abs(c - col) == abs(board[c] - row)))

    for _ in range(max_steps):
        clashing = [c for c in range(n) if conflicts(c, board[c]) > 0]
        if not clashing:
            return board                             # h = 0 — solved
        col = random.choice(clashing)
        counts = [conflicts(col, r) for r in range(n)]
        best = min(counts)
        board[col] = random.choice([r for r in range(n) if counts[r] == best])
    return None

The scaling difference is enormous:

nnBacktrackingMin-conflicts
8instantinstant
30~secondsinstant
100impracticalinstant
1,000,000impossible~50 moves

Min-conflicts solves million-queens in about 50 moves on average, almost independent of nn. But it has no completeness guarantee: on a problem with no solution it never terminates, and on a hard one it can stall in a local minimum where every single move makes things worse. That’s the trade — backtracking is complete and slow; local search is incomplete and fast.

Pick by what you need. If a solution definitely exists and you just want one, local search wins. If you need all solutions, or proof that none exists, you need backtracking.

N-queens as a constraint satisfaction problem

The general framing, which is where this technique becomes reusable:

  • Variables — Q0,…,Qn−1Q_0, \dots, Q_{n-1}, one per column
  • Domains — each Qi∈{0,…,n−1}Q_i \in \{0, \dots, n-1\} (which row)
  • Constraints — for all i≠ji \ne j: Qi≠QjQ_i \ne Q_j and ∣i−j∣≠∣Qi−Qj∣|i - j| \ne |Q_i - Q_j|

Once written this way, generic CSP machinery applies:

TechniqueWhat it does
Forward checkingAfter each assignment, remove now-illegal values from the remaining domains. If any empties, backtrack immediately.
Arc consistency (AC-3)Propagate constraints until every value has a consistent partner. Prunes far more than forward checking.
MRV heuristicAssign the variable with the fewest remaining values first — fail fast.
LCV heuristicTry the value that rules out the fewest options for other variables.
Conflict-directed backjumpingOn failure, jump back to the variable that actually caused it, not just the previous one.

Forward checking alone roughly halves the nodes explored on 8-queens. MRV plus forward checking makes n=30n = 30 practical for exact enumeration.

Why this problem matters

N-queens itself is a puzzle. Constraint satisfaction is an industry.

  • Exam and shift timetabling — variables are events, domains are time slots, constraints are “no room double-booked”, “no student in two exams at once”. Literally the same solver.
  • Sudoku — 81 variables, domains 1–9, constraints on rows, columns and boxes. Arc consistency alone solves most newspaper puzzles without search.
  • Register allocation — variables are program values, domains are CPU registers, constraints are “two values live at the same time need different registers”. This is graph colouring, a close cousin.
  • Hardware verification — SAT solvers (the industrial descendants of backtracking + constraint propagation) check billion-gate chip designs.
  • Frequency assignment — cell towers whose ranges overlap need different channels.

The two lessons worth carrying away:

  1. Representation beats optimisation. Going from (648)\binom{64}{8} to 8!8! was a 110,000× win, and it came from thinking, not from code.
  2. Complete and incomplete search solve different problems. Backtracking proves things; local search finds things. Know which one you need before you start writing.

Where to go next