Crate sudoku_variants

This crate implements an easy-to-understand and flexible Sudoku engine. It supports the following key features:

• Parsing and printing Sudoku
• Checking validity of Sudoku and solutions according to standard rules as well as some common variants
• Injection of custom constraints
• Solving Sudoku using a perfect backtracking algorithm
• Generating Sudoku with a possibility to specify a custom solver that has to be able to solve the result, thus controlling the difficulty

Note in this introduction we will mostly be using 4x4 Sudoku due to their simpler nature. These are divided in 4 2x2 blocks, each with the digits 1 to 4, just like each row and column.

Parsing and printing Sudoku

See SudokuGrid::parse for the exact format of a Sudoku code.

Codes can be used to exchange Sudoku, while pretty prints can be used to display a Sudoku in a clearer manner. An example of how to parse and display a Sudoku grid is provided below.

use sudoku_variants::SudokuGrid;

let grid =
    SudokuGrid::parse("2x2;2, ,3, , ,1, , ,1, , ,4, ,2, ,3").unwrap();
println!("{}", grid);

Checking validity of Sudoku

To check validity, an instance of Sudoku not only contains the numbers (stored in a SudokuGrid), but also some constraint which specifies the rules. For classic Sudoku rules, DefaultConstraint can be used.

It is possible to check an entire Sudoku, individual cells, or potential changes to individual cells that do not require changing the Sudoku’s state. An example of the former is provided below.

use sudoku_variants::Sudoku;
use sudoku_variants::constraint::DefaultConstraint;

// Some Sudoku for which it is totally unclear whether it is valid.
let sudoku = Sudoku::parse("2x2;1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1",
    DefaultConstraint).unwrap();
assert!(!sudoku.is_valid());

If you are developing an app that gives feedback to the user, it may be desirable to specify where they made an error. Also, sometimes checking the entire Sudoku is redundant, since only one cell has changed. To do this, it is possible to check the validity of just one cell in the grid.

use sudoku_variants::Sudoku;
use sudoku_variants::constraint::DefaultConstraint;

// A riddle posed by our app:
// ╔═══╤═══╦═══╤═══╗
// ║   │   ║   │ 4 ║
// ╟───┼───╫───┼───╢
// ║   │ 4 ║ 3 │   ║
// ╠═══╪═══╬═══╪═══╣
// ║   │ 3 ║   │   ║
// ╟───┼───╫───┼───╢
// ║   │   ║ 1 │   ║
// ╚═══╧═══╩═══╧═══╝
let mut sudoku = Sudoku::parse("2x2; , , ,4, ,4,3, , ,3, , , , ,1, ",
    DefaultConstraint).unwrap();

// Some (unfortunatly wrong) user input to the top-left cell
sudoku.grid_mut().set_cell(0, 0, 4);
assert!(!sudoku.is_valid_cell(0, 0).unwrap());

Similarly, it is also possible to check a singular cell with a potntial new entry, before changing the Sudoku, using Sudoku::is_valid_number. Since it otherwise behaves just like the example above, we will not provide another example.

All examples above have been using the DefaultConstraint, which is actually a composition of RowConstraint, ColumnConstraint, and BlockConstraint. Additionally to those three primitives, a few more common Sudoku variants’ rules are provided, which can be combined into more exciting rule sets. Check out the constraint module for more details and instructions on how to write your own rules.

Solving Sudoku

This crate offers a Solver trait for structs that can totally or partially solve Sudoku (that is, able to solve every Sudoku with a unique solution or not). As a default implementation, BacktrackingSolver is provided, which can solve every uniquely solveable Sudoku.

To use it, first instantiate a Sudoku an then call Solver.solve on a backtracking solver (as it is a zero-sized struct, no instantiation is required).

use sudoku_variants::{Sudoku, SudokuGrid};
use sudoku_variants::constraint::DefaultConstraint;
use sudoku_variants::solver::{BacktrackingSolver, Solution, Solver};

// The same Sudoku as in our previous example.
let sudoku = Sudoku::parse("2x2; , , ,4, ,4,3, , ,3, , , , ,1, ",
    DefaultConstraint).unwrap();
let solution = BacktrackingSolver.solve(&sudoku);

