Sudoku solver

This project brings together my passion for Sudoku and my desire to learn a new programming language - Rust. Despite my initial unfamiliarity, I discovered that Rust is not only powerful and exceptionally fast but also really enjoyable to program in.

Strategy

On the algorithmics side, the solver uses optimized backtracking to progressively solve grids. It keeps track of all empty cells and makes use of bitmasks to instantly fetch all the possible candidates for a each cell.

It also uses the MRV (Minimum Remaining Values) heuristic which prioritizes selecting the cells with fewer candidates first, greatly reducing the number of possibilities that need to be explored in the search tree. With some optimizations such as pruning early if there are 0 candidates remaining for a cell or selecting the first cell with exactly 1 candidate, MRV proves to be an improvement in all cases.

Using multithreading is a no-brainer when it comes to large inputs that can easily be parallelized. But because the performance increase doesn't come from a direct optimization in the code itself, some may consider it cheaty. That's why I defaulted to a single thread and only added multithreading as an option.

Implementation

Rust makes it really easy to treat all errors and assure no undefined behavior, while keeping everything fast. The performance drop was insignificant after implementing strict validations, proper error handling and command line option parsing on top of the fast algorithm. Using crates was also a very convenient decision here, because the project isn't focused on implementing everything from scratch.

Key features:

• Error handling with explicit messages - anyhow
• Simple parallelism - rayon
• Buffered IO operations
• Runtime statistics
• Formatted output
• Progress bars for solving and writing output - indicatif
• Command line options for flexible conguration - clap

Benchmarks

There are 4 main datasets I used for benchmarking: easy, medium, hard and 17 clues.

The following benchmarks were generated with the help of hyperfine. The solver was ran 10 times on each dataset with the --no-progress option (because it's slightly faster).

Raw data

Dataset	Single thread	Multithreading
Easy	622.878	4.776.029
Medium	540.866	3.853.361
Hard	81.707	560.216
17 clues	1.110	7.508

Input format

Each grid has to be in the following format:

• Must be a string with length 81
• Must use '0' to denote empty cells and digits from '1' to '9' for cells that are already solved
• Must be a valid sudoku puzzle with at least one solution

Example: 004300209005009001070060043006002087190007400050083000600000105003508690042910300

Options

The solver accepts several command-line arguments:

Option	Short	Description
--input-file <INPUT_FILE>	-i	Path to input file containing grids
--output-file <OUTPUT_FILE>	-o	Path to output file for writing results
--single <GRID>	-s	Pass a single grid directly
--multithreading [<THREAD_COUNT>]	-m	Use multithreading (uses all CPUs if value not specified)
--max-grids <MAX_GRIDS>	-g	Maximum number of grids to solve (solves all if not specified)
--format	-f	Write results in human-readable format
--no-stats		Hide stats (execution time and average grids/second)
--no-progress		Hide progress bar
--help	-h	Print help

Examples:

# Solves grids from a file using 4 threads and writes formatted output
./sudoku-solver -i example.txt -o output.txt -m 4 -f

# Limits grids to 10 and doesn't print a progress bar
./sudoku-solver -i example.txt -g 10 --no-progress
 
# Solves a single grid directly
./sudoku-solver -s "000000000000000001000002030000003020001040000005000060030000004070080009620007000" 

Quick start

1. Clone the repository

git clone https://github.com/alex-croitoriu/Sudoku-Solver.git
cd Sudoku-Solver

2. Build the release version

cargo build --release

3. Run the executable

./target/release/sudoku-solver -i example.txt