This is a toolkit for solving and generating Sudoku puzzles in Go.
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.
Some tests take a while to run, so they are excluded if the -short
testing
flag is provided:
$ go test -v -short . ./svg
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.
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:https://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.