How Is a Sudoku Solved in a Blink?: Computing Further 9–12

Try it

Rows and columns are numbered from 0 to 8 on this page, top to bottom and left to right, the way Python counts. Start with an easy puzzle and go slowly.

Press Step a few times, then Play. Tap an empty square (when it isn’t playing) to see which digits could go there.

Next square:

Tries: 0
Undos: 0
Guesses: 0
Search time: –

Press Step to place one digit, or Play. Tap an empty square to see what fits there.

Watch what the solver does, and what the sentence under the board says.

It always fills the first empty square, reading along the rows like a book.
In each square it puts the smallest digit that fits: one not already in that square’s row, column or box.
Sometimes it reaches a square where nothing fits. Then it takes back the digit it put in last (an undo, the square flashes red) and tries that square’s next digit. If that square has no digits left either, it takes back the one before, and so on.
When it puts a digit in a square that had two or more choices, the board counts a guess.

Which square next?

The easy puzzle took 2,428 tries and 586 guesses, although it is easy. A person solving it would never guess: they would look for a square where only one digit fits. The solver could do that too. Instead of the first empty square, it could choose the square with the fewest digits allowed.

Next square: Fewest choices is chosen. Press Play, then compare it with In order on each puzzle.

Puzzle:

Next square:

Tries: 0
Undos: 0
Guesses: 0
Search time: –

Press Step to place one digit, or Play. Tap an empty square to see what fits there.

On the easy puzzle, choosing the square with the fewest choices first, how many guesses did the solver make?

Pick an answer to see why.

How it works: try, and take it back

The solver’s method has a name: backtracking. Choose a square, try a digit that fits, and go on to the next square as if that digit were right. If you are stuck later, come back (backtrack) and try the next digit. Because it only ever takes back its most recent choice, and goes through each square’s digits in order, it never tries the same thing twice and never misses a possibility: if the puzzle has a solution, it finds it.

The easiest way to write this is a function that calls itself. solve(grid) finds an empty square and, for each digit that fits there, calls solve on the grid with that digit put in. That call does the same for the next square, and so on. A call that finds no empty square has solved the puzzle and gives back True, and each call above it gives back True too. A call whose square has no digit left that works gives back False, and the call that made it tries its next digit. A function that calls itself is recursive.

Here is a small Sudoku to watch, 4 × 4 with 2 × 2 boxes and digits 1 to 4. The top two rows are full. The six empty squares are numbered as the program numbers them, 0 to 15 along the rows.

Figure 5.1 A 4 × 4 Sudoku: each row, column and 2 × 2 box must hold 1, 2, 3 and 4. Squares 8 to 13 are empty.

The program keeps the grid as one string of 16 characters, with . for an empty square. Step through its calls: each circle is one call of solve, with the digit it has just put in; ✓ or ✗ under it is what that call gave back.

Press Next to see each call made and each answer come back.

Step 1 / 25

The puzzle: the top two rows are full (3 1 2 4 and 4 2 1 3), so the boxes show only the bottom two; · is an empty square. solve finds the first empty square, square 8, and tries the digits 1 to 4 there, calling itself on each new grid.

Calls made: 1
Open now: 1
Most open at once: 1

Open calls, newest on top

gives back ✓waiting for solve(…1··· ··42)waiting for solve(…2··· ··42)gives back ✗waiting for solve(…13·· ··42)waiting for solve(…14·· ··42)waiting for solve(…143· ··42)waiting for solve(…23·· ··42)waiting for solve(…24·· ··42)waiting for solve(…243· ··42)waiting for solve(…2431 ··42)waiting for solve(…2431 1·42)waiting for solve(…2431 1342)running

solve(…···· ··42)

gives back ✓waiting for solve(…1··· ··42)waiting for solve(…2··· ··42)gives back ✗waiting for solve(…13·· ··42)waiting for solve(…14·· ··42)waiting for solve(…143· ··42)waiting for solve(…23·· ··42)waiting for solve(…24·· ··42)waiting for solve(…243· ··42)waiting for solve(…2431 ··42)waiting for solve(…2431 1·42)waiting for solve(…2431 1342)running

