Backtracking, discovered — the Sudoku solver

1 · The problemThe puzzle and its three rules

A nine-by-nine grid. Some cells already hold a digit; the rest are empty. Your job is to fill every empty cell with a digit from 1 to 9 so that three rules hold at once: each digit appears once in its row, once in its column, and once in its three-by-three box.

The rules are what make a digit wrong. Put a 3 in the fourth cell of the top row and it clashes with the 3 already in that row. The rules reject it before you have gone any further — remember that, because it is the only thing the computer will ever "know" about the puzzle.

A person solving this looks for cells where only one digit can go. A computer could do that too, but we are after something more general: a way to solve a puzzle when there is no clever next step, only choices.

2 · The obvious ideaMake a choice, keep going

Start at the first empty cell: the third one in the top row. Which digits are not ruled out? The row already has 5, 3 and 7; the column has an 8; the box has 5, 3, 6, 9 and 8. What is left is 1, 2 or 4.

We don't know which one is right. So take the first that fits: 1. Then move on to the next empty cell and do the same thing. Just make a choice… and keep going.

It goes well. The next empty cell takes a 2, the one after it a 4, the one after that a 9. Four cells filled, no rule broken. It feels like it is working.

3 · The failureNothing fits

Then the next empty cell. Try 1: the row has one. 2, 3, 4, 5: all in the row already. 6: in the column. 7: the row. 8: the column. 9: the row. Every digit from 1 to 9 is ruled out. The tray is empty.

This is the moment the obvious idea breaks, and it breaks in an interesting way. Nothing is wrong with this cell. Every digit we placed was legal when we placed it. And yet here we are, with an empty cell that cannot be filled. The contradiction is real, but its cause is somewhere behind us.

4 · The observationWhich choice was wrong?

Wait. The problem is not necessarily the last thing we did. One of the earlier choices was wrong — and we have no idea which. The 9? The 4? The 2? The 1 at the very start?

We cannot tell from here. So do the only honest thing: go back. Undo the 9. Is there another digit for that cell? If not, undo the 4. And so on — back to a choice where something else can still be tried.

In the story he walks all the way back to the first empty cell, where 2 and 4 are still untried, and crosses out the 1. The 1 was not illegal; it just led nowhere. That is the key distinction of this whole technique: a choice can be allowed and still be wrong, and the only way to find out is to follow it until it either works or breaks.

5 · The second attemptTry another — and fail again

With a 2 in the first cell the next cell has only one digit left, a 6, so that one is forced. Then a 4, an 8, a 1 — and the last cell of the row has nothing left. Wrong again. A different dead end, one cell further along.

So back again, cross out the 2, and try the 4. This time: 6, 8, 9, 1, and a 2 in the last cell, the only digit that fits. The top row is complete, and every rule holds.

Notice what we never did: we never knew the right digit in advance, and we never needed to. We needed a way to recover from the wrong one.

6 · The discoveryYou are exploring a path

Step back and look at what the attempts form. The first cell had three choices; each of those led to a different set of choices in the next cell, and so on. Every choice opens up more possibilities, and every possibility is itself a choice. The attempts are not guesses — they are paths through a tree.

Seen like this, "go back" has a precise meaning: when a path breaks, return to the last fork where an untried branch remains, and take it. You are not guessing once. You are exploring a tree, one path at a time, and pruning the paths that break.

7 · The nameThis is backtracking

Only now does the technique deserve its name. Backtracking: build a solution one choice at a time; whenever the partial solution can no longer be completed, step back to the most recent choice and change it. The name is literal. When the track ends, you track back.

The whole loop fits on one hand:

1. Choose

   Pick the next decision to make — here, the next empty cell.

2. Try

   Take the first option the rules still allow, and make it real on the board.

3. Keep going

   Move to the next decision as if the choice were right. If there are no decisions left, you are done.

4. If it fails, undo

   A dead end means some choice behind you was wrong. Take the most recent one back.

5. Try the next option

   At that same decision, the next allowed option. If there is none, undo one more.

8 · The distinctionNot starting over

Backtracking does not mean wiping the board and beginning again. When the 2-path broke at the end of the row, only the choices that depended on the 2 were undone — the 6, the 4, the 8, the 1. The thirty given digits never moved, and neither would any cell filled before the bad choice. You only undo the choices that depend on the wrong decision.

9 · The codeTranslate what we did into Python

The board is a nine-by-nine list of lists of characters: a digit, or '.' for an empty cell. The board itself is the whole state — there is no separate record of the path, because the path is the digits currently on the board.

Build the solver from the loop above, one piece at a time.

Find an empty cell

Scan row by row, cell by cell. A cell that already holds a digit is skipped. The first empty cell found is the decision to make now.

    def solve():        for r in range(9):            for c in range(9):                if board[r][c] != '.':                    continue

Try every digit

For that cell, go through the digits 1 to 9 in order. A digit that breaks a rule is skipped before anything else happens — this is the tray with some digits missing.

                for num in "123456789":                    if not valid(r, c, num):                        continue

What makes a digit valid?

