Sudoku, Go and WebAssembly - Eli Bendersky's website

A Sudoku Toolkit in Go, Compiled to the Browser

When a programmer encounters a Sudoku puzzle, the urge to write an automated solver is nearly irresistible. But this latest project went beyond basic solving. The goal was a toolkit for generating puzzles of varying difficulty, paired with an experiment in running Go code in the browser through WebAssembly. The result is the go-sudoku package.

Solving: Old Algorithm, New Backend

The solver is based on Peter Norvig's constraint-propagation approach. It applies basic row, column, and block elimination, then falls back to recursive search when it gets stuck. In practice, this is fast enough for most single-solution puzzles.

While Norvig's original Python code is already quick, the Go port is dramatically faster—measuring about one hundred times faster in informal tests. A key optimization lies in the data structure: where Norvig uses strings to track possible digits in each square, the Go version uses a uint16 with bitwise operations. This avoids the overhead of string allocation and linear scanning. For example, a square that cannot contain a 2 is represented not as the string "13456789", but as a single integer with the right bits set.

Testing against Norvig's curated list of hard puzzles, the solver completes each one in under a quarter of a millisecond on average. The package also includes SolveAll, which finds every valid solution; running it on an empty board is not advised.

One experiment with adding higher-order human techniques, specifically Naked Pairs via the ApplyTwinsStrategy function, showed that such strategies slow the solver down. The built-in backtracking search is efficient enough that the extra logic isn't worth the overhead.

Generation Strategy: Filling, Then Removing

Generating interesting puzzles is the real focus. The approach starts with an empty board. First, a solver with randomized digit ordering quickly produces a random, valid solution in tens of microseconds. Then, the generator removes numbers from squares one by one in a random order.

At each removal step, the code verifies that the board still has exactly one solution. The process stops once a threshold is reached, such as a target number of remaining hints or a difficulty estimate. Compared to a simpler method that places random digits until a contradiction, this approach guarantees a single solution. The trade-off: it is hard to generate extremely difficult puzzles with very few hints. For non-expert solvers, the generated puzzles are more than challenging enough.

Evaluating Difficulty

Difficulty estimation is essential when generating puzzles for others. The evaluation logic in go-sudoku is inspired by the paper "Sudoku Puzzles Generating: from Easy to Evil" by Xiang-Sun ZHANG's research group, with some adjustments. The resulting score ranges from 1.0 (easiest) to 5.0 (hardest); a score of 3.0 is already a good workout.

A Browser Interface via WebAssembly

To make puzzle generation usable for printing, the project ships a small web interface. The Go package can emit any board as SVG, and the same Go code lives on the frontend: it compiles to WebAssembly using Go's wasm backend and is driven by a thin layer of JavaScript and HTML.

The web UI exposes a "Hint count" input, which sets the target number of non-empty squares. Below about 25 hints, treat it as a lower bound—the generator may leave slightly more. Lower hint counts also mean longer generation times.

Compiling the Go code to WebAssembly was straightforward. The demonstration files live in the repository's cmd/wasm directory, useful as a reference for similar browser-based experiments.