Module sudoku_variants::constraint

This module defines constraints which can be applied tu Sudoku grids, thus specifying the rules of the puzzle.

Besides the definition of the Constraint trait, this crate contains some predefined constraint for default Sudoku rules and some variants. We will cover them first and afterwards show how to implement a custom constraint.

Default Sudoku rules

To get the default Sudoku rules, DefaultConstraint can be used. Conceptually, it is a conjunction of RowConstraint, ColumnConstraint, and BlockConstraint.

Variants

Besides the default rules, sudoku-variants also offers some pre-defined variantions. As an example, we will use the DiagonalsConstraint, which requires that the two diagonals, top-left to bottom-right and top-right to bottom-left, do not contain duplicate digits, just like each row, column, and block in standard Sudoku.

Normally, one wants to apply a DiagonalsConstraint and a DefaultConstraint. This can be done in two ways: using a CompositeConstraint and using a DynamicConstraint. The first is type-checked over two parameter types, which both need to be constraints. It is provided one instance of each type, and is defined to be fulfilled if both instances are fulfilled. In contrast, the DynamicConstraint uses a vector of trait objects and is fulfilled if all entries are fulfilled. This enables a more flexible design and is less cumbersome, especially when combining more than two constraints, but comes at a runtime cost due to dynamic dispatch.

To define our combination of default- and diagonals-constraints, we can write the following code:

use sudoku_variants::constraint::{
    CompositeConstraint,
    DefaultConstraint,
    DiagonalsConstraint,
    DynamicConstraint
};

// Option 1: CompositeConstraint
let c1 = CompositeConstraint::new(DefaultConstraint, DiagonalsConstraint);

// Option 2: DynamicConstraint
let c2 = DynamicConstraint::with_children(vec![
    Box::new(DefaultConstraint),
    Box::new(DiagonalsConstraint)
]);

Custom constraints

When implementing a constraint, it is usually sufficient to implement Constraint::check_number and Constraint::get_groups. All other methods are default-implemented. However, the performance of Constraint::check could be improved by a specialized implementation, since by default it calls check_number for every cell.

As an example of an implementation of a custom constraint, we will look at the source code of a subset of the DiagonalsConstraint, which we call MainDiagonalConstraint. It only checks the diagonal from the top-left to the bottom-right corner of the Sudoku.

use sudoku_variants::SudokuGrid;
use sudoku_variants::constraint::{Constraint, Group};

#[derive(Clone)]
struct MainDiagonalConstraint;

impl Constraint for MainDiagonalConstraint {
    fn check_number(&self, grid: &SudokuGrid, column: usize, row: usize,
            number: usize) -> bool {
        // For all cells on the diagonal, the column index is equal to the
        // row index. All other cells don't interact with this constraint,
        // so we return true, indicating that they don't violate it.
        if column == row {
            let size = grid.size();

            for i in 0..size {
                // Since column == row, if i == column we are looking at
                // the checked cell itself, which may contain the number.
                if i != column &&
                        grid.has_number(i, i, number).unwrap() {
                    return false;
                }
            }
        }

        true
    }

    fn get_groups(&self, grid: &SudokuGrid) -> Vec<Group> {
        // There is one group in this case: the main diagonal.
        let size = grid.size();
        let mut group = Group::new();

        for i in 0..size {
            group.push((i, i));
        }

        vec![ group ]
    }
}

Deriving Clone is important, since occasionally Sudoku need to be cloned. Sudoku therefore implements Clone, which requires its constraint to be cloneable aswell. Note that Clone is not required by the Constraint trait, since that would make it impossible to create Constraint-trait objects, which are used in the DynamicConstraint. Instead, CloneConstraint, which clones a trait object, is required for elements of a DynamicConstraint. However, if you derive Clone, you do not need to worry about CloneConstraint, since it is implemented for every constraint that implements Clone by default.

Structs

AdjacentConsecutiveConstraint	A RelativeCellConstraint that excludes consecutive digits in orthogonally adjacent cells. As a visualization, the cells marked with ‘X’ in the following grid are excluded from being a 2 or a 4:
BlockConstraint	A Constraint that there are no duplicates in each block.
ColumnConstraint	A Constraint that there are no duplicates in each column.
CompositeConstraint	A Constraint which simultaneously enforces two other constraints. This allows the construction of complex constraints by nesting composite constraints.
DefaultConstraint	The default Sudoku Constraint which is a logical conjunction of RowConstraint, ColumnConstraint, and BlockConstraint.
DiagonallyAdjacentConstraint	A RelativeCellConstraint that excludes duplicates in a diagonally adjacent cell to the reference cell. If normal Sudoku rules apply, this is equivalent to a KingsMoveConstraint.
DiagonalsConstraint	A Constraint which checks that there are no duplicates in each of the two diagonals ( ╲ and ╱ ).
DynamicConstraint	A Constraint that contains a vector of trait objects representing constraints and verifies all of them. This is more flexible than a CompositeConstraint, but also less efficient, since it needs dynamic dispatch.
KingsMoveConstraint	A RelativeCellConstraint that excludes duplicates a Chess-Kings’s move away from the reference cell (orthogonally or diagonally adjacent). Note that some checks performed by this constraint are redundant if standard Sudoku rules apply, since orthogonally adjacent cells are either in the same row or column as the reference cell. In that case, using the DiagonallyAdjacentConstraint is more efficient and has the same effect.
KnightsMoveConstraint	A RelativeCellConstraint that excludes duplicates a Chess-Knight’s move away from the reference cell.
RowConstraint	A Constraint that there are no duplicates in each row.

Traits

CloneConstraint	A trait for cloneable Constraints which is used in the DynamicConstraint to clone trait objects. Normally a user should not have to implement this trait manually, as it is automatically implemented for all Constraints that implement Clone (and have static lifetime).
Constraint	A constraint defines some property on a Sudoku grid. These are essentially the rules of the Sudoku. In standard Sudoku these are “No duplicates in a row” (RowConstraint), “No duplicates in a column” (ColumnConstraint), and “No duplicates in a block” (BlockConstraint). Here, however, the design is more flexible to allow for custom constraints.
RelativeCellConstraint	A trait for Constraints that are defined by having no forbidden numbers in some relative configuration to the reference cell. Whether a number is forbidden is defined by RelativeCellConstraint::is_forbidden, which is a boolean relation between the reference cell and the other cell. By default, this checks for equality.

Type Definitions

Group

A group of cells, represented by a vector of their coordinates in the form (column, row).