def fits(grid, i, d):    r, c = i // 4, i % 4    for k in range(4):        if grid[r * 4 + k] == d or grid[k * 4 + c] == d:            return False    br, bc = r // 2 * 2, c // 2 * 2    for a in range(2):        for b in range(2):            if grid[(br + a) * 4 + bc + b] == d:                return False    return True def solve(grid):    i = grid.find('.')    if i == -1:        print(grid)        return True    for d in '1234':        if fits(grid, i, d):            if solve(grid[:i] + d + grid[i + 1:]):                return True    return False solve('3124'    # the four rows, one after another      '4213'      '....'      '..42')

Output

In the tree, the first digit tried was 1 in square 8, and everything under it failed. What did that ✗ tell the program?

Pick an answer to see why.

Program it

You will build the solver in three steps, each running here on the page. A grid is a list of 9 rows, each a list of 9 numbers, with 0 for an empty square: grid[r][c] is the square in row r, column c.

Step 1: which digits fit?

allowed(grid, r, c) collects the digits already in the square’s row, column and box in a set, and gives back the digits from 1 to 9 that aren’t in it. The box starts at the row and column r // 3 * 3 and c // 3 * 3: for r = 5, that is row 3, the top of the middle band.

puzzle = ["...76....",          ".......63",          "1...2579.",          "...9..87.",          ".2..4..1.",          ".81..3...",          ".7619...8",          "51.......",          "....74..."] def read(rows):    return [[0 if ch == '.' else int(ch) for ch in row] for row in rows] def allowed(grid, r, c):    used = set(grid[r])                 # the digits in its row    for i in range(9):        used.add(grid[i][c])            # ... in its column    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])        # ... in its box    return [d for d in range(1, 10) if d not in used] grid = read(puzzle)print(allowed(grid, 0, 0))print(allowed(grid, 2, 8))

Output

[2, 3, 4, 8, 9][4]

The top-left square has five choices; row 2, column 8 has only one, 4. (Tap those squares on the board above to check.)

Step 2: a backtracking solver

choose_square gives back the first empty square, or None when there is none. solve is the tree’s solve, for a 9 × 9 grid of lists: put a digit in, call itself, and if that fails, put the 0 back. It counts every digit it puts in, in tries, a global variable (one outside the function, which global tries lets it change).

puzzles = {    'easy':        ["...76....", ".......63", "1...2579.", "...9..87.", ".2..4..1.",                    ".81..3...", ".7619...8", "51.......", "....74..."],    'Inkala 2010': ["..53.....", "8......2.", ".7..1.5..", "4....53..", ".1..7...6",                    "..32...8.", ".6.5....9", "..4....3.", ".....97.."],} def read(rows):    return [[0 if ch == '.' else int(ch) for ch in row] for row in rows] def allowed(grid, r, c):    used = set(grid[r])    for i in range(9):        used.add(grid[i][c])    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])    return [d for d in range(1, 10) if d not in used] def choose_square(grid):    for r in range(9):        for c in range(9):            if grid[r][c] == 0:                return (r, c)    return None tries = 0 def solve(grid):    global tries    square = choose_square(grid)    if square is None:        return True                     # no empty square: solved    r, c = square    for d in allowed(grid, r, c):        grid[r][c] = d        tries = tries + 1        if solve(grid):            return True        grid[r][c] = 0                  # it failed: take it back    return False for name, rows in puzzles.items():    tries = 0    grid = read(rows)    solve(grid)    print(f'{name}: {tries} tries')    print(''.join(str(d) for d in grid[0]), '(the top row)')

Output

easy: 2428 tries243769581 (the top row)Inkala 2010: 10007 tries145327698 (the top row)

The same counts as the board: 2,428 tries on the easy puzzle and 10,007 on Inkala’s. Your program and the board use exactly the same method.

Step 3: the fewest choices first

Now the one change. choose_square looks at every empty square and gives back the one with the fewest digits allowed (the first one, if several tie). Nothing else changes.

