The N-Queens Puzzle and Backtracking, Explained

After reading this you will understand how backtracking search places N queens on a chessboard, why it prunes billions of dead arrangements without ever visiting them, and how to count the solutions for any board size.

What the puzzle is

The task is simple to state. Put N queens on an N×N chessboard so that no two attack each other. A queen attacks along her row, her column, and both diagonals. So no two queens may share a row, a column, or a diagonal.

On the standard 8×8 board this is the eight-queens puzzle. There are 92 ways to do it. That number is tiny next to the number of ways to drop 8 queens on 64 squares, which is \binom{64}{8} = 4{,}426{,}165{,}368, about 4.4 billion. A blind search that checked every arrangement would waste almost all of its work. Backtracking finds all 92 solutions after examining only a few thousand partial placements.

The hook is the retreat. The algorithm marches forward placing queens, and when a row offers no safe square it does not give up. It steps back one row, moves the earlier queen, and tries again. That single idea, undo and retry, is the whole method.

Why one queen per row

The first useful observation cuts the problem down before any search begins. Because no two queens can share a row, and you need N queens on N rows, every row holds exactly one queen. So a solution is just a choice of column for each row.

Write the answer as a list c_0, c_1, \dots, c_{N-1} where c_r is the column of the queen in row r. This turns a placement problem into a sequence of N choices, each from N columns. The raw count of such lists is N^N, which for N = 8 is 8^8 = 16{,}777{,}216.

Two more constraints trim it further. No shared column means the list must have distinct values, so it is a permutation. That drops the count to N! = 40{,}320 for N = 8. The diagonal rule removes almost all of those, leaving 92.

The attack test

To decide whether a new queen in row r, column c is safe against a queen already placed in row r', column c', you check three things.

The first inequality forbids the same column. The second forbids the same anti-diagonal: every square on one anti-diagonal shares the value r + c. The third forbids the same main diagonal, where r - c is constant. You never need to test the row, because you place exactly one queen per row by construction.

A faster equivalent test uses one comparison for both diagonals. Two queens sit on a common diagonal when the row gap equals the column gap in absolute value.

Here |r - r'| is the number of rows between the queens and |c - c'| is the number of columns. When those match, the queens lie on a 45-degree line, so they attack. When they differ, the diagonals are clear.

How backtracking searches

The algorithm builds the column list one row at a time and abandons any partial list the moment it becomes illegal. In pseudocode form the recursion is short:

1. If every row has a queen, record a solution and return.
2. For the current row, try each column from 0 to N-1.
3. If that column is safe against all queens placed so far, place the queen and recurse on the next row.
4. When the recursion returns, remove the queen (this is the backtrack) and try the next column.
5. If no column in the current row is safe, return to the previous row.

The power lives in step 3. When a partial placement of the first k rows already fails, every one of the N^{N-k} ways of filling the remaining rows is thrown out at once, unvisited. Backtracking never enumerates those subtrees. That is why 92 solutions fall out of a few thousand node visits instead of billions.

Counting solutions across board sizes

The solution count grows fast but not smoothly. The 2×2 and 3×3 boards have zero solutions: they are too cramped for the diagonal rule to leave room. Every board from 4×4 up has at least one.

The second column counts every board separately. The third counts only boards that differ after you remove the 8 symmetries of the square (4 rotations and their mirrors). The 92 solutions for N = 8 collapse to 12 essentially different ones. Notice that N = 6 dips to 4 solutions while N = 5 has 10. The count is not monotone.

Watch the search tree shrink

The instructive thing a static page cannot show is how much pruning cuts the work as N grows. The permutation count N! is a floor on what a column-distinct search would face, yet backtracking visits far fewer nodes because it drops diagonal failures early.

Common mistakes

Three errors trip up people writing or reasoning about this search.

Forgetting to undo the queen

Backtracking only works if step 4 actually removes the queen before trying the next column. Leave her on the board and the state corrupts, and the search reports placements that share squares.

Testing the row

Adding a row check wastes time and hides a bug. If you place one queen per row by design, no two can ever share a row, so the row test is always true and adds nothing.

Confusing the two symmetry counts

The 8-queens puzzle has 92 solutions but only 12 fundamental ones. Reporting 12 as "the answer" is fine only if you say "up to rotation and reflection." Most solvers, including this visualizer, count all 92.

How dead ends distribute

The number of dead ends the search hits gives a feel for how hard a board is. A dead end is a legal partial placement of the first k rows with no safe square in row k. For N = 8 the search hits 1965 of them before finishing.

Each step up in N multiplies the work by roughly 4 to 5. From N = 8 (2057 nodes) to N = 12 (856189 nodes) the cost grows about 416-fold. This is why a browser visualizer stays smooth up to modest board sizes but slows sharply past N = 14 or so.

Related tools

The N-queens puzzle sits alongside other classic search and constraint toys on this site. The Knight's Tour also visits a board under movement rules and uses a greedy heuristic that avoids most backtracking. The Four Color Map is another constraint-satisfaction problem where you assign labels under adjacency rules. For the recursion pattern itself, the Tower of Hanoi shows a clean recursive unfolding, and the Wave Function Collapse tool collapses possibilities on a grid much as this search collapses column choices. If you want to see combinatorial explosion measured directly, the Fifteen Puzzle and its parity argument make a good companion.

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.