Smarter backtracking — the Sudoku solver, part 2

1 · RecapWhere part 1 left us

In part 1 we built a solver out of one honest move: make a choice, keep going, and when a square has nothing left, go back to the last choice that can still change. The program found the first empty square, tried the digits 1 to 9 in order, and let the call stack walk back from every dead end.

It works. On our board it fills all 51 empty squares correctly. But to get there it placed a digit 4,208 times — about eighty placements per square, almost all of them wrong guesses that were later undone.

Part 1 ended on a question: the program always picks the first empty square. What if it picked a better one?

2 · The diagnosisWhere the 4,208 went

Go back to the very first decision part 1's solver made. The first empty square in reading order is the third cell of the top row, and three digits fit there: 1, 2 or 4. The solver had no way to know which, so it tried 1 — and then spent 333 placements exploring everything that follows from a 1 before giving up on it, then 2,207 placements in total before it got to the 4.

Nothing was wrong with backtracking. What was wrong was where it chose to guess. It picked a square with three options when the board had squares with fewer. Every extra option at an early square multiplies the work behind it.

3 · The observationLook at the empty squares

Instead of blindly picking the next empty square, look at all of them. For each one, count how many digits are still possible — the ones its row, column and box don't already use.

The counts on our board, before anything is placed:

Digits that still fit	1	2	3	4	5	6
Empty squares	4	13	17	14	2	1

Part 1's solver started at a square with 3. But four squares have only one possible digit. There is nothing to guess there at all.

4 · The ideaThe most constrained square

Read three squares. The last one in the top row could be 2, 4 or 8. The first one in the third row, 1 or 2. And the last one in the seventh row… only 4.

A square with only one possible digit tells us something for certain. The more limited a square is, the more information it gives. So put the 4 in, and watch what it does to the squares around it: a neighbour that had two options now has one.

That is the whole idea, and it has a name: pick the most constrained square first — the empty square with the fewest possible digits. When that number is 1, there is no guess at all. When it is 2, you are guessing between two, not nine.

5 · The bonusFail sooner

The rule has a second payoff, and it is the one that matters when guessing is unavoidable. Suppose a guess was wrong. Part 1's solver placed 1, 2 and 4 at the start of the top row. At that moment, look at the sixth square of the third row: nothing fits there any more. The board is already dead.

Part 1's solver doesn't look. It carries on filling the top row, places two more digits, and only notices when it reaches the end of the row. The smart search counts every empty square before each decision, so a square with zero choices is the first thing it sees. It stops right there and goes back.

6 · The second improvementStop rescanning: remember

Counting the options of every empty square, before every decision, sounds expensive. In part 1, checking one digit meant walking along its row, its column and its box. Doing that for 9 digits in each of dozens of squares, at every step, is a lot of scanning for information we already had.

Why keep searching for information we already know? Keep it instead. Three lists of nine sets: one set of used digits per row, per column, per box. When a digit goes on the board, add it to its three sets; when it comes off, remove it.

Now, to ask "does 4 fit here?", look in three sets — three instant lookups instead of three scans. And the full list of options for a square is one subtraction: all nine digits, minus the three sets.

7 · Put it togetherThe new loop

Line the new loop up against part 1's. Only the first step changed:

1. Find the most constrained empty square

   The one with the fewest possible digits. If one has none, this board is dead: go back now. If there is no empty square, the puzzle is solved.

2. Try one of its digits

   Only the digits its row, column and box allow — already known from the three sets.

3. Go deeper

   Place it, update the three sets, and solve the rest.

4. If it fails, undo

   Take the digit off the board and out of its three sets — exactly part 1's undo, plus the bookkeeping.

5. Try another

   The next of that square's digits. If there is none, report failure to the call before.

8 · The codeThe code, piece by piece

Same board format as part 1: a nine-by-nine list of characters, '.' for empty. Line numbers refer to the whole program in the next section.

Memory first: three lists of sets

One empty set for each row, each column and each box.

    rows = [set() for _ in range(9)]    cols = [set() for _ in range(9)]    boxes = [set() for _ in range(9)]

Fill them from the given digits