puzzles = {    'easy':        ["...76....", ".......63", "1...2579.", "...9..87.", ".2..4..1.",                    ".81..3...", ".7619...8", "51.......", "....74..."],    'Inkala 2010': ["..53.....", "8......2.", ".7..1.5..", "4....53..", ".1..7...6",                    "..32...8.", ".6.5....9", "..4....3.", ".....97.."],} def read(rows):    return [[0 if ch == '.' else int(ch) for ch in row] for row in rows] def allowed(grid, r, c):    used = set(grid[r])    for i in range(9):        used.add(grid[i][c])    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])    return [d for d in range(1, 10) if d not in used] def choose_square(grid):    best = None    fewest = 10    for r in range(9):        for c in range(9):            if grid[r][c] == 0:                n = len(allowed(grid, r, c))                if n < fewest:                    best = (r, c)                    fewest = n    return best tries = 0 def solve(grid):    global tries    square = choose_square(grid)    if square is None:        return True    r, c = square    for d in allowed(grid, r, c):        grid[r][c] = d        tries = tries + 1        if solve(grid):            return True        grid[r][c] = 0    return False for name, rows in puzzles.items():    tries = 0    grid = read(rows)    solve(grid)    print(f'{name}: {tries} tries')

Output

easy: 54 triesInkala 2010: 542 tries

From 2,428 to 54, and from 10,007 to 542. Choosing each square takes more work (it counts the choices in every empty square), so each try is slower; but there are so many fewer tries that the whole search still finishes sooner, and on the harder puzzles below, far sooner.

The board below runs your choose_square: the one in the program just above, as you have it (press Edit there to change it). The page does the rest of the search exactly as solve does, and draws every step.

Your code uses your function. Try it on 17 clues, then press In order and To the end on the same puzzle, and wait for the count: a few seconds, or up to ten on a phone (↺ stops it).

Puzzle:

Next square:

Tries: 0
Undos: 0
Guesses: 0
Search time: –

Press Step to place one digit, or Play. Tap an empty square to see what fits there.

What your choose_square prints, and any error, appears here.

On the 17-clue puzzle, the in-order solver made 9,727,396 tries. About how many times more than yours?

Pick an answer to see why.

What your program shows

This program solves all four puzzles with your Step 3 solver and counts its guesses too: the squares it chose that had two or more digits allowed.

puzzles = {    'easy':        ["...76....", ".......63", "1...2579.", "...9..87.", ".2..4..1.",                    ".81..3...", ".7619...8", "51.......", "....74..."],    'Inkala 2010': ["..53.....", "8......2.", ".7..1.5..", "4....53..", ".1..7...6",                    "..32...8.", ".6.5....9", "..4....3.", ".....97.."],    'Inkala 2006': ["85...24..", "72......9", "..4......", "...1.7..2", "3.5...9..",                    ".4.......", "....8..7.", ".17......", "....36.4."],    '17 clues':    ["4.....8.5", ".3.......", "...7.....", ".2.....6.", "....8.4..",                    "....1....", "...6.3.7.", "5..2.....", "1.4......"],} def read(rows):    return [[0 if ch == '.' else int(ch) for ch in row] for row in rows] def allowed(grid, r, c):    used = set(grid[r])    for i in range(9):        used.add(grid[i][c])    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])    return [d for d in range(1, 10) if d not in used] def choose_square(grid):    best = None    fewest = 10    for r in range(9):        for c in range(9):            if grid[r][c] == 0:                n = len(allowed(grid, r, c))                if n < fewest:                    best = (r, c)                    fewest = n    return best tries = 0guesses = 0 def solve(grid):    global tries, guesses    square = choose_square(grid)    if square is None:        return True    r, c = square    digits = allowed(grid, r, c)    if len(digits) > 1:        guesses = guesses + 1    for d in digits:        grid[r][c] = d        tries = tries + 1        if solve(grid):            return True        grid[r][c] = 0    return False for name, rows in puzzles.items():    tries = 0    guesses = 0    grid = read(rows)    clues = sum(1 for row in grid for d in row if d)    solve(grid)    print(f'{name:12} {clues} clues, {tries:5} tries, {guesses:3} guesses')

Output

easy         27 clues,    54 tries,   0 guessesInkala 2010  23 clues,   542 tries,  28 guessesInkala 2006  22 clues,  4036 tries, 370 guesses17 clues     17 clues,   481 tries,  68 guesses

Your program, with the board’s counts in order beside it, has found three things.

