Backtracking: N-Queens Problem

In chess, a queen can attack any piece that shares its row, its column, or one of its two diagonals.

The N-Queens problem asks: can we place N queens on an N×N board so that no two queens attack each other?

That means our placement must obey three rules:

1. No two queens in the same row.
2. No two queens in the same column.
3. No two queens on the same diagonal.

We will use a small board, N = 4. It is easy to follow and has exactly 2 valid solutions.

There are a huge number of ways to drop 4 queens onto 16 squares, so checking every possible placement is wasteful.

Backtracking is much smarter. The key idea: place one queen per row.

• Start at row 0. Try the columns one at a time, left → right.
• For a column, check if placing a queen there is safe (no earlier queen attacks it).
• If it is safe, place the queen and move on to the next row.
• If a row has no safe column, we hit a dead end. We undo (remove) the last queen we placed and try its next column instead. This "undo" step is the backtrack.

Because we give up on a bad path the moment it fails, we prune away enormous numbers of placements we never have to look at.

When we want to put a new queen at row r, column c, we only need to compare it against the queens already placed in the earlier rows (rows 0 to r-1). We never need to check the same row, because we only ever place one queen per row.

A new queen at (r, c) is unsafe if some earlier queen at (r', c') shares:

• the same column: c == c', or
• a diagonal: |r - r'| == |c - c'| (the row distance equals the column distance).

Tiny worked check. Suppose a queen already sits at (0, 0). We want to try (1, 1).

• Same column? 1 == 0? No.
• Same diagonal? |1 - 0| == |1 - 0| → 1 == 1? Yes — they are on a diagonal.

So (1, 1) is unsafe and we reject it. We would then try (1, 2) instead.

Watch the backtracking search on the 4×4 board. The current cell being tried is outlined in cyan. Placed queens turn green. When a placement conflicts with an earlier queen, the attacking squares flash red and we reject it. When a row runs out of options we backtrack and remove the last queen. The counter shows how many full solutions we have found so far — there are 2 in total.

The function SOLVE(row) tries to place a queen in row and then recurses to the next row. When row reaches N, every row has a safe queen, so we have found a complete solution.

In the worst case there are up to N column choices in each of the N rows, which gives a rough bound of O(N!) (pruning by the safety check removes most of those branches in practice, so the real work is far smaller).

The board only needs O(N) memory: we store a single column index per row in an array, plus the recursion stack which is at most N deep.

Step through the full search at your own pace. Use the controls to move forward and back, or press play to watch the queens get placed, rejected, and backtracked until both solutions are found.