Michael Helm

My first Sudoku solver is quick on easy puzzles and hopeless on hard ones. This post puts measured numbers on how far the later versions moved on from it. It covers the four versions on my portfolio page, from the first plain backtracking solver to the January 2024 update. The full source isn’t published, but the interesting parts are quoted below.

It started as an algorithm challenge: I wanted to write a solver and then keep making it faster. The Flask page was a way to show each version working.

What the project is

Each version is a small Flask app with a nine-by-nine grid of number inputs. You fill in the givens, press the button and the server either shows the solved grid or says the puzzle can’t be solved. The apps run in Docker (python:3.8-slim-buster images, Flask unpinned, the Werkzeug development server), one container per version, behind a reverse proxy on cosmo.ihelm.org.uk. All four are still live:

• Sudoku Solver v1
• Sudoku Solver v1.1
• Sudoku Solver v2
• Sudoku Solver v2 (January 2024 update)

Versions 1 and 1.1 date from 22 and 23 January 2023, and version 2 followed on 29 January 2023. The January 2024 update came almost a year later, on 21 January 2024.

Version 1: plain backtracking

Version 1 is the textbook approach. Find the first empty cell, reading row by row. Try each digit from 1 to 9. If a digit doesn’t clash with anything, place it and recurse. If the recursion fails, take the digit back out and try the next one. When no digit fits, return and let the previous cell try something else.

def solve(grid):
    global iterations
    empty = find_empty(grid)
    if not empty:
        return True
    row, col = empty

    for num in range(1, 10):
        if is_valid(grid, (row, col), num):
            iterations += 1
            grid[row][col] = num
            if solve(grid):
                return render_template("solution.html", grid=grid, iterations=iterations)
            grid[row][col] = 0
    return False

def find_empty(grid):
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                return (row, col)
    return None

def is_valid(grid, pos, num):
    # Check row
    for i in range(9):
        if grid[pos[0]][i] == num:
            return False

    # Check col
    # …

It works, but it is crude, and it has rough edges I’d rather admit to than hide:

• is_valid rescans the row, the column and the box for every digit tried.
• There is no check on the input. Give it a grid with a repeated given and it searches the whole tree before saying “Puzzle cannot be solved”.
• solve returns render_template(...) from inside the recursion. On success, the solution page is rendered at every level on the way back up. It is wasteful.
• The iteration counter is never reset. On the live server it accumulates across visitors until the container restarts.

Version 1.1: a better page, the same algorithm

Version 1.1 is the same solver with a better page: a styled grid with the three-by-three boxes marked, a proper title and a meta description, the first bit of SEO. Nothing changed in the search. I include it because the portfolio lists it, and because it makes a useful control: any difference between 1 and 1.1 is not about the algorithm.

Version 2: validate first, then try only what fits

Version 2 made two changes. First, is_input_valid checks the givens up front and rejects a grid with repeated digits (“Puzzle cannot be solved as the input is invalid”) instead of searching for a solution that can’t exist.

Second, solve stopped trying every digit. Trying digits that couldn’t possibly fit looked wasteful, so cutting them out was the next obvious speed-up. It builds the set of candidates for the cell from its row, column and box, and tries only those:

    possibilities = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    for i in range(9):
        if grid[row][i] in possibilities:
            possibilities.remove(grid[row][i])
        if grid[i][col] in possibilities:
            possibilities.remove(grid[i][col])
    box_x = col // 3
    box_y = row // 3
    for i in range(box_y*3, box_y*3 + 3):
        iterations += 1
        for j in range(box_x * 3, box_x*3 + 3):
            if grid[i][j] in possibilities:
                possibilities.remove(grid[i][j])

    for num in possibilities:
        if is_valid(grid, (row, col), num):
            # …

I described this on the portfolio page as drastically reducing solving time. The measurements below don’t bear that out, and the reason is worth understanding. Version 2 still picks the first empty cell in row order, and its candidates come out in ascending order. Removing the digits that is_valid would have rejected anyway doesn’t change which digits get tried, in which order, so it explores exactly the same search tree as version 1. It does less work per step, because it doesn’t call is_valid for digits already ruled out. But it takes exactly as many steps.

Version 2, January 2024 update: fewest candidates first

This is the version where the search itself changed. (Its own page calls it “Version 4”; I’ve kept the portfolio’s name for it here.) There are two ideas.

Pick the most constrained cell, not the first one. find_least_possibilities looks at every empty cell, works out its candidates and returns the cell with the fewest. This is the minimum remaining values heuristic (MRV), sometimes called “fail first”. A cell with one candidate is forced, so you place it immediately. A cell with zero candidates means you have already gone wrong, and you find out at once instead of after filling in a dozen cells that never mattered.

def find_least_possibilities(grid):
    min_count = 10  # More than the maximum possible count (9)
    best_cell = None
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                possibilities = find_possibilities(grid, row, col)
                if len(possibilities) < min_count:
                    min_count = len(possibilities)
                    best_cell = (row, col)
    return best_cell

Check the consequences of each move straight away. After placing a digit, forward_check looks at every empty cell, and if any of them has been left with no candidates, the move is rejected without recursing at all:

def forward_check(grid, row, col, num):
    original_num = grid[row][col]
    grid[row][col] = num  # Temporarily place the number

    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:  # Check only empty cells
                if not find_possibilities(grid, i, j):
                    grid[row][col] = original_num  # Restore the original number
                    return False

    grid[row][col] = original_num  # Restore the original number
    return True

