the N-queens problem
On a chessboard, a queen attacks any piece sharing its row, its column, or either diagonal. The N-queens problem asks: can you place N queens on an N-by-N board so that no two attack each other? For the classic 8-by-8 board the answer is yes (there are 92 distinct solutions), and the puzzle is the textbook showcase for backtracking — small enough to picture, hard enough that blind enumeration is hopeless.
The first insight cuts the search space drastically: since no two queens can share a column, place exactly one queen per column. Now a candidate solution is just a choice of row for each of the N columns — an array where entry c is the row of the queen in column c. Backtracking fills this array left to right: try each row for the current column, and before recursing, check that the new queen does not share a row or a diagonal with any queen already placed (two queens are on the same diagonal exactly when the absolute difference of their rows equals the absolute difference of their columns). If the placement is safe, recurse to the next column; if it conflicts, skip it; if no row works, return and let the previous column try its next row. A full board (all N columns filled) is a solution.
Why it works and why it is fast: restricting to one-per-column shrinks the space from C(N^2, N) board placements to N^N row-choices, and feasibility pruning shrinks it again, because a conflict detected in column 2 prunes away all completions of columns 3 through N at once. The number of solutions grows quickly (it is not known in closed form), so the problem is also a benchmark for clever counting; but as a first lesson it cleanly demonstrates the make-recurse-undo loop and how an early conflict check turns an astronomically large enumeration into something a laptop solves in a blink.
For 4-queens, represent a placement as rows per column. Trying column 0 = row 0, column 1 = row 2 (not attacked), column 2 has no safe row (rows conflict by column or diagonal with the first two), so backtrack and change column 1. The search lands on the two solutions [1,3,0,2] and [2,0,3,1] — read as: in column 0 the queen is in row 1, etc.
One queen per column reduces the problem to a row-array; a diagonal check on each placement does all the pruning.
N-queens has solutions for every N except 2 and 3, and finding one is easy — but counting all solutions stays expensive and has no known simple formula, so do not mistake easy to satisfy for easy to count.