A simple and fast implementation of backtrack solving of Sudokus
The executable runs the solver on the hardest problem found so far. Which takes around 10s to solve.
cargo run -r
Tests checks whether it correctly solves a bunch of different sudokus.
cargo test
Benchmarks test how quickly a few sudokus are solved
cargo bench
This is a backtracking solver, see here for explanation on that part.
The most notable part is this code, found here:
pub fn candidates(&self, x: usize, y: usize) -> usize {
self.valid_ranks[y] & self.valid_files[x] & self.get_box(x, y)
}This gives for any square the valid values that can be placed there. It does so by finding the intersection between the valid values for rank, file, and the box.
Benchmarked on a AMD Ryzen 5 5600X 6-Core Processor × 6 with Criterion
The benchmarks can be seen here
Solves most Sudokus in a few micro seonds and does around 159 million state modifications each second.