Three loops, one per rule: the row, the column, the three-by-three box. The box's top-left corner is found by rounding the row and column down to a multiple of three.

    def valid(r, c, num):        for j in range(9):            if board[r][j] == num:                return False         for i in range(9):            if board[i][c] == num:                return False         box_r = (r // 3) * 3        box_c = (c // 3) * 3         for i in range(box_r, box_r + 3):            for j in range(box_c, box_c + 3):                if board[i][j] == num:                    return False         return True

Place it, go deeper, and if that fails, undo

This is where the story becomes recursion. Put the digit on the board, then call solve() again to fill the rest. If that call comes back True, the rest got filled and we are done — pass the True upward. If it comes back False, every path through this digit broke somewhere ahead, so take the digit back off the board and let the loop try the next one.

                    board[r][c] = num                     if solve():                        return True                     board[r][c] = '.'

Line 36 is the single most important line in the file: board[r][c] = '.'. It is the digit lifted off the board. Without it, the board would still show the wrong digit when the loop tried the next one, and the "walk back" would never happen.

No digit works

If the loop finishes without any digit leading to a solution, this cell cannot be filled with the board as it stands — someone before us chose wrongly. Say so: return False. And if the scan never found an empty cell at all, the board is full and every rule held along the way: return True.

                return False         return True

The whole thing

def solve_sudoku(board):    def valid(r, c, num):        for j in range(9):            if board[r][j] == num:                return False         for i in range(9):            if board[i][c] == num:                return False         box_r = (r // 3) * 3        box_c = (c // 3) * 3         for i in range(box_r, box_r + 3):            for j in range(box_c, box_c + 3):                if board[i][j] == num:                    return False         return True     def solve():        for r in range(9):            for c in range(9):                if board[r][c] != '.':                    continue                 for num in "123456789":                    if not valid(r, c, num):                        continue                     board[r][c] = num                     if solve():                        return True                     board[r][c] = '.'                 return False         return True     solve()

Every line is something that happened on the board. The table the video ends on says the same thing twice:

In the story	In the code
Find an empty cell	if board[r][c] != '.': continue
Try a choice	for num in "123456789":
Check if it is possible	valid(r, c, num)
Make the choice	board[r][c] = num
Keep going	solve()
It worked	if solve(): return True
It failed	solve() returned False
Undo	board[r][c] = '.'
Try another	the next turn of the for num loop
No choice works	return False
Everything solved	return True

10 · The programming insightWho walks back? The call stack

In the story, the walk back is a thing he does: a step at a time, lifting a digit at each post. In the code there is no "walk back" anywhere. So who does it?

Python does. Every solve() call that places a digit calls solve() again for the rest of the board, which calls solve() again, and so on — a stack of calls, one per placed digit. When the deepest call returns False, control goes back to the call before it, which is still standing on its own line 34 with its own r, c and num. That call lifts its digit on line 36 and tries the next one. If it runs out, it returns False too, and control steps back once more.

So failure travels backwards through the stack on its own, one level per False, until it reaches a call that still has digits to try. The recursion is not a trick to make the code short. It is the data structure that remembers where every fork was and what has been tried at each — for free.

11 · The costWhat it costs

Up to nine choices at each of the empty cells, one after another: in the worst case the tree has 9 × 9 × 9 … paths, one factor per empty cell — 9^E for E empty cells. Our board has 51, and 9⁵¹ is a number with 49 digits. Nothing can explore that.

Nothing has to. Every valid() that says no cuts off a whole branch before a single step is taken down it. On this board the program places a digit 4,208 times in total — wrong placements included — and arrives at the solution.

That is the lesson about cost, and it is the same lesson as the technique: backtracking becomes practical exactly to the degree that you can reject bad paths early. Sudoku is generous here — three rules, each a cheap check. A problem with weaker rules prunes less and costs more.

12 · Watch it runThe program, live

13 · The lessonTwo questions for any problem like this

The important part of this problem is not the Sudoku, and not the recursion. It is realizing that you can make progress on a problem whose right answer you cannot see, as long as you can recognize a wrong one and take it back. Don't start by writing code. Answer two things first:

1. What are my choices?

   At each step, what are the options I could take? Here: a digit from 1 to 9 for the current empty cell. In another problem: a letter for a position, a queen for a column, a coin for a slot.

2. What makes a choice impossible?

   The rule that lets me reject an option early, before exploring it. Here: a repeat in the row, the column or the box. The stronger this rule, the smaller the tree you actually walk.

Answer those and the code is the loop from section 7 with your answers filled in: choose, try, go deeper, undo, next. If you can also say when you are done — here, no empty cell left — you have everything.

14 · PracticeFour problems, same shape

None of these mention a board. For each, write down your choices and your rejection rule before touching the keyboard.

• Warm-upPermutations

  Given a few distinct numbers, list every possible order of them. The choice is "which unused number comes next"; the rejection rule is "already used". No dead ends here — every path reaches the end — which makes it the cleanest place to feel the undo.

• PracticeThe Sudoku solver, from scratch

  Close this page and write valid and solve yourself. Then count the placements on this board; you should get 4,208. If you get a different number, your loop visits cells in a different order — find out why.

• VariationWord search

  A grid of letters and a word: can the word be spelled by a path of neighbouring cells, each used once? The choice is "which neighbour next"; the rejection rule is "wrong letter, or already on the path". Same undo, different board.

• ChallengeN queens

  Place N queens on an N-by-N chessboard so that none attacks another. Decide what one "choice" is (a whole column makes it easy), what a clash is, and how early you can detect one. Then count your dead ends.

Make a choice. If it fails, go back. Try again. Don't fear the wrong path.