Recursive N-Queens Visualization

The n-queens problem

A chess queen attacks every square in its row, its column and both of its diagonals. The n-queens problem asks for a way to put n queens on an n × n board so that no two attack each other. For n = 8 there are 92 solutions; for n = 2 and n = 3 there are none.

Trying every way to put 8 queens on 64 squares would mean more than four billion boards. Backtracking does much better: build the solution one queen at a time, and as soon as a partial placement has a conflict, abandon it and try the next possibility, without ever extending it further. Enter a board size from 1 to 8 and press Queens.

The idea

No two queens can share a column, and there are n queens and n columns, so every column holds exactly one queen. That lets us describe a placement with a single array: board[c] is the row of the queen in column c, and -1 means "no queen yet". Columns are then conflict-free by construction, and only rows and diagonals have to be checked. Two queens in columns i and j are:

• in the same row if board[i] == board[j];
• on the same diagonal if the distance between their rows equals the distance between their columns: abs(board[j] - board[i]) == j - i.

The recursive function queens(board, current, size) assumes columns 0 to current - 1 already hold non-attacking queens, and tries to complete the board. It tries each row for column current in turn; if the new queen is safe, it recurses on the next column. If the recursive call reports failure, it moves the queen to the next row. If no row works, it returns false, and its caller moves its queen: that step back is the backtrack.

def calcQueens(size):
    board = [-1] * size
    return queens(board, 0, size)

def queens(board, current, size):
    if (current == size):
        return true                       # every column has a queen: solved
    else:
        for i in range(size):             # try each row for this column
            board[current] = i
            if (noConflicts(board, current)):
                done = queens(board, current + 1, size)
                if (done):
                    return true
        return false                      # no row works: backtrack

def noConflicts(board, current):          # check the new queen against the earlier ones
    for i in range(current):
        if (board[i] == board[current]):
            return false                  # same row
        if (current - i == abs(board[current] - board[i])):
            return false                  # same diagonal
    return true

(The code on the canvas prints the diagonal test as abs(board[current] = board[i]); it means a minus, as above, and the animation computes it that way.)

What the canvas shows

The code is on the left, with the line being executed in red. The boxes in the middle are the activation records (stack frames) of the calls that are currently running: calcQueens at the top, then one queens frame per column filled so far (with its current, size, loop variable i and done), and a short-lived noConflicts frame while a queen is being checked. When the stack gets too tall it continues in a second column. The frames' board fields all point to the same array, drawn on the right with its indices in blue; below it is the chessboard itself, where column c shows a Q in row board[c]. During a check, the two queens being compared turn red. When a call finishes, its frame disappears and "Return Value = ..." shows what it returned.

Worked example: 4 queens

Here is the complete search for n = 4, exactly as the page performs it. Indentation shows the depth of recursion; "X" marks a queen that noConflicts rejects, with the first conflict it finds.

col 0: row 0  board=[0]        ok
  col 1: row 0  board=[0,0]      X same row as col 0
  col 1: row 1  board=[0,1]      X diagonal with col 0
  col 1: row 2  board=[0,2]      ok
    col 2: row 0  board=[0,2,0]    X same row as col 0
    col 2: row 1  board=[0,2,1]    X diagonal with col 1
    col 2: row 2  board=[0,2,2]    X diagonal with col 0
    col 2: row 3  board=[0,2,3]    X diagonal with col 1
    col 2: no row works -> return false        (backtrack)
  col 1: row 3  board=[0,3]      ok
    col 2: row 0  board=[0,3,0]    X same row as col 0
    col 2: row 1  board=[0,3,1]    ok
      col 3: row 0  board=[0,3,1,0]  X same row as col 0
      col 3: row 1  board=[0,3,1,1]  X diagonal with col 1
      col 3: row 2  board=[0,3,1,2]  X diagonal with col 2
      col 3: row 3  board=[0,3,1,3]  X diagonal with col 0
      col 3: no row works -> return false      (backtrack)
    col 2: row 2  board=[0,3,2]    X diagonal with col 0
    col 2: row 3  board=[0,3,3]    X same row as col 1
    col 2: no row works -> return false        (backtrack)
  col 1: no row works -> return false          (backtrack: move the first queen)