a.Every puzzle falls. Even Inkala’s 2006 puzzle, which he called “the most difficult sudoku-puzzle known so far”, took your solver 4,036 tries: on a laptop a quarter of a second of plain Python, on the board a few thousandths. A person can spend hours on it; the program never gets tired of trying.
b.The order of the search matters more than its speed. The same tries and undos, in a better order, cut the work from 9,727,396 tries to 481 on the 17-clue puzzle. A computer a thousand times faster wouldn’t do as much.
c.The hard puzzles are the ones that need guesses. The easy puzzle never needs one: some square always has exactly one digit left. Inkala’s puzzles make even the best-ordered search guess dozens or hundreds of times (28 and 370), and a person can’t guess and rub out that often. That is what makes them hard for people: no square is forced, and you must think several moves ahead.

Watch the grid fill

This program records the grid after every fourth try while it solves Inkala 2010, and shows them as pictures, one square for each square of the grid and a color for each digit, the clues darker. pixels is this page’s own module for showing pictures from Python.

from pixels import show_frames rows = ["..53.....", "8......2.", ".7..1.5..", "4....53..", ".1..7...6",        "..32...8.", ".6.5....9", "..4....3.", ".....97.."] def read(rows):    return [[0 if ch == '.' else int(ch) for ch in row] for row in rows] def allowed(grid, r, c):    used = set(grid[r])    for i in range(9):        used.add(grid[i][c])    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])    return [d for d in range(1, 10) if d not in used] def choose_square(grid):    best = None    fewest = 10    for r in range(9):        for c in range(9):            if grid[r][c] == 0:                n = len(allowed(grid, r, c))                if n < fewest:                    best = (r, c)                    fewest = n    return best COLORS = ['white', '#d95f5f', '#e08d3c', '#d9b43c', '#7fb04a', '#3f9e7c',          '#3f8fc0', '#5a6fc8', '#9a62c0', '#c85f9a']palette = {d: COLORS[d] for d in range(10)}for d in range(1, 10):                  # a clue: the same color, darker    palette[10 + d] = tuple(int(COLORS[d][k:k + 2], 16) * 6 // 10 for k in (1, 3, 5)) clue = read(rows)frames = []tries = 0 def picture(grid):    return [[grid[r][c] + (10 if clue[r][c] else 0) for c in range(9)] for r in range(9)] def solve(grid):    global tries    square = choose_square(grid)    if square is None:        return True    r, c = square    for d in allowed(grid, r, c):        grid[r][c] = d        tries = tries + 1        if tries % 4 == 0:            frames.append(picture(grid))        if solve(grid):            return True        grid[r][c] = 0    return False grid = read(rows)solve(grid)frames.append(picture(grid))print(tries, 'tries,', len(frames), 'pictures')show_frames(frames, palette)

Output

542 tries, 136 pictures

Picture

Inkala 2010 solved: every row, column and 3 × 3 box holds all nine colors, the 23 clues darker. — The last of its 136 steps: press Run to play them all.

Play it. The colors creep in, vanish in a flash when a guess goes wrong, and creep in again. In the last picture every row and column has all nine colors.

Sixteen clues are never enough

The 17-clue puzzle has only one solution. Take one clue away, and it has more than one. This program takes away the 6 in row 3, column 7, searches for solutions, stops when it has found 2, and prints the squares where those two differ.

rows = ["4.....8.5", ".3.......", "...7.....", ".2.....6.", "....8.4..",        "....1....", "...6.3.7.", "5..2.....", "1.4......"] def read(rows):    return [[0 if ch == '.' else int(ch) for ch in row] for row in rows] def allowed(grid, r, c):    used = set(grid[r])    for i in range(9):        used.add(grid[i][c])    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])    return [d for d in range(1, 10) if d not in used] def choose_square(grid):    best = None    fewest = 10    for r in range(9):        for c in range(9):            if grid[r][c] == 0:                n = len(allowed(grid, r, c))                if n < fewest:                    best = (r, c)                    fewest = n    return best found = [] def search(grid):    square = choose_square(grid)    if square is None:        found.append([row[:] for row in grid])   # a copy: the search goes on        return    r, c = square    for d in allowed(grid, r, c):        grid[r][c] = d        search(grid)        grid[r][c] = 0        if len(found) == 2:            return grid = read(rows)grid[3][7] = 0                          # take away one cluesearch(grid)print(len(found), 'solutions')a, b = foundfor r in range(9):    for c in range(9):        if a[r][c] != b[r][c]:            print(f'row {r}, column {c}: {a[r][c]} or {b[r][c]}')

Output

2 solutionsrow 5, column 6: 3 or 6row 5, column 8: 6 or 3row 8, column 6: 6 or 3row 8, column 8: 3 or 6

In these two solutions, four squares at the corners of a rectangle hold 3 and 6 one way round or the other, and nothing else in the grid tells the two ways apart. And these are only the first two the search met. Let the search run on instead of stopping at 2, and it finds every solution: 24,914 of them. (That run takes about 8 seconds of plain Python on our laptop, longer than this page lets a program run, so it isn’t done here.) One clue fewer, and the puzzle falls apart. Every one of the 17 clues is needed: take away any one of them instead, and the search finds hundreds or thousands of solutions.

So is there any 16-clue puzzle with only one solution? That question took mathematicians years.

A story from science

Seventeen, and not one fewer

Sudoku fans found many puzzles with 17 clues and one solution (Gordon Royle collected 49,151 different ones), and nobody ever found one with 16. Gary McGuire, of University College Dublin in Ireland, with Bastian Tugemann and Gilles Civario, settled it the hard way: take every possible finished grid, and check that none of them hides a 16-clue puzzle with only one solution. There are 6,670,903,752,021,072,936,960 finished grids (about 6.67 × 10²¹; counted by Bertram Felgenhauer and Frazer Jarvis, published in 2006), but most are the same grid turned, flipped or with its digits renamed, which leaves 5,472,730,538 really different ones. Their program, checker, searched them on the Stokes computer at the Irish Centre for High-End Computing from January to December 2011: about 7.1 million hours of processor time, about 3.6 seconds a grid. It found nothing. They announced on 1 January 2012 that a Sudoku with one solution needs at least 17 clues. Their first version of checker, from 2006, would have taken over 300,000 processor-years; a better algorithm, not a faster computer, made the proof possible.

Going further still

How many 4 × 4 grids?

Fill an empty 4 × 4 grid in every possible way instead of stopping at the first: there are only 288 finished 4 × 4 grids.

Dancing links

Your choose_square follows a rule older than Sudoku. In 1965 Solomon Golomb and Leonard Baumert suggested that a backtracking program choose, at each step, the choice with the fewest branches, whenever that can be found quickly. In 2000 Donald Knuth used the same rule in Algorithm X, his name for plain trying and taking back on puzzles where every part must be covered exactly once (an exact cover: tiling a board with shapes, placing queens on a chessboard, and Sudoku, where every square, and every digit in every row, column and box, must be used exactly once). His way of taking a step back quickly, dancing links, unhooks an item from a list so that it can be hooked back in exactly where it was. He traced that trick to Hirosi Hitotumatu and Kohei Noshita, who had used it in 1979 to make a program for the queens puzzle nearly twice as fast.

Thinking ahead

In his 2006 essay Solving Every Sudoku Puzzle, Peter Norvig adds constraint propagation to the search: after each digit, cross it off the choices of every square in its row, column and box, and whenever a square is left with one choice, fill it at once, and so on. Then most puzzles need little or no search at all. His program solved Inkala’s puzzles in about a hundredth of a second each. Yet among a million random puzzles he made, one took it 188 seconds. His guess was that a wrong choice in two early squares led to a long search before the program discovered it was wrong; that puzzle also turned out to have more than one solution.

A question to think about: on a 9 × 9 board your program is fast. Sudoku can be played on bigger boards too: 16 × 16 with 4 × 4 boxes, 25 × 25 with 5 × 5 boxes, and so on. In 2003 Takayuki Yato and Takahiro Seta, at the University of Tokyo, proved that deciding whether a Sudoku of any size can be filled in is NP-complete, one of the problems in Grade 12’s P versus NP: a filled grid is quick to check, and nobody knows a method that fills big ones quickly every time. Why does that not stop your program solving 9 × 9 puzzles in a blink?

Challenges

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. The examples show what your function should give; there are more tests you can’t see.

★ Is it solved?

Write is_solved(grid): True if the grid is full and every row, column and box holds each digit from 1 to 9 exactly once, False otherwise. Checking a finished grid is quick, however long finding it took.

def is_solved(grid):    # Give back True if every row, column and box holds 1 to 9.    return False grid = [[2, 4, 3, 7, 6, 9, 5, 8, 1],        [9, 5, 7, 4, 8, 1, 2, 6, 3],        [1, 6, 8, 3, 2, 5, 7, 9, 4],        [6, 3, 4, 9, 1, 2, 8, 7, 5],        [7, 2, 5, 8, 4, 6, 3, 1, 9],        [9, 8, 1, 5, 7, 3, 6, 4, 2],        [4, 7, 6, 1, 9, 2, 1, 5, 8],        [5, 1, 9, 2, 3, 8, 4, 2, 7],        [3, 9, 2, 6, 7, 4, 1, 5, 6]]print(is_solved(grid))

The easy puzzle, solved is_solved([[2, 4, 3, 7, 6, 9, 5, 8, 1], [9, 5, 7, 4, 8, 1, 2, 6, 3], [1, 6, 8, 3, 2, 5, 7, 9, 4], [4, 3, 5, 9, 1, 6, 8, 7, 2], [6, 2, 9, 8, 4, 7, 3, 1, 5], [7, 8, 1, 2, 5, 3, 6, 4, 9], [3, 7, 6, 1, 9, 2, 4, 5, 8], [5, 1, 4, 6, 3, 8, 9, 2, 7], [8, 9, 2, 5, 7, 4, 1, 3, 6]]) Should give True Yours —
The grid in the program is_solved([[2, 4, 3, 7, 6, 9, 5, 8, 1], [9, 5, 7, 4, 8, 1, 2, 6, 3], [1, 6, 8, 3, 2, 5, 7, 9, 4], [6, 3, 4, 9, 1, 2, 8, 7, 5], [7, 2, 5, 8, 4, 6, 3, 1, 9], [9, 8, 1, 5, 7, 3, 6, 4, 2], [4, 7, 6, 1, 9, 2, 1, 5, 8], [5, 1, 9, 2, 3, 8, 4, 2, 7], [3, 9, 2, 6, 7, 4, 1, 5, 6]]) Should give False Yours —
One square still empty is_solved([[2, 4, 3, 7, 6, 9, 5, 8, 1], [9, 5, 7, 4, 8, 1, 2, 6, 3], [1, 6, 8, 3, 2, 5, 7, 9, 4], [4, 3, 5, 9, 1, 6, 8, 7, 2], [6, 2, 9, 8, 4, 7, 3, 1, 5], [7, 8, 1, 2, 5, 3, 6, 4, 9], [3, 7, 6, 1, 9, 2, 4, 5, 8], [5, 1, 4, 6, 3, 8, 9, 2, 7], [8, 9, 2, 5, 7, 4, 1, 3, 0]]) Should give False Yours —

Tests passed: — / 9
Challenge: ★ solved

Write your is_solved in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Answer

★★ Only one choice

Write fill_forced(grid): again and again, find every empty square where only one digit is allowed and fill it, until there are none; then give back how many squares you filled. (Change grid itself.) Easy puzzles are solved this way alone, with no search at all.

def allowed(grid, r, c):    used = set(grid[r])    for i in range(9):        used.add(grid[i][c])    br = r // 3 * 3    bc = c // 3 * 3    for i in range(br, br + 3):        for j in range(bc, bc + 3):            used.add(grid[i][j])    return [d for d in range(1, 10) if d not in used] def fill_forced(grid):    # Fill every square with one choice, again and again; give back how many.    return 0 rows = ["...76....", ".......63", "1...2579.", "...9..87.", ".2..4..1.",        ".81..3...", ".7619...8", "51.......", "....74..."]grid = [[0 if ch == '.' else int(ch) for ch in row] for row in rows]print(fill_forced(grid))

The easy puzzle fill_forced([[0, 0, 0, 7, 6, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 6, 3], [1, 0, 0, 0, 2, 5, 7, 9, 0], [0, 0, 0, 9, 0, 0, 8, 7, 0], [0, 2, 0, 0, 4, 0, 0, 1, 0], [0, 8, 1, 0, 0, 3, 0, 0, 0], [0, 7, 6, 1, 9, 0, 0, 0, 8], [5, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 7, 4, 0, 0, 0]]) Should give 54 Yours —
Inkala 2010 fill_forced([[0, 0, 5, 3, 0, 0, 0, 0, 0], [8, 0, 0, 0, 0, 0, 0, 2, 0], [0, 7, 0, 0, 1, 0, 5, 0, 0], [4, 0, 0, 0, 0, 5, 3, 0, 0], [0, 1, 0, 0, 7, 0, 0, 0, 6], [0, 0, 3, 2, 0, 0, 0, 8, 0], [0, 6, 0, 5, 0, 0, 0, 0, 9], [0, 0, 4, 0, 0, 0, 0, 3, 0], [0, 0, 0, 0, 0, 9, 7, 0, 0]]) Should give 0 Yours —

Tests passed: — / 10
Challenge: ★★ solved

Write your fill_forced in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Another hint

Answer

★★★ One solution, or more?

Write count_solutions(grid, most): the number of solutions the puzzle has, but stop counting once you reach most. With most = 2 this tells you whether a puzzle is a proper Sudoku (exactly one solution). Don’t change grid in the end: put back every digit you try.

def count_solutions(grid, most):    # Count the solutions, stopping at most.    return 0 rows = ["4.....8.5", ".3.......", "...7.....", ".2.....6.", "....8.4..",        "....1....", "...6.3.7.", "5..2.....", "1.4......"]grid = [[0 if ch == '.' else int(ch) for ch in row] for row in rows]print(count_solutions(grid, 2))

17 clues count_solutions([[4, 0, 0, 0, 0, 0, 8, 0, 5], [0, 3, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 6, 0], [0, 0, 0, 0, 8, 0, 4, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 7, 0], [5, 0, 0, 2, 0, 0, 0, 0, 0], [1, 0, 4, 0, 0, 0, 0, 0, 0]], 2) Should give 1 Yours —
16 clues: the 6 in row 3 taken away count_solutions([[4, 0, 0, 0, 0, 0, 8, 0, 5], [0, 3, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 8, 0, 4, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 7, 0], [5, 0, 0, 2, 0, 0, 0, 0, 0], [1, 0, 4, 0, 0, 0, 0, 0, 0]], 2) Should give 2 Yours —
The easy puzzle count_solutions([[0, 0, 0, 7, 6, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 6, 3], [1, 0, 0, 0, 2, 5, 7, 9, 0], [0, 0, 0, 9, 0, 0, 8, 7, 0], [0, 2, 0, 0, 4, 0, 0, 1, 0], [0, 8, 1, 0, 0, 3, 0, 0, 0], [0, 7, 6, 1, 9, 0, 0, 0, 8], [5, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 7, 4, 0, 0, 0]], 2) Should give 1 Yours —

Tests passed: — / 8
Challenge: ★★★ solved

Write your count_solutions in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Another hint

Answer

Questions

What does a backtracking solver do when it reaches an empty square where no digit fits?

Pick an answer to see why.

Why does choosing the square with the fewest choices first make the solver so much faster?

Pick an answer to see why.

a.

In Step 2, solve puts grid[r][c] = 0 after a failed call. A friend leaves the line out, and their solver says False for a puzzle that has a solution. Explain why.

Answer

b.

A puzzle has a unique solution. The in-order solver made 9,727,396 tries on it, yours 481. Explain how two programs following the same rules can differ so much, using the idea of a tree of choices.

Answer

c.

McGuire, Tugemann and Civario proved there is no 16-clue Sudoku with one solution. Why couldn’t they prove it simply by trying lots of 16-clue puzzles and failing to find one?

Answer

d.

A friend says: “Sudoku is NP-complete, so a computer can’t solve them quickly.” Is that right for the puzzles in newspapers?

Answer

Quiz yourself on this unit →

Where to go next

Grade 11, Recursion: functions that call themselves, from the Tower of Hanoi to flood fill, and how to be sure they stop.
Grade 12, The Limits of Computing: P versus NP, and why checking an answer can be so much easier than finding one.
Grade 12, Algorithms for Hard Problems: another search whose choices multiply, and heuristics that make it manageable.
How Can a Computer Never Lose at Tic-Tac-Toe?: a search through every future of a game, with a function that calls itself.