Solving sudoku from scratch

The rule

Sudoku solvers are a classic programming exercise, and the well-known approaches are one search away. That was the problem. I wanted to see what I'd come up with on my own, so the repo's README states the rule up front: "Trying to build this without consulting other algorithms."

The commit history tells the rest. The first real commit is solving code as written in one file. I wrote the whole solver first, then pushed it on August 23, 2019, and spent the next 20 minutes or so tidying: moving the sample puzzles into a folder, splitting out helper functions, adding a license and a run script. Seven commits, about 160 lines of JavaScript.

How it works

It's the way a person solves sudoku with a pencil, made relentless. Look at an empty cell and ask which numbers could possibly go there.

Row is missing13478

Column is missing35679

Box is missing457

Only 7 is in all three, so the cell must be 7.

Step 1: for an empty cell, take the numbers missing from its row, its column and its 3×3 box. Whatever is in all three lists is a candidate. One candidate means the cell is solved. This is the first cell the solver fills in easy.js.

One cell rarely solves a puzzle, so the solver sweeps the whole board, fills every cell it can, and repeats. Each number it writes in narrows the options for its neighbors, so easy puzzles fall apart in a few sweeps.

1
Any empty cells left?No → solved ✓
2
Sweep the board. For every empty cell, work out its candidates. If there's exactly one, write it in right away, so later cells in the same sweep benefit.
3
Did any cell end up with zero candidates?Yes → dead end ✗, back up
4
Did the sweep change the board?Yes → go back to 1 ↺
5
Stuck. Take a snapshot and guess. Find the first cell with exactly two candidates. Try the first one and start again from 1. If that leads to a dead end, restore the snapshot and try the second.Both fail → dead end ✗, back up

Step 2: the whole solver is this loop. solve() is one sweep (steps 2–3), and solvingTree() decides what happens next (steps 1, 4 and 5).

Harder puzzles get stuck: every empty cell has two or more candidates, and sweeping changes nothing. That's when it guesses. It snapshots the board, picks a cell with exactly two options, and tries one. If the guess is wrong, a later sweep finds a cell with no possible numbers, and the solver rolls back to the snapshot and tries the other option. Guesses can stack inside guesses, which makes it a depth-first search.

Step 3: guessing turns the loop into a search tree. Each guess is followed by more sweeps. A wrong guess eventually leaves some cell with no candidates, and the solver backs up to the last snapshot and takes the other branch. This example is illustrative; on the "world's hardest" puzzle it got stuck 928 times.

How it did

The repo ships with six puzzles. I ran them again for this write-up, in a browser, with counters added to the original code:

Puzzle	Empty cells	Sweeps	Guesses	Dead ends	Time	Result
`easy`	43	3	0	0	~1 ms	Solved
`easy-two`	43	3	0	0	<1 ms	Solved
`medium-one`	51	8	1	0	<1 ms	Solved
`medium-two`	56	69	29	14	~7 ms	Solved
`everest`	60	4,172	1,850	922	~60 ms	Solved
`extreme`	58	606	238	120	~22 ms	No solution

everest is Arto Inkala's puzzle, published in 2012 as the "world's hardest sudoku." My solver needs nearly a thousand dead ends to get through it, and it still finishes in a fraction of a second.

Then there's extreme, which the solver says can't be solved. I assumed that was a bug in the solver. It isn't. Row 7 of the puzzle file reads 0 0 0 7 0 7 0 0 0: two 7s in one row. I made a typo copying it in back in 2019, and the solver correctly reported that no solution exists.

Looking back

Without knowing it, I'd landed on the standard approach: rule out candidates using what's already on the board, and when that stalls, guess and backtrack. That's the same general shape as most textbook solvers. If I picked it back up, I'd:

Guess where it's cheapest. It guesses at the first cell with two options. Choosing the cell with the fewest options would prune the search faster, and it would handle a board where no cell has exactly two.
Keep candidates around. Every sweep recomputes each cell's options from scratch. Updating them only when a neighbor changes would cut most of the work.
Return the answer. The solver prints the finished board but only returns true or false, so nothing else can use the solution.
Check the puzzle first. A two-line check for duplicate givens would have caught the typo before any solving started.

The code is still exactly as I left it in 2019: github.com/josephm28/sudoku.