go-sudoku

This is a toolkit for solving and generating Sudoku puzzles in Go.

What's inside

All the code is in a single top-level package: sudoku. It's broadly separated into three parts:

• sudoku.go: board representation and functions for parsing boards from strings, emitting boards back to output and solving Sudoku puzzles. The basic solver uses constraint propagation and recursive search and is based on Peter Norvig's old post, although the Go code is about 100x faster than Norvig's Python (faster compiled language but also an optimized board representation).

Contains additional functionality like finding all the solutions of a given puzzle and not just a single solution.

• generator.go: generate valid Sudoku puzzles that have a single solution. The algorithm is based on a mish-mash of information found online and tweaked by me. Contains additional functionality like generating symmetrical Sudoku boards.

Note: generating hard-to-solve boards with a single solution is fairly difficult. The best way to do this in practice seems to be to generate a large number of boards, sifting through them to find the hardest ones. These boards can then be transformed in a myriad ways to retain the same difficulty but look and feel very different (through swapping rows and columns, rotations, and permuting the existing hint digits). Therefore, a single genuienly hard board can be replayed in many different ways.

• difficulty.go: code to evaluate the difficulty of a given Sudoku puzzle; the approach was partially inspired by the paper "Sudoku Puzzles Generating: from Easy to Evil" by Xiang-Sun ZHANG's research group.

The cmd directory has two command-line tools: generator and solver that demonstrate the use of the package.

Testing

Some tests take a while to run, so they are excluded if the -short testing flag is provided:

$ go test -v -short ./...

Generating printable boards

go-sudoku includes some rudimentary functionality to emit a Sudoku board into a printable SVG format, like this:

You can invoke the cmd/generator command with the -svgout flag to see this in action, or use the web interface.

Web interface

This repository includes a web interface for generating Sudoku puzzles, by compiling the Go code to WebAssembly. To run it locally:

    $ cd cmd/wasm
    $ make build
    $ make serve

This will run a local webserver; open http://localhost:8899 in your browser to generate puzzles!

The repository also has a GitHub actions setup to automatically deploy the web interface to https://eliben.github.io/go-sudoku on each commit.