Place N queens on an N×N board so that no two share a row, a column, or a diagonal. Watch a backtracking search try every square, catch each attack, and back up when a row runs out of options.
How to read this: the search fills one row at a time, top to bottom (rows and columns are numbered from 0). Amber marks the square it is testing; if a red dashed line appears, an earlier queen attacks that square along that line.
Try this: press Step a dozen times and watch a row run out of safe squares, then press Run.
Each line is one row the search is working on. The outlined one is the row it's on now; depth counts the rows.
How to read this: every column and every diagonal on the board gets one box. A box turns green once a queen sits on that line, so testing a square only means looking up three boxes. Each diagonal is named by one number: row minus column (r − c) for ↘ lines, row plus column (r + c) for ↙ lines, which stays the same all along the line.
Try this: hover a square on the board and see which three boxes light up.
Each solution the search finds lands here. Select one to inspect it on the board.
Three ideas turn an astronomically large search into one a laptop finishes in milliseconds.
Two queens in the same row attack each other, so a valid board has exactly one queen in every row. That lets the search work row by row and only choose a column each time.
Adding "one per column" turns each board into a permutation of the columns, cutting the space to N!.
Every square on a ↘ diagonal has the same value of r − c. Every square on a ↙ diagonal has the same r + c. So a diagonal is just one integer.
Keeping three sets of occupied lines makes the attack test constant time. Hover the board to see the values.
Backtracking abandons a partial board the moment it breaks a rule. One bad queen in row 2 eliminates every board that would have extended it, which is most of the tree.
The funnel below measures that pruning for the current N.
How to read this: each step down the funnel is a smarter way to count the boards worth checking. Bars use a log scale, so a bar twice as long as another means the number has twice as many digits.