Before solving, every digit already on the board goes into its row's, its column's and its box's set. Line 10 is the little formula that numbers the boxes 0 to 8, left to right, top to bottom.

    for r in range(9):        for c in range(9):            if board[r][c] != '.':                num = board[r][c]                box = (r // 3) * 3 + c // 3                rows[r].add(num)                cols[c].add(num)                boxes[box].add(num)

Look at every empty square

Inside solve(), scan the board. Filled squares are skipped. For each empty one, its options are all nine digits minus what its row, column and box already use.

        for r in range(9):            for c in range(9):                if board[r][c] != '.':                    continue                 box = (r // 3) * 3 + c // 3                choices = (                    set("123456789")                    - rows[r]                    - cols[c]                    - boxes[box]                )

A square with no options: stop at once

The "fail sooner" rule is two lines. If any empty square has nothing left, this whole board is dead — return False immediately, without trying anything.

                if not choices:                    return False

Keep the smallest

Remember the square with the fewest options seen so far. If a square has exactly one, nothing can beat it: stop looking (the second break leaves the outer loop too).

                if best_choices is None or len(choices) < len(best_choices):                    best = (r, c, box)                    best_choices = choices                    if len(best_choices) == 1:                        break             if best_choices is not None and len(best_choices) == 1:                break

Solved, or branch

If the scan found no empty square at all, the board is full: done. Otherwise, try that square's digits, in sorted order so the run is the same every time — a Python set has no fixed order.

        if best is None:            return True         r, c, box = best        for num in sorted(best_choices):

Place, go deeper, undo — part 1, plus the sets

This block is part 1's heart with three extra lines on each side: the digit goes into its three sets when it is placed, and comes out of them when it is undone.

            board[r][c] = num            rows[r].add(num)            cols[c].add(num)            boxes[box].add(num)             if solve():                return True             board[r][c] = '.'            rows[r].remove(num)            cols[c].remove(num)            boxes[box].remove(num)         return False

Lines 49, 54 and 57 are the same three lines that carried part 1 — make the choice, go deeper, undo. Everything new is either bookkeeping (the sets) or the one new decision (which square).

9 · The whole programAll 64 lines

def solve_sudoku(board):    rows = [set() for _ in range(9)]    cols = [set() for _ in range(9)]    boxes = [set() for _ in range(9)]     for r in range(9):        for c in range(9):            if board[r][c] != '.':                num = board[r][c]                box = (r // 3) * 3 + c // 3                rows[r].add(num)                cols[c].add(num)                boxes[box].add(num)     def solve():        best = None        best_choices = None         for r in range(9):            for c in range(9):                if board[r][c] != '.':                    continue                 box = (r // 3) * 3 + c // 3                choices = (                    set("123456789")                    - rows[r]                    - cols[c]                    - boxes[box]                )                 if not choices:                    return False                 if best_choices is None or len(choices) < len(best_choices):                    best = (r, c, box)                    best_choices = choices                    if len(best_choices) == 1:                        break             if best_choices is not None and len(best_choices) == 1:                break         if best is None:            return True         r, c, box = best        for num in sorted(best_choices):            board[r][c] = num            rows[r].add(num)            cols[c].add(num)            boxes[box].add(num)             if solve():                return True             board[r][c] = '.'            rows[r].remove(num)            cols[c].remove(num)            boxes[box].remove(num)         return False     solve()

The five lines that tell the story, if you read only five:

The idea	The line
Find the most constrained cell	37 · best_choices = choices
Make a choice	49 · board[r][c] = num
Go deeper	54 · if solve():
If it fails, undo it	57 · board[r][c] = '.'
Try the next choice	48 · for num in sorted(best_choices):

10 · The payoffThe real run: 51

Run it on the same board. It finds the tightest square, places the only digit that fits, and moves on. Square by square. No guessing.

Every one of its 51 placements goes into a square with exactly one possible digit. Each forced digit lowers the counts around it until the next square is forced too. On this board the smart search never guesses, and never has to go back.

11 · Try itRace them

12 · Honest accountingWhat changed, and what didn't

• The worst case did not change. A puzzle designed against this rule can still force real guesses at every step; backtracking with any search order is exponential in the worst case. What changed is how much of the tree this board makes us walk: 51 placements instead of 4,208.
• Each step now costs more thinking. Before every placement, the smart search looks at every empty square and subtracts three sets for each. Part 1 looked at one square. That trade is overwhelmingly worth it here: a few dozen set subtractions per step against thousands of wrong placements.
• The sets cost almost nothing to keep. Three lists of nine small sets, updated with one add and one remove per placement. Beyond the board, memory is constant: 27 sets and a recursion at most 81 calls deep.
• 51 is this board, not a law. Puzzles rated "hard" are hard precisely because forced squares run out and a real guess is needed. Then the smart search guesses — between two digits, at the tightest square — and backtracks exactly like part 1 when it is wrong.

13 · The lessonChoose smart, go deeper, go back

The trick was never simply "try every possibility". It was knowing when to stop — a square with zero options ends the branch at once — and knowing which possibility to try first — the square where you have the least freedom. Backtracking gives you the ability to go back. Smart choices keep you from going everywhere.

Part 1 gave you two questions to ask before writing any search. This part adds a third:

1. What are my choices?

   From part 1. Here: a digit for an empty square.

2. What makes a choice impossible?

   From part 1. Here: a digit already in the row, the column or the box.

3. Which decision should I make next?

   New. Usually: the one with the fewest options left. It forces the easy moves, and it exposes the dead ends earliest.

14 · PracticeFour problems, same shape

• Warm-upCount your own badges

  On the board above, before anything is placed, find the four squares with one possible digit by hand. Then place them and find the squares they force. How far do you get before a real guess is needed? (On this board: all the way.)

• PracticeThe smart solver, from scratch

  Write it from part 1's solver by changing only the cell-picking and adding the sets. Count placements: you should get 51 on this board. Then remove the if not choices: return False lines and count again.

• VariationWord search, with a better start

  Can a word be spelled by a path of neighbouring cells? Part 1's practice. Now ask: which letter of the word should the search start from? Hint: the rarest one on the board is the most constrained.

• ChallengeN queens, fewest columns first

  Place N queens so none attacks another, one per row — but each time, fill the row with the fewest safe squares left. Count the dead ends against the plain row-by-row order for N = 8, 12, 20.

Choose smart. Go deeper. Go back.