Sign in to watch this lesson
Algorithms - Recursion, Backtracking and Combinatorics · 3:53
Backtracking with Pruning
We solve the eight queens puzzle row by row, greying out every attacked square, and watch the search hit its first dead end (row six has no free square) and back up. Pulled back as a tree, checking each queen as it is placed visits 2,057 nodes against 19,173,961 for one queen per row checked only at the end, and both find the same 92 solutions. Then three bitmasks (columns and two diagonals that shift one place per row) make each check a couple of instructions: 14 queens, over 27 million nodes, ran in a fraction of a second on this Mac, several times faster than arrays; symmetry halves the work, and the most constrained choice goes first.
You will learn
- Solve N-Queens with backtracking that places one queen per row and rejects attacked squares before descending.
- Measure how pruning shrinks a search tree (2,057 against 19,173,961 nodes on 8 x 8) without changing the answers.
- Implement the bitmask version with cols, d1 and d2 masks, shifting the diagonal masks per row and taking the lowest free bit with avail & -avail.
- Apply symmetry breaking and most-constrained-first ordering, and avoid the negative diagonal index and missing un-mark bugs.