// The solution we expect:
// ╔═══╤═══╦═══╤═══╗
// ║ 3 │ 1 ║ 2 │ 4 ║
// ╟───┼───╫───┼───╢
// ║ 2 │ 4 ║ 3 │ 1 ║
// ╠═══╪═══╬═══╪═══╣
// ║ 1 │ 3 ║ 4 │ 2 ║
// ╟───┼───╫───┼───╢
// ║ 4 │ 2 ║ 1 │ 3 ║
// ╚═══╧═══╩═══╧═══╝
let expected_solution_grid =
    SudokuGrid::parse("2x2;3,1,2,4,2,4,3,1,1,3,4,2,4,2,1,3").unwrap();

assert_eq!(Solution::Unique(expected_solution_grid), solution);

The backtracking solver can deal with any (correctly implemented) constraint and type of Sudoku. If there is no solution, it will return Solution::Impossible and if there are multiple solutions, it will reutrn Solution::Ambiguous.

Performance improvements

Using pure backtracking can be an issue regarding performance. It is possible to use heuristics, so-called Strategies that use logic to fill some cells or remove some optinos. This can be much faster than pure backtracking, but some experimentation is required. See the strategy module for further information.

Generating Sudoku

Probably the most interesting feature of this crate is the generation of random Sudoku. This is done in two steps: generating a full grid using a Generator and then removing as many clues as possible using a Reducer.

The generator needs a solver, which helps to reduce the search space for valid grids, and a random number generator, for which we use the Rng trait from the rand crate. The reducer needs the same, however its solver is used to define the difficulty. Essentially, the reducer will generate a puzzle that is just not too hard for the given solver, that is, if one more clue were removed, the solver would be unable to solve it. An example of generating a minimal puzzle (where no clues can be removed without losing uniqueness) is provided below.

use sudoku_variants::constraint::DefaultConstraint;
use sudoku_variants::generator::{Generator, Reducer};
use sudoku_variants::solver::{BacktrackingSolver, Solution, Solver};

// new_default yields a generator/reducer with a backtracking solver and
// rand::thread_rng()
let mut generator = Generator::new_default();
let mut reducer = Reducer::new_default();

// Generate a full, 3x3 block Sudoku board with default rules.
let mut sudoku = generator.generate(3, 3, DefaultConstraint).unwrap();
assert!(sudoku.is_valid());

// Remove as many clues as possible
reducer.reduce(&mut sudoku);

let unique = match BacktrackingSolver.solve(&sudoku) {
    Solution::Unique(_) => true,
    _ => false
};
assert!(unique);

Defining a difficulty

The above example removes digits as long as the resulting Sudoku is still uniquely solveable. This may result in some very difficult Sudoku, since it provides no guarantees as to how the Sudoku can be solved. To generate less difficult Sudoku, you can provide a less powerful Solver, which has to be able to solve the reduced Sudoku. See the strategy module for further information.

Note regarding performance

While generating ordinary, minimal Sudoku with this crate is doable within a few seconds, more complicated rule sets which result in less necessary clues or larger boards may result in performance issues. In any case, it is strongly recommended to use at least opt-level = 2 for approximately a 28-fold performance improvement, even in tests that use Sudoku generation.

Modules

constraint	This module defines constraints which can be applied tu Sudoku grids, thus specifying the rules of the puzzle.
error	This module contains some error and result definitions used in this crate.
generator	This module contains logic for generating random Sudoku.
solver	This module contains the logic for solving Sudoku.
util	This module contains utility functionality needed for this crate. Most prominently, it contains the definition of the USizeSet used for storing cell options for strategies.

Macros

set	Creates a new USizeSet that contains the specified elements. First, the minimum and maximum values must be specified. Then, after a semicolon, a comma-separated list of the contained values must be provided. For empty sets, [USizeSet.new()] can be used.

Structs

Sudoku	A Sudoku represents a grid of numbers with an associated constraint. The numbers may or may not fulfill the constraint, but there is a method to check it.
SudokuGrid	A Sudoku grid is composed of cells that are organized into blocks of a given width and height in a way that makes the entire grid a square. Consequently, the number of blocks in a row is equal to the block height and vice versa. Each cell may or may not be occupied by a number.