Sudoku, Go and WebAssembly

Solving puzzles

I started from Peter Norvig's fantastic Solving Every Sudoku Puzzle, where he describes a constraint-satisfaction solver written in Python. The solver only employs basic row/column/block elimination as a solution strategy and then runs a recursive search when stuck. This approach is very fast for solving Sudoku puzzles that have a single solution.

Norvig's solver in Python is already quick, but my Go code is far faster still - around 100x faster in some informal measurements. One reason for this is that Go - in general - is more efficient than Python. Another is a key optimization to the core data structure; Norvig's code uses a string to represent the possible digits in a Sudoku square; e.g. if some square can have any value except 2, it's represented as the string "13456789". So there's a lot of string allocation, deallocation and linear scanning. I've replaced this by a single uint16 in Go with bitwise operations to add/remove/test digits. My solver burns through Norvig's list of "hard" Sudoku puzzles taking less than a quarter of a millisecond per puzzle on average.

I've also added a SolveAll function that finds all solutions of a given Sudoku puzzle; careful - do not run this on an empty board :-)

In the repository, you can try the solver by running the cmd/solver command.

More powerful Sudoku solving strategies

As mentioned above, my solver follows Norvig's in that it only applies the basic "first-order" constraint propagation technique to Sudoku - elimination. Expert human Sudoku solvers have many higher-order techniques at their disposal. For my solver, I experimented with implementing one of them - Naked Pairs (alternatively known as "Naked Twins").

While the implementation works (check out the ApplyTwinsStrategy function), I found that it's not very helpful for the automated solver. The backtracking search is so fast that burdening it with additional strategies makes it slower, not faster. YMMV.

Generating puzzles

Solving puzzles was just the warmump - I've done this before and just wanted the infrastructure set up. What I was really after is generating interesting Sudoku puzzles.

The approach Norvig uses is:

1. Start from an empty board
2. Assign random digits to random squares until a contradiction is reached (the puzzle becomes unsolvable), or a minimum count of assigned squares is reached.

Unfortunately, most puzzles produced this way will have multiple solutions; if you've done a bit of manual Sudoku-ing, you'll know that puzzles with multiple solutions suck - no one likes them.

Instead, we can start with an empty board:

Then, we solve the board using a randomized solver (a solver which randomizes the order of guessed digits it tries to assign to empty squares); this is a very quick process (tens of micro-seconds) that produces a random valid solution:

Now, we remove numbers from squares on the board one by one (in random order). At each step, we make sure that the resulting board still has a single solution. We stop when some pre-set threshold is reached - number of remaining hints, some difficulty estimate, etc.

Compared to the method used by Norvig, this approach has a powerful advantage: the produced puzzle is guaranteed to have a single solution. It also has a limitation: it's challenging to generate extremely hard puzzles with very low hint counts. That said, the puzzles it generates can certainly be hard enough for non-experts, so it's not a huge problem in practice [1].

Estimating puzzle difficulty

Estimating the difficulty of Sudoku puzzles is important if you want to generate puzzles for others to solve. The most enjoyable puzzles are just at the right level of difficulty - not too easy and not too hard. The estimation process itself is fairly complicated and heuristic, and there are academic papers written on the subject.

In the go-sudoku package the evaluation (EvaluateDifficulty) is inspired by the paper "Sudoku Puzzles Generating: from Easy to Evil" by Xiang-Sun ZHANG's research group, with some tweaks. The difficulty score is provided on a scale from 1.0 (easiest) to 5.0 (hardest). Generally, I find that puzzles with difficulty 3 or above are pretty hard!

Web interface

Since my ultimate goal was to generate printable Sudoku puzzles for my family, I wanted a simple graphical interface one could use to generate puzzles and print those that look good. Instead of mucking with GUIs or PDFs, I decided to embrace the web! This is achieved in two steps:

1. The go-sudoku package can emit any Sudoku board into a SVG image.
2. Using Go's wasm backend, the package is compiled to WebAssembly and attached to a simple JS/HTML frontend.

The result is quite pleasing - you can check it out online [2]; here's a screenshot:

The "Hint count" box tells the generator how many hints (non-empty squares) to leave on the board. For low counts (lower than 25 or so) it should be treated as a lower bound; the generator will often generate puzzles with slightly more hints. Also, the lower the hint count, the longer it might take to run.

Compiling my Go code to WebAssembly turned out to be surprisingly easy! If you're interested in seeing how it works, take a look at the cmd/wasm directory in the repository.