Card 06/ 09
Pruning a Branch as Soon as It Breaks a Rule
Place queens row by row, and abandon a row the moment a queen is attacked.
Pruning means abandoning a partial solution the moment it breaks a rule, so that nothing below it in the tree is ever built. This walkthrough traces a pruned backtracking search placing four queens on a 4 × 4 chessboard, from the first queen to the first solution.
The puzzle is to place n queens so that no two attack each other; a queen attacks along its row, its column and both diagonals. Each row must hold exactly one queen, so the search places one per row, top to bottom, trying the columns left to right. Before placing a queen it checks the column and both diagonals against the queens already placed, and skips any square that is attacked. When a row has no safe square, the search undoes the queen in the row above and moves it on.
In the boards below, Q is a queen and a dot an empty square; columns and rows are numbered from 0. A run printed every placement, skip and removal.
Four queens placed row by row, with each attacked square skipped
Row 0, column 0
The first queen goes in the first column of the top row, since nothing attacks an empty board.
Q...
....
....
....Row 1, column 2
Columns 0 and 1 of row 1 are attacked, by the column and by the diagonal, so the search skips them without placing anything and puts the queen in column 2.
Q...
..Q.
....
....Row 2 is a dead end
Every square in row 2 is attacked by one of the two queens. The search removes the queen from row 1, column 2, and nothing below that placement was ever built.
Q...
....
....
....Row 1, column 3
The row 1 queen moves on to column 3, the only other safe square.
Q...
...Q
....
....Row 2, column 1
Column 0 of row 2 is attacked; column 1 is safe.
Q...
...Q
.Q..
....Back to row 0
Every square in row 3 is attacked. The search removes the row 2 queen and finds no other safe square in row 2, removes the row 1 queen and finds no column after 3, and removes the row 0 queen. Every board that starts with a queen in the top-left corner has failed.
....
....
....
....Row 0, column 1
The top queen moves to column 1.
.Q..
....
....
....Rows 1 and 2
In row 1, columns 0, 1 and 2 are attacked and column 3 is safe. In row 2, column 0 is safe at once.
.Q..
...Q
Q...
....Row 3, column 2: solved
Columns 0 and 1 of row 3 are attacked and column 2 is safe. Four queens, none attacking another: the columns by row are 1 3 0 2.
.Q..
...Q
Q...
..Q.The search placed 8 queens to reach the first solution. Each skipped square is a whole subtree pruned: the boards below it would have been built, checked and thrown away by a search that only checked complete boards.
The run then counted the full search, which finds every solution. With pruning it placed 16 queens and found the 2 solutions. Without pruning, placing a queen in every column of every row and checking only complete boards, it placed 340 queens and built all 256 full boards, 4⁴, to find the same 2. On an 8 × 8 board the gap is 2,056 queens placed against 19,173,960, and 16,777,216 full boards built, to find the same 92 solutions.
Pruning leaves the search exponential in n, so a bound in Big O can look the same with or without it; what changes is how much of the tree is ever built, here by a factor of more than 9,000 at n = 8. To prune, check each rule on the partial solution as soon as the choice that could break it is made, not at the leaf. A rule that can only be checked on a complete solution prunes nothing.
← → move through sections and cards