Framework Overview
Solvers
SudokuSpice provides two different solvers: the
ConstraintBased.PuzzleSolver
or the original
RuleBased.PuzzleSolver
.
Generally speaking, the rule-based solver is the fastest of the two when solving standard Sudoku puzzles. However, the constraint-based solver can be faster in some cases, especially when implementing custom rules or constraints.
Important concepts
SudokuSpice uses four main interfaces:
The
IPuzzle
Puzzles store the underlying Sudoku data. You likely only need the standard implementations,
Puzzle
for constraint-based tools, andPuzzleWithPossibleValues
for rule-based tools. However, the interface is provided in case you need to do something a little different, like work with a puzzle with jagged regions instead of the normal square box regions.The
IRule
Rules define - you guessed it - the rules for a puzzle. For example, standard Sudokus use the
RowUniquenessRule
, theColumnUniquenessRule
, and theBoxUniquenessRule
. For convenience and efficiency, these come prepackaged in theStandardRules
class. Rules do not directly modify theIPuzzle
or its possible values themselves. They should use anIReadOnlyPuzzle
and just enough internal state to efficiently provide the possible values of any given square according to only that rule.Rules are enforced by an
IRuleKeeper
. TheDynamicRuleKeeper
provides a general implementation that works with any number of rules. Custom implementations can provide even more efficiency, but are generally messier and more complex than simply creating custom rules.StandardRuleKeeper
is an example of this. Check out the benchmarks for performance comparisons. The rule keeper actually updates the possible values based on all the rules while ensuring that no rules are broken by any given update.The
IHeuristic
Heuristics are logical tricks that can be used to reduce the number of possible values for any given square. These are only used in solving when the framework would otherwise have to guess (i.e. all unset squares have at least two possible values), so they can be relatively expensive and still improve solving times.
Heuristics depend on an
IReadOnlyPuzzleWithMutablePossibleValues
. They directly modify the possible values during an update. They can alo optionally depend on one or more rules, as is demonstrated by theUniqueInRowHeuristic
. Heuristics can either be perfect heuristics, i.e. they reduce squares to only one possible value (like theUniqueIn*
heuristics), or they can be loose heuristics, i.e. they eliminate possible values from squares, but don't necessarily reduce them down to a single possible value.Due to heuristics' complexity and flexibility, no generic class is provided to enforce multiple heuristics. To enforce multiple heuristics, define a custom heuristic that implements your desired heuristics. This pattern is demonstrated by the
StandardHeuristic
.The
IConstraint
Constraints represent rules that the puzzle needs to satisfy. For example, the
RowUniquenessConstraint
enforces the constraint that "each row must contain all possible values."Constraints are implemented using a form of an exact-cover matrix. The exact-cover matrix combines two concepts into a single matrix. Each row represents a possible value for a single square, for example "Row: 1, Column: 0, Value: 2". We'll represent this in the short-form notation:
R1C0V2
. Each column represents a single objective that must be satisfied, for example, "Row 1 contains a 2." We'll represent columns in the short-form notation: "R1V2". These rows and columns can be combined into a single matrix containing 1s and 0s, where a 1 is placed in each column (i.e. objective) that a given row (i.e. possible square value) satisfies. For a standard Sudoku puzzle, this looks something like the following:R0V1 R0V2 ... R1V1 R1V2 ... C0V1 C0V2 ... B0V1 V0V2 ... B8V8 B8V9 R0C0V1 1 0 ... 0 0 ... 1 0 ... 1 0 ... 0 0 R0C0V2 0 1 ... 0 0 ... 0 1 ... 0 1 ... 0 0 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... R0C1V1 1 0 ... 0 0 ... 0 0 ... 1 0 ... 0 0 R0C1V2 0 1 ... 0 0 ... 0 0 ... 0 1 ... 0 0 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... R1C0V1 0 0 ... 1 0 ... 1 0 ... 1 0 ... 0 0 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... R8C8V8 0 0 ... 0 0 ... 0 0 ... 0 0 ... 1 0 R8C8V9 0 0 ... 0 0 ... 0 0 ... 0 0 ... 0 1 SudokuSpice's implementation of this matrix can be thought of as a sparse 2D-doubly linked list. Row headers (i.e. the
RxCxVx
cells in the first column) are represented byPossibility
s. Column headers (i.e. the cells in the first row) are represented byObjective
s. Rows and columns are connected by links, which represent the 1s in the matrix. Each link is connected up and down to the other '1s' that satisfy that objective, and connected left and right to the other '1s' that are present for that possibility.In addition, SudokuSpice's implementation extends the matrix to a larger graph to enable more complicated constraints. These use
OptionalObjective
s to groupPossibility
s and/or otherOptionalObjective
s. More details can be found in theExactCoverGraph
andOptionalObjective
docs. TheMagicSquaresConstraint
demonstrates how to use these optional objectives to implement a complicated constraint.The constraint-based solver uses constraints instead of rules. It does not provide a separate heuristics concept because the objectives inherently provide the
UniqueIn*
heuristics. Adding additional layers of heuristics would add complexity with minimal, if any, performance improvement.
For more information on extending SudokuSpice, see:
Non-unique (i.e. duplicate) values
What if you need to solve puzzles that allow multiple instances of the same value in a given region? For example, let's say that your puzzle contains the first 9 digits of Pi in each region:
3.14159265 -> 1, 1, 2, 3, 4, 5, 5, 6, 9
This is currently only supported by the rule-based solver. When constructing a Puzzle
, you can
also include the possible values for any given region:
var puzzle = new Puzzle(data, new int[] {1, 1, 2, 3, 4, 5, 5, 6, 9 });
This will be used to calculate the IPuzzle.CountPerUniqueValue
dictionary, and rules can use that
to properly enforce the correct number of values. The MaxCountPer* rules are provided for the
simple case that each box, column, or row needs to contain each value up to the max count as
specified in the CountPerUniqueValue
dictionary.
Namespaces
- SudokuSpice: Contains base classes for solving and generating puzzles.
- SudokuSpice.RuleBased: Contains classes for rule-based puzzle-solving and -generating.
- SudokuSpice.RuleBased.Heuristics: Contains standard heuristics and interfaces for creating custom heuristics.
- SudokuSpice.RuleBased.Rules: Contains rules and interfaces for creating custom rules.
- SudokuSpice.ConstraintBased: Contains classes for constraint-based puzzle-solving and -generating.
- SudokuSpice.ConstraintBased.Constraints: Contains standard constraints and the
IConstraint
interface.