Backtracking — Exhaustive Search, Done Right

A room of people all shake hands, each pair exactly once.

Write handshakes(people) that returns the list of all unique pairs as tuples. A pair should appear once: if ("A", "B") is in the list, ("B", "A") must not be.

handshakes(["A", "B", "C"])
# [("A", "B"), ("A", "C"), ("B", "C")]

Think: for n people, how many handshakes will there be? Test your formula with the last assertion.

Print all numbers of length n where each digit runs from 0 to m-1 — that is, all n-digit numbers in base m. (No itertools allowed — you are inventing it.)

First idea: a car odometer. To go from 199 to 200 the rightmost wheel rolls over to 0 and carries into the next wheel.

Write next_numb(arr, m) that treats the list arr as digits in base m and adds 1 in place. Return True if the increment succeeded, False if every digit was already maxed out.

Work it out by hand first: what happens when you add 1 to [0, 2, 2] in base 3? What about [2, 2, 2]? Where does the "carrying" start, and when does it stop?

a = [0, 1]
next_numb(a, 2)   # True, a is now [1, 0]

Write generate(n, m) that returns all n-digit base-m numbers as strings, in counting order. Start from [0, 0, ..., 0] and keep calling next_numb until it returns False, collecting each state as a string.

generate(2, 2)   # ["00", "01", "10", "11"]

Now the recursive view: an n-digit number is a first digit followed by an (n-1)-digit number.

Write generate_rec(n, m):

• Base case: n == 0 — there is exactly one number of length 0: the empty string "".
• Recursive case: for each digit d from 0 to m-1, prepend str(d) to every string in generate_rec(n - 1, m).

It must produce exactly the same list as generate.

Think: how many strings does generate_rec(n, m) return? You met this formula in the very first chapter (Learning to Count): d digits in base B represent B^d numbers. Enumeration and counting are the same tree — one walks it, one measures it.

Print all rearrangements of your name (assume all letters are distinct).

Write perms(s) returning the list of all permutations of the string s.

Approach: pick each character in turn to go first, then recurse on the string without that character:

perms("abc") = "a" + each of perms("bc")
             + "b" + each of perms("ac")
             + "c" + each of perms("ab")

Think: how many permutations does a string of length n have? (Your name has 7 distinct letters — expect 5040.)

How many permutations does a list of 4 distinct elements have?

A. 4

B. 16

C. 24

D. 256

Exhaustive search lives or dies by its checker — the little function that says "this state is fine" or "this state is broken". Before Sudoku, practice on brackets.

Write are_valid(s) for a string of (), [], {} characters. It is valid when every opener is closed by the matching closer, in the right order.

Hint: as you scan left to right, you need to remember which openers are still waiting for their closers. What data structure naturally handles "most recent first"?

are_valid("([{}])")   # True
are_valid("}{")       # False — closes before opening

The main event. A Sudoku board is a 9×9 grid; every row, every column, and every 3×3 block must contain the digits 1–9 exactly once. The puzzle gives you some digits (the clues); you fill the rest.

We represent the board as a list of 9 lists, with 0 meaning empty.

Write find_first_empty_space(board) that scans top-to-bottom, left-to-right and returns the (row, col) of the first 0. If the board has no empty cell, return (None, None) — that will be our signal that the puzzle is solved.

The checker. Write can_place(i, row, col, board) — may digit i legally go into cell (row, col)?

1. If i already appears anywhere in that row — False.
2. If i already appears anywhere in that column — False.
3. If i already appears in the cell's 3×3 block — False.
4. Otherwise True.

Now the backtracking itself. Write solve_sudoku(board) (it modifies the board in place and returns True/False).

You have find_first_empty_space and can_place. For each empty cell, you could try placing digits 1–9. If a placement leads to a dead end, what should you do? Think about the pattern from generate_rec and the * wildcard matcher.

A 9×9 Sudoku has 81 cells. If you tried every possible assignment of digits 1–9 to all empty cells (brute force without checking constraints), approximately how many combinations would that be for a puzzle with 50 empty cells?

A. 50 × 9 = 450

B. 9^50 — an astronomically large number

C. 50! (50 factorial)

D. 81 × 9 = 729

The puzzle has 51 empty cells. Blind enumeration would try up to 9⁵¹ ≈ 10⁴⁸ boards — the sun would burn out first. Your solver finishes in well under a second.

The difference is pruning: can_place kills a bad branch at its first wrong digit, so the enormous tree of possibilities almost entirely never gets built. Enumeration provides completeness; checking provides the speed.