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:

  1. The IPuzzle

    Puzzles store the underlying Sudoku data. You likely only need the standard implementations, Puzzle for constraint-based tools, and PuzzleWithPossibleValues 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.

  2. The IRule

    Rules define - you guessed it - the rules for a puzzle. For example, standard Sudokus use the RowUniquenessRule, the ColumnUniquenessRule, and the BoxUniquenessRule. For convenience and efficiency, these come prepackaged in the StandardRules class. Rules do not directly modify the IPuzzle or its possible values themselves. They should use an IReadOnlyPuzzle 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. The DynamicRuleKeeper 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.

  3. 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 the UniqueInRowHeuristic. Heuristics can either be perfect heuristics, i.e. they reduce squares to only one possible value (like the UniqueIn* 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.

  4. 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 by Possibilitys. Column headers (i.e. the cells in the first row) are represented by Objectives. 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 OptionalObjectives to group Possibilitys and/or other OptionalObjectives. More details can be found in the ExactCoverGraph and OptionalObjective docs. The MagicSquaresConstraint 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