Sudoku Solver
2022A playable Sudoku board with a depth-first backtracking solver, written in Python with pygame. The solver is ported to TypeScript here so you can step through the search in the browser.
- Python
- pygame
- TypeScript
Sudoku, solved live
Runs entirely in your browserPlay it yourself, or switch to Watch it solve and try the hardest board.
Loading solver…
The original is two files: solver.py holds the algorithm and GUI.py draws a pygame board with cell selection, pencil marks, a strike counter and a timer. Keeping the solver free of any dependency on the UI was the point — it imports nothing at all, which is what made it portable years later.
The interesting part of a Sudoku solver is not that it finds the answer but how much work it does to get there. Backtracking commits to a guess, walks as deep as it can, and unwinds the moment the board becomes contradictory. That cost is invisible when you print the finished grid, so the demo exposes it: every attempt, placement and undo is a step you can watch.
To animate it without rewriting the algorithm, I re-expressed solve() as a generator that yields each decision. The recursion is unchanged — yield* delegates through it — but the caller now controls the pace, which is what makes stepping, pausing and speed control possible.
What it does
- Solver logic is pure and dependency-free, so it unit tests in plain Node with no DOM
- Generator-based stepping animates the real recursion rather than a re-implementation
- Runs on requestAnimationFrame with a per-frame budget, so high speeds never block the page
- The hardest board takes ~700x the search of the original — visible live in the step counter
Problems worth writing down
Porting the box-conflict check looked trivial but hid a real bug. The Python compares tuples — (i, j) != pos — and the obvious translation, r !== row && c !== col, is not equivalent: it also skips every cell sharing just a row or just a column, missing genuine conflicts.
The correct negation is !(r === row && c === col). Two unit tests pin the exact case the naive port would get wrong. It happens not to change the answer here because the row and column scans already ran, but only by accident.
My first choice of showcase puzzle was one built to defeat left-to-right backtracking. Measured, it needed 622 million decisions and pegged a CPU core for 12 seconds — which reads as a broken page, not an impressive one.
Swapped in Arto Inkala's 2012 puzzle: roughly 450,000 decisions, still ~700x the original board, but done in under 20ms.