README
¶
Sudoku Solvers and Simplifiers
This project aims to implement different techniques for simplifying and solving sudokus.
Beware of breaking changes! The API is not stable at all!
For good descriptions of some techniques check out Sudoku of the Day (no affiliation)!
You can see the code in action at sudokoin.com.
All help is greatly appreciated!
Documentation
¶
Overview ¶
Package sudoku contains sudoku solvers following different strategies.
Index ¶
- type AnnotatedBoard
- type Board
- func Backtrack(ab AnnotatedBoard, maxSolutions int) (solved bool, solutions []Board)
- func GenerateSimple(random Board, minimum int) (unsolved Board)
- func NewEmptyBoard(size int) Board
- func NewFromShort(s string, size int) (bo Board, err error)
- func NewRandomBoard(size int) Board
- func SingleCandidate(ab AnnotatedBoard, maxSolutions int) (bool, []Board)
- type Candidates
- type Parser
- type Simplifier
- type Solver
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AnnotatedBoard ¶
type AnnotatedBoard struct {
Board
Candidates [][]Candidates
}
AnnotatedBoard contains "penciled" candidates.
func CandidateLines ¶
func CandidateLines(ab AnnotatedBoard) (ab2 AnnotatedBoard, succeeded bool)
CandidateLines tries to simplify by finding candidates of the same kind on the same row or column within a block, so that they can be safely removed from other fields of that line not within that block.
func NewAnnotatedBoard ¶
func NewAnnotatedBoard(bo Board) (ab AnnotatedBoard, err error)
NewAnnotatedBoard returns an annotated version of provided board.
func (AnnotatedBoard) Annotate ¶
func (ab AnnotatedBoard) Annotate() (AnnotatedBoard, error)
Annotate (naively) annotates a board with possible candidates for each field. All data except board will be overwritten.
func (AnnotatedBoard) Copy ¶
func (ab AnnotatedBoard) Copy() (ab2 AnnotatedBoard)
Copy returns a copy of the annotated board. Helpful to stay as immutible as possible for now.
func (AnnotatedBoard) Solved ¶
func (ab AnnotatedBoard) Solved() bool
Solved returns true if board is solved correctly.
type Board ¶
type Board [][]int
Board contains all fields of a simple, unannotated sudoku.
func Backtrack ¶
func Backtrack(ab AnnotatedBoard, maxSolutions int) (solved bool, solutions []Board)
Backtrack implements a simple backtracking solver. It is not performant but guaranteed to finish.
func GenerateSimple ¶
GenerateSimple generates a board that is solvable with only single candidates strategy. Minimum param sets the number of minimum numbers that should remain on sudoku. minimum <= 0 will be ignored (hardest) and the higher the easier it gets. minimum >= size² makes no sense.
func NewEmptyBoard ¶
NewEmptyBoard builds an empty board with provided size.
func NewFromShort ¶
NewFromShort tries to parse provided short notation into board with provided size.
func NewRandomBoard ¶
NewRandomBoard returns a solved, pseudo random board of provided size.
func SingleCandidate ¶
func SingleCandidate(ab AnnotatedBoard, maxSolutions int) (bool, []Board)
SingleCandidate will look through annotated board for fields with just one candidate, fill it, recalculate candidates for all fields, and repeat, until board is solved or no longer solvable. It will not return more than one solution.
func (Board) Copy ¶
Copy returns a copy of the board. Helpful to stay as immutible as possible for now.
func (Board) FirstEmpty ¶
FirstEmpty returns coordinates of first empty field and whether one was found.
func (Board) UltraShort ¶
UltraShort returns an even shorter identifier only if board is full. It does so by returning only values and removing the last column and row. A 9x9 sudoku will thus result in 64 chars.
type Candidates ¶
type Candidates int
Candidates contains all "penciled" numbers that may occupy a field.
func (Candidates) Add ¶
func (c Candidates) Add(v int) Candidates
Add adds provided number to candidates (if not exists).
func (Candidates) Complement ¶
func (c Candidates) Complement(size int) Candidates
Complement returns the candidates not represented assuming a sudoku of provided size.
func (Candidates) Contains ¶
func (c Candidates) Contains(v int) bool
Contains checks whether candidates contain provided number.
func (Candidates) Decimals ¶
func (c Candidates) Decimals() (dcs []int)
Decimals returns candidates as a decimal array.
func (Candidates) Remove ¶
func (c Candidates) Remove(v int) Candidates
Remove provided number from candidates (if exists).
func (Candidates) Single ¶
func (c Candidates) Single() bool
Single returns whether candidates contain a single candidate.
type Parser ¶
A Parser is a function that parses a certain string representation of a sudoku into a board.
type Simplifier ¶
type Simplifier func(ab AnnotatedBoard) (ab2 AnnotatedBoard, succeeded bool)
A Simplifier does not solve a sudoku but tries to remove candidates.
type Solver ¶
type Solver func(ab AnnotatedBoard, maxSolutions int) (solved bool, solutions []Board)
A Solver is a function that tries to solve an annotated board following a certain strategy. An integer should be provided to limit the amount of calculated solutions. -1 means, as many solutions as possible will be calculated.
Source Files