col 0: row 1  board=[1]        ok
  col 1: row 0  board=[1,0]      X diagonal with col 0
  col 1: row 1  board=[1,1]      X same row as col 0
  col 1: row 2  board=[1,2]      X diagonal with col 0
  col 1: row 3  board=[1,3]      ok
    col 2: row 0  board=[1,3,0]    ok
      col 3: row 0  board=[1,3,0,0]  X same row as col 2
      col 3: row 1  board=[1,3,0,1]  X same row as col 0
      col 3: row 2  board=[1,3,0,2]  ok
        queens(current = 4): all four columns filled -> return true

A queen in the top-left corner can't be part of any solution, and the search proves it before moving on. The answer is board = [1, 3, 0, 2]:

        col 0  1  2  3
row 0       .  .  Q  .
row 1       Q  .  .  .
row 2       .  .  .  Q
row 3       .  Q  .  .

In total the search makes 9 calls to queens (including the final one with current == 4) and 26 calls to noConflicts. At its deepest the stack holds calcQueens and five queens frames (the last one, with current == 4, returns true at once). The other solution for 4 queens is the mirror image, [2, 0, 3, 1]; the page stops at the first one it finds.

Why it is correct

Picture every partial placement (the first k columns filled) as a node in a tree whose children are the n ways to fill the next column. Plain recursion over this tree would visit all nⁿ complete placements. Backtracking visits it in the same order but skips a subtree only when its root already contains two attacking queens. Adding more queens can never remove a conflict, so every placement in a skipped subtree is also invalid: no solution is ever skipped. Because noConflicts checks the new queen against all earlier ones, every placement that is extended is valid, so when current == size the board really is a solution. And when the top-level call returns false (for 2 or 3 queens), the search has ruled out every possibility, so no solution exists. Overwriting board[current] for each new row is enough to undo the previous attempt; the entries to the right are ignored because only columns before current are checked.

Running time and space

With one queen per column and the row check, at most n(n−1)(n−2)··· partial placements survive, so the search tree has O(n!) nodes, and each check costs O(n). That is exponential in the worst case, but pruning makes the real numbers much smaller. To find the first solution this page's algorithm makes this many calls to queens:

n              1   2   3   4   5    6    7     8
queens calls   2   3   6   9   6   32   10   114
solutions      1   0   0   2  10    4   40    92      (total number, for comparison)

(For n = 8 that is 876 conflict checks, so the animation takes a while; use the speed slider.) The space used is the n-element array plus a recursion depth of n + 1 frames: O(n).

Common mistakes and variants

• Returning too early: when a recursive call fails, the loop must continue with the next row, not return false at once. Only after all rows fail does the function report failure.
• The diagonal test needs the absolute value: the other queen may be above or below. Checking only one direction misses half the conflicts.
• Checking the wrong columns: compare only with columns 0 .. current-1. Later entries of board may hold stale values from an abandoned attempt.
• Base case: current == size means success (all columns filled), not failure.
• No solution: for 2 and 3 queens the function correctly returns false. For 1 queen the answer is trivial.
• All solutions: instead of returning true at the base case, record or count the board and keep going; this gives 92 for 8 queens.
• Faster checks: keep boolean arrays for used rows and used diagonals (row + col and row - col are constant along each diagonal) so a check is O(1); bitmask versions count all solutions for boards up to the high teens in seconds. For very large n, local search (min-conflicts) or explicit formulas find a solution almost instantly.

Where it is used

The n-queens puzzle is the standard first example of backtracking. The same pattern — choose, check constraints, recurse, undo — solves Sudoku and crossword puzzles, graph coloring and timetabling problems, generates permutations and subsets, and sits at the core of constraint-satisfaction and SAT solvers (the DPLL algorithm is backtracking with clever pruning).

References

Eight queens puzzle

Backtracking