N-Queens (Backtracking)

The puzzle

Place N queens on an N × N chessboard so that no two queens attack each other. A queen attacks along its row, its column and both diagonals. The classic version uses a normal 8 × 8 board and has 92 solutions.

Brute force is hopeless

Choosing 8 squares out of 64 gives over 4.4 billion arrangements. Even “one queen per row” still leaves 8⁸ ≈ 16.7 million. We need to be smarter.

Backtracking

Backtracking builds a solution one choice at a time and abandons a path as soon as it can’t possibly work:

1. Go row by row (exactly one queen per row).
2. In the current row, try each column from left to right.
3. If the square is safe, place a queen and move on to the next row.
4. If no column in a row is safe, you’ve hit a dead end: remove the queen from the previous row (backtrack) and try its next column.
5. When all N rows have a queen, you have a solution.

In the 3D model, conflicts flash red (with the queen causing them), safe placements drop a pink queen onto the board, and backtracks show the queen being lifted off again.

Analogy: solving a maze by walking forward and, at every dead end, walking back to the last junction to try another corridor.

Checking “safe” quickly

A new queen at (r, c) is safe if no earlier queen shares:

• the same column c,
• the same “↘” diagonal — same r − c,
• the same “↙” diagonal — same r + c.

Keeping three sets (cols, diag1, diag2) makes every check O(1).

Code

def solve_n_queens(n):
    cols, d1, d2 = set(), set(), set()
    queens = []                       # queens[r] = column of the queen in row r

    def place(r):
        if r == n:
            return True
        for c in range(n):
            if c in cols or (r - c) in d1 or (r + c) in d2:
                continue              # attacked → try next column
            queens.append(c); cols.add(c); d1.add(r - c); d2.add(r + c)
            if place(r + 1):
                return True
            queens.pop(); cols.remove(c); d1.remove(r - c); d2.remove(r + c)  # backtrack
        return False

    return queens if place(0) else None

print(solve_n_queens(8))   # [0, 4, 7, 5, 2, 6, 1, 3]

#include <iostream>
#include <vector>
using namespace std;

int n = 8;
vector<int> queens;
vector<bool> col(n), d1(2 * n), d2(2 * n);

bool place(int r) {
    if (r == n) return true;
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r - c + n] || d2[r + c]) continue;
        col[c] = d1[r - c + n] = d2[r + c] = true;
        queens.push_back(c);
        if (place(r + 1)) return true;
        queens.pop_back();                               // backtrack
        col[c] = d1[r - c + n] = d2[r + c] = false;
    }
    return false;
}

int main() {
    place(0);
    for (int c : queens) cout << c << " ";               // 0 4 7 5 2 6 1 3
}

The backtracking template

The same pattern solves Sudoku, generating permutations and subsets, graph colouring, crosswords and the knight’s tour:

solve(state):
    if state is complete: record / return success
    for each choice:
        if choice is valid:
            apply choice
            if solve(next state): return success
            undo choice                 # backtrack
    return failure

Common mistakes

• Forgetting to undo the choice (remove from the sets) when backtracking.
• Checking only columns and forgetting one of the diagonals.
• Expecting a solution for N = 2 or N = 3 — there is none.