README
¶
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 . ./svg
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.
Documentation
¶
Index ¶
- Variables
- func ApplyTwinsStrategy(values Values) bool
- func CountHints(values Values) int
- func Display(values Values) string
- func DisplayAsInput(values Values) string
- func DisplayAsSVG(w io.Writer, values Values, difficulty float64)
- func EliminateAll(values Values) bool
- func EvaluateDifficulty(values Values) (float64, error)
- func IsSolved(values Values) bool
- func WithStats(f func())
- type Digits
- type Index
- type SolveOptions
- type StatsCollector
- type Unit
- type Values
Constants ¶
This section is empty.
Variables ¶
var EnableStats bool = false
EnableStats enables statistics collection during the processes of solving. When stats are enabled, solving will be slightly slower.
Note: statistics collection is NOT SAFE FOR CONCURRENT ACCESS.
Functions ¶
func ApplyTwinsStrategy ¶
ApplyTwinsStrategy applies the "naked twins" Sudoku strategy to the given board and updates it. It returns false if there was a contradiction discovered while applying the strategy. The "naked twins" strategy is to find two digits that are the only candidates in two squares in the same unit. This helps eliminate these digits from other squares in the same unit. For example, two squares in the same row cell may have 38 as their only candidates, which means that 3 and 8 must occupy these squares (though we don't know which goes where), and that no other square in the unit may have either 3 or 8.
func CountHints ¶
CountHints counts the total number of hints on the board.
func Display ¶
Display returns a visual representation of values, with all the digit candidates as a string in each cell.
func DisplayAsInput ¶
DisplayAsInput returns a 2D Sudoku input board corresponding to values. It treats solved squares (with one candidate) as hints that are filled into the board, and unsolved squares (with more than one candidate) as empty.
func DisplayAsSVG ¶
DisplayAsSVG write the board's visual representation in SVG format into w. The difficulty is emitted too.
func EliminateAll ¶
EliminateAll runs elimination on all assigned squares in values. It applies first-order Sudoku heuristics on the entire board. Returns true if the elimination is successful, and false if the board has a contradiction.
func EvaluateDifficulty ¶
EvaluateDifficulty evaluates the difficulty of a Sudoku puzzle heuristically and returns the score on a scale from 1.0 (easiest) to 5.0 hardest. It can also return an error if the given board has contradictions, is unsolvable, etc. It should be passed a board that didn't have elimination applied to it.
The heuristics are based on 4 factors:
- How many hints (filled-in squares) the board has.
- How many hints remain after running a round of elimination (first-order Sudoku solving value deduction).
- How many hints does a row or column with the minimal number of hints have
- How many guesses a backtracking search requires to solve the board (averaged over multiple runs).
This approach was partially inspired by the paper "Sudoku Puzzles Generating: from Easy to Evil" by Xiang-Sun ZHANG's research group.
Types ¶
type Digits ¶
type Digits uint16
Digits represents a set of possible digits for a Sudoku square. The functions in this file perform set operations on Digits, as needed for Sudoku.
func FullDigitsSet ¶
func FullDigitsSet() Digits
FullDigitsSet returns a Digits with all possible digits set.
func SingleDigitSet ¶
SingleDigitSet returns a Digits with a single digit 'n' set.
func (Digits) RemoveAll ¶
RemoveAll removes all digits represented by dn from d and returns the new set.
func (Digits) SingleMemberDigit ¶
SingleMemberDigit returns the digit that's a member of a 1-element set; this assumes that the set indeed has a single element.
type Index ¶
type Index = int
Index represents a square on the Sudoku board; it's a number in the inclusive range [0, 80] that stands for row*9+col.
These are the squares designated by an Index:
0 1 2 | 3 4 5 | 6 7 8 9 10 11 | 12 13 14 | 15 16 17
18 19 20 | 21 22 23 | 24 25 26 ---------+----------+--------- 27 28 29 | 30 31 32 | 33 34 35 36 37 38 | 39 40 41 | 42 43 44 45 46 47 | 48 49 50 | 51 52 53 ---------+----------+--------- 54 55 56 | 57 58 59 | 60 61 62 63 64 65 | 66 67 68 | 69 70 71 72 73 74 | 75 76 77 | 78 79 80
type SolveOptions ¶
type SolveOptions struct {
// Randomize tells the solver to randomly shuffle its digit selection when
// attempting to guess a value for a square. For actual randomness, the
// rand package's default randomness source should be properly seeded before
// invoking Solve.
Randomize bool
}
SolveOptions is a container of options for the Solve function.
type StatsCollector ¶
var Stats StatsCollector
Stats is the global variable for accessing statistics from this package. It's recommended to call Stats.Reset() before solving a board, and access the Stats fields after it's done.
func (*StatsCollector) Reset ¶
func (s *StatsCollector) Reset()
type Unit ¶
type Unit = []Index
Unit is a list of square indices that belong to the same Sudoku unit - a row, column or 3x3 block which should contain unique digits. There are overlaps between many units - e.g. a single square will be a member of a row unit, a column unit and a 3x3 block unit.
type Values ¶
type Values []Digits
Values represents a Sudoku board in a format that's usable for solving. An element at index [i] in Values represents Sudoku square i (see the documentation of the Index type), and contains a set of all candidate digits for this square.
func EmptyBoard ¶
func EmptyBoard() Values
EmptyBoard creates an "empty" Sudoku board, where each square can potentially contain any digit.
func Generate ¶
Generate generates a random Sudoku board that has a single solution, with at-most hintCount hints remaining on the board. Note that this cannot be always reliably done when the count is low (lower than 23 or so), because generating a board with a single solution that has a low number of initial hints is very hard. There are no guarantees made about the difficulty of the generated board, though higher hint counts generally correlate with easier boards. It's recommended to generate a large number of boards using this function and evaluate their difficulty separately using EvaluateDifficulty. Notes:
- Make sure the default rand source is seeded if you really want to get random boards.
- This function may take a while to run when given a low hintCount.
func GenerateSymmetrical ¶
GenerateSymmetrical is similar to Generate, but it generates symmetrical boards with 180-degree rotational symmetry. Because of this additional constraint, it may have more trouble generating boards with a small hintCount than Generate, so you'll have to run it more times in a loop to find a good low-hint-count board.
func ParseBoard ¶
ParseBoard parses a Sudoku board given in textual representation, and returns it as Values. The textual representation is as described in http://norvig.com/sudoku.html: a string with a sequence of 81 runes in the set [0123456789.], where 0 or . mean "unassigned". All other runes in the string are ignored, making the input format flexible (it can be just 81 runes on a single line, or it can be a nice multi-line |-separated board representation - since all runes outside the aforementioned set are ignored).
If runElimination is false, the board is returned immediately after parsing. If runElimination is true, ParseBoard will invoke EliminateAll on the board and return the result. This is recommended when the board is then passed to a solver. It returns an error if there was an issue parsing the board, or if the board isn't a valid Sudoku board (e.g. contradictions exist).
func Solve ¶
func Solve(values Values, options ...SolveOptions) (Values, bool)
Solve runs a backtracking search to solve the board given in values. It returns true and the solved values if the search succeeded and we ended up with a board with only a single candidate per square; otherwise, it returns false. The input values is not modified. The solution process can be configured by providing SolveOptions.
func SolveAll ¶
SolveAll finds all solutions to the given board and returns them. If no solutions were found, an empty list is returned. max can specify the (approximate) maximal number of solutions to find; a value <= 0 means "all of them". Often more solutions than max will be returned, but not a lot more (maybe 2-3x as many). values is not modified. Warning: this function can take a LONG time to run for boards with multiple solutions, and it can consume enormous amounts of memory because it has to remember each solution it finds. For some boards it will run forever (e.g. finding all solutions on an empty board). If in doubt, use the max parameter to restrict the number.
Source Files
Directories