Pruning

Listing every possible choice is often far too slow. But many branches of the decision tree can be seen to fail early on. Pruning means noticing that, and not going down those branches at all.

Stop as soon as a branch cannot work

A backtracking search builds an answer one decision at a time. After each decision, check whether the partial answer can still lead to a full answer. If it cannot, return at once. Everything below that point in the tree is skipped. This is called pruning, as in cutting branches off a tree.

Example: placing queens

Place n chess queens on an n × n board so that no two attack each other. A queen attacks along its row, its column and both diagonals. Since no two queens can share a row, place exactly one queen in each row, top to bottom. The decision for each row is which column to use.

Place one queen per row. Keep three sets: the columns in use, the down-right diagonals in use and the down-left diagonals in use. For row r, try each column c, and skip it at once if it clashes:

if c in cols or r - c in d1 or r + c in d2:
    continue                  # prune: clashes already

If it does not clash, add c, r − c and r + c to the three sets, place the queens of the next row, then remove the three again. When every row has a queen, count one answer. Writing the whole search is RECR-P5.

Two squares are on the same down-right diagonal exactly when r − c is the same for both, and on the same down-left diagonal when r + c is the same. Keeping these in sets makes each check O(1), instead of comparing with every queen placed so far.

How much pruning saves

The worst case is still exponential, so pruning does not change the Big-O bound you can prove. But in practice it can make the difference between an answer in under a second and no answer in your lifetime. The earlier a branch that cannot succeed is spotted, the bigger the saving.

Kinds of pruning

• Rule broken: the partial answer already breaks a rule, like two queens that clash.
• Cannot reach the goal: for “pick items that add up to exactly T” with positive items, stop when the sum passes T. With the items sorted, you can also stop the loop at the first item that is too big.
• Cannot beat the best: when looking for the best answer, stop when even the best possible finish of this branch is worse than the best answer found so far. This is called branch and bound.
• Repeats: with repeated items, such as [1, 1, 2], skip an item when it equals the one just tried at the same level, so the same group is not listed twice.

Now try RECR-P5, Queens on the yard.