The cost is that each call now does much more work. Choosing a cell scans every empty cell, and forward checking scans them all again for every digit tried. Fewer calls only pays off if the saving outweighs that, and as the results show, on easy puzzles it makes no visible difference. This version keeps is_input_valid from version 2.

Both ideas were my own, worked out the way a person tackles a Sudoku by hand: start with the cell that has the fewest options, and notice straight away when a move leaves another cell with none.

How I measured it

The apps’ own iteration counters can’t be compared. Version 1 counts only the digits that pass is_valid, and never resets. Version 1.1 counts every digit it tries. Version 2 adds three on each call to solve, because the increment sits inside the loop over the box’s rows. The January 2024 version counts only the digits it places. So the “approximately 1/100th” on my portfolio page, comparing the January 2024 version with version 2, was never a like-for-like figure. The rest of this post is the like-for-like version.

For this post I wrote a small test harness that sends the same puzzles to all four apps through Flask’s test client and counts one common unit: the number of calls to solve, recursive calls included. Every run has a 60 s limit, and a run that hits it is stopped and reported as not finished. The harness checks every answer independently against the puzzle’s givens, rather than trusting the app, and it repeats each finished run and takes the median time. The times come from my PC, not the server, and the demos run on a different Python version, so treat them as relative to one another rather than as server figures. Timings of a few milliseconds vary noticeably from run to run, so I make no claims about differences between them.

The puzzles, all unique-solution unless stated:

• Easy (32 clues): Grid 01 from Project Euler problem 96.
• Hard (22 clues): the first puzzle in hardest.txt from Peter Norvig’s essay Solving Every Sudoku Puzzle.
• Minimal (17 clues): the first puzzle in Gordon Royle’s collection of 17-clue puzzles, as archived by the Internet Archive.
• Built against backtracking (17 clues): the puzzle illustrating Wikipedia’s Sudoku solving algorithms article, described there as designed to work against the brute-force algorithm. I read the digits from the image.
• Valid givens, no solution (33 clues): I built this from the Easy puzzle by adding a 5 in the first cell, where the real solution has a 4. The 5 repeats nothing already given in its row, column or box, so only a search can find the problem.
• Duplicate givens (33 clues): I built this from the Easy puzzle by adding a second 3 to the first row.

Results

Solve calls and outcome per version. Times are shown only where the run was long enough for them to mean anything. Every other run on Easy, no solution and duplicate givens finished in a few milliseconds.

What the table shows

Versions 1, 1.1 and 2 search exactly the same tree. Wherever they finish, they make the identical number of calls: 201 on Easy and 335,638 on Hard. Version 2 only makes each call cheaper. On Hard that gets it from 1.58 s to 1.32 s, but it is the same search.

On easy puzzles, the January 2024 version makes fewer calls but is no faster. On Easy it needs 50 calls against 201, yet all four versions finish in a few milliseconds and I wouldn’t claim a winner. This is the trade-off from earlier: a smarter call is a more expensive call.

On a hard puzzle, the call count wins. On Hard, the January 2024 version makes 3,670 calls against 335,638. Version 2 makes 91.5 times as many calls, and takes 3.24 times as long. Version 1 takes 3.88 times as long. The time ratio is smaller than the call ratio because each of the January 2024 version’s calls does far more work. It is still a large gain.

On the hardest puzzles, it is the difference between solving and not solving. The 17-clue puzzles give a plain first-empty-cell search very little to work with. With so few givens, the early cells have many candidates and the contradiction may only appear many levels deeper, so the search spends its time in huge subtrees that contain no solution. Versions 1, 1.1 and 2 didn’t finish either one within 60 s. The January 2024 version solved the first in 0.530 s and the Wikipedia puzzle, built specifically to defeat brute force, in 4.72 s.

Early rejection pays off on impossible puzzles. With the valid-looking but unsolvable puzzle, the first three versions make 349 calls to discover there is no solution, while the January 2024 version needs 4. Duplicate givens cost version 1 and 1.1 308 calls, and cost versions 2 and later none at all, because the input check rejects them first.

Where the old 1/100th claim stands

The portfolio page says the January 2024 version “reduces solution attempts to approximately 1/100th of the v2 algorithm”. Measured as solve calls, on Hard, version 2 makes 91.5 times as many, so the claim is close there. On Easy it is 4.02 times. On the two hardest puzzles version 2 doesn’t finish at all, so there is no ratio to quote. “Approximately 1/100th” is a fair description of one puzzle and an overstatement for easy ones.

I’ve corrected the portfolio page to quote the measured figure.

Lessons

Three things I’d pass on from this:

• Measure before you claim, and measure like for like. My own “approximately 1/100th” was read off counters that counted different things.
• Doing less work per step and taking fewer steps are different improvements. Version 2 did the first and the January 2024 version did the second.
• A cleverer search is not always faster. Where the puzzle is easy, the extra work per call cancels the saving.

Wrapping up

That is the whole story of the four versions, from a solver that falls over on a 17-clue puzzle to one that solved every puzzle I gave it. If you want to compare them yourself, the four demos are all still live. Try the same hard puzzle on version 2 and the January 2024 update and watch which one comes back. Good luck, and let me know if you find a puzzle that stumps the last one.