Unit 2: Try Everything

Sometimes the plan really is "try everything"

Unit 1 said n up to 20 lets you try every subset. That is not a consolation prize — for a lot of contest problems, trying everything is the intended solution, and the setter chose 20 to tell you so.

The skill is writing the search neatly, so here is the pattern once, and it never changes.

Each item is in or out

Walk down the list. At each item, do the whole rest of the job twice: once without it, once with it.

When you run out of items, the group you are holding is one of the answers.

Python

def subsets(items, index, chosen):
    if index == len(items):
        print(chosen)
        return
    subsets(items, index + 1, chosen)
    subsets(items, index + 1, chosen + [items[index]])

subsets([1, 2, 3], 0, [])

It prints

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

Two branches per item, so two to the power of n

Eight subsets from three items. Every extra item doubles the work, which is exactly 2 ** n.

That doubling is why the limit is 20 and not 40: a million is nothing, a million million is a fortnight.

Python

def count(items, index):
    if index == len(items):
        return 1
    return count(items, index + 1) + count(items, index + 1)

print(count([1, 2, 3, 4], 0))
print(2 ** 4)

It prints

16
16

Usually you do not want the subsets — you want an answer about them

Printing a million lists is slow and useless. Carry the thing you actually care about down the recursion instead — a running total, a count, the best score so far — and return an answer rather than a pile of lists.

Python

def count(items, index, total):
    if index == len(items):
        return 1 if total == 10 else 0
    return count(items, index + 1, total) + count(items, index + 1, total + items[index])

print(count([2, 3, 5, 7], 0, 0))

It prints

2

The other shape of complete search

Subsets ask "which ones?". Some problems ask "in which order?" — visit these cities, do these jobs, seat these people.

Same pattern: choose the next one from whatever is left, and recurse.

Python

def orders(items, chosen):
    if len(chosen) == len(items):
        print(chosen)
        return
    for x in items:
        if x not in chosen:
            orders(items, chosen + [x])

orders([1, 2, 3], [])

It prints

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Orders grow much faster than subsets

The first choice has n options, the next has n - 1, and so on. That is n factorial, and it leaves 2 ** n standing.

Subsets are fine at 20. Orders are already hopeless at 15.

Python

import math

for n in [5, 10, 15, 20]:
    print(n, 2 ** n, math.factorial(n))

It prints

5 32 120
10 1024 3628800
15 32768 1307674368000
20 1048576 2432902008176640000

A real problem: the shortest round trip

Four towns, a table of distances, and a delivery van that starts at town 0, visits all of them and comes home. Which order is shortest?

With four towns there are only six orders to try, so try them all. The answer is 18.

Python

d = [
    [0, 5, 9, 4],
    [5, 0, 3, 8],
    [9, 3, 0, 6],
    [4, 8, 6, 0],
]

def best_tour(order):
    if len(order) == 3:
        length = 0
        here = 0
        for town in order:
            length += d[here][town]
            here = town
        return length + d[here][0]
    best = 1000
    for town in [1, 2, 3]:
        if town not in order:
            best = min(best, best_tour(order + [town]))
    return best

print(best_tour([]))

It prints

18

This is the travelling salesman, and it is genuinely hard

Nobody knows a fast way to do this for a thousand towns. Not "nobody has written it yet" — nobody knows whether one can exist.

Unit 7 will get it down to about a million steps for 20 towns using bits and memory, which is the best anyone has. For now, notice that a problem can be easy to state and hard for ever.

Most of a search is time wasted

A search that has already gone past the total it was looking for will never come back. Every branch below that point is guaranteed to fail.

Cutting a branch you can prove is hopeless is called pruning, and it is the difference between a search that finishes and one that does not.

One line, three times less work

Same search, same answer, counting the states it visits. Adding if total > target: return 0 takes it from 127 states to 41.

The counter is a one-item list because a plain number inside a function would be a fresh copy each time.

Python

items = [3, 34, 4, 12, 5, 2]
target = 9

def search(index, total, nodes, prune):
    nodes[0] += 1
    if prune and total > target:
        return 0
    if index == len(items):
        return 1 if total == target else 0
    return (search(index + 1, total, nodes, prune)
            + search(index + 1, total + items[index], nodes, prune))

plain = [0]
pruned = [0]
print(search(0, 0, plain, False), plain[0])
print(search(0, 0, pruned, True), pruned[0])

It prints

2 127
2 41

And the order you try things in matters

Sort the items biggest first and the search overshoots the target sooner, so it gives up sooner: 33 states instead of 41.

The answer is identical. Only the wasted work changed — and that is the only thing a contest is measuring.

Python

items = sorted([3, 34, 4, 12, 5, 2], reverse=True)
target = 9

def search(index, total, nodes):
    nodes[0] += 1
    if total > target:
        return 0
    if index == len(items):
        return 1 if total == target else 0
    return search(index + 1, total, nodes) + search(index + 1, total + items[index], nodes)

nodes = [0]
print(items)
print(search(0, 0, nodes), nodes[0])

It prints

[34, 12, 5, 4, 3, 2]
2 33

Pruning is only safe when it is provable

This prune works because every number is positive, so a total can only grow. Put one negative number in the list and it becomes wrong, silently, on some inputs only.

That is the rule: cut a branch only when you can say out loud why nothing down there could ever win.

The oldest search puzzle there is

Put eight queens on a chessboard so that no two can take each other. A queen covers her whole row, her whole column and both diagonals.

There are 4426165368 ways to drop eight queens on 64 squares. There are 92 answers. Complete search has to be cleverer than that.

One queen per row, by force

Two queens in the same row is instantly illegal, so stop generating those: put exactly one queen in each row and only choose her column.

That alone takes 4 billion placements down to 16 million — and pruning the columns and diagonals as you go takes it to a few thousand.

Two queens share a diagonal when their sums or differences match

A queen at row r, column c covers everything with the same r + c — one diagonal — and everything with the same r - c — the other.

That is the whole check, and it is why no board is needed: three lists of numbers already used are enough.

Python

for r in range(3):
    for c in range(3):
        print(r, c, r + c, r - c)

It prints

0 0 0 0
0 1 1 -1
0 2 2 -2
1 0 1 1
1 1 2 0
1 2 3 -1
2 0 2 2
2 1 3 1
2 2 4 0

The whole solver

Row by row. Skip a column that is taken, or on a diagonal that is taken. When the last row is placed, that is one answer.

Four queens on a 4 by 4 board: 2 answers. Six on a 6 by 6: 4 answers.

Python

def solve(n, row, cols, diag1, diag2):
    if row == n:
        return 1
    total = 0
    for col in range(n):
        if col in cols or row - col in diag1 or row + col in diag2:
            continue
        total += solve(n, row + 1, cols + [col], diag1 + [row - col], diag2 + [row + col])
    return total

for n in [4, 5, 6]:
    print(n, solve(n, 0, [], [], []))

It prints

4 2
5 10
6 4