When I posted my Javascript Sudoku solver earlier this month, I noted that it would be interesting to build a version that was optimized for speed. The original deliberately pauses every 1/100th of a second to update the screen and give your computer a chance to breathe.
In my experience, Javascript running at full speed for a long time tends to make browsers unresponsive. So the solver uses only about 3% of my laptop’s CPU power, and can take up to 5 minutes to solve a complicated puzzle. On the plus side, I think it does look nice, and it’s fast enough for any Sudoku you’ll find in puzzle books.
Trying Rust
I’d been wanting to try Rust for a while. It’s a modern programming language that is very different from other languages I use. And from what I’d heard, programs written in Rust were really fast.
So this seemed like the perfect thing to try and build as a first Rust project. I decided to do a CLI application that solves Sudokus using the same algorithm I used in Javascript, but with no visual output. Also, I’d not throttle it in any way to see how fast it was.
https://github.com/roytanck/sudoku-solver-rust
Please keep in mind that this was quite literally the first thing I ever wrote in Rust after “Hello, World!”. I’m probably not fully utilizing the language’s strengths, and yet it seems plenty fast to me already.
Testing
This is actually the same puzzle that took the Javascript version 5 minutes to solve. It’s designed to frustrate brute force solvers, but from the looks of it fails miserably at that :).
Since there’s a lot of randomness in the algorithm, solve times vary wildly, even with the same puzzle. But the 2ms in the screenshot isn’t even the fastest solve I’ve seen. Anything between 0(!) and 30 milliseconds is common, and the highest I’ve seen is ~90ms.
Currently, the CLI application uses 100% of a single CPU core. Rust does support multi-threading, but I’m not sure it would make much of a difference here.
Please note that this does not mean that Rust is 30,000 times faster than Javascript. The two programs are very different in what they aim to do. It does prove that on a reasonably fast computer, my algorithm can solve pretty much any Sudoku puzzle in a fraction of a second.
Update: Benchmarking
I decided to add a simple benchmarking option to the CLI program, that allows you to solve the same puzzle multiple time. I used the included puzzles and got some interesting results.
| Puzzle | Nr of solves | Time (mm:ss) | Avg. time |
|---|---|---|---|
| extreme.txt | 100,000 | 02:40 | 1.60 ms |
| unsolvable.txt | 10,000 | 29:35 | 177.50 ms |
| protected.txt | 1,000 | 08:43 | 523.10 ms |
(Update, Feb 11th, 2022: A bug caused the original benchmarking results to be wrong, so I updated these with new, correct values).
Update 2: Multi-threading
Since the only way to make this any faster was to use multiple CPU threads, I read up on multi-threading in Rust. That turned out to be relatively straightforward, so I added that. If I re-run the benchmarks with four threads, I get the following results.
| Puzzle | Nr of solves | Time (mm:ss) | Avg. time |
|---|---|---|---|
| extreme.txt | 100,000 | 01:00 | 0.60 ms |
| unsolvable.txt | 10,000 | 11:22 | 68.28 ms |
| protected.txt | 1,000 | 03:22 | 202.14 ms |
The Virtual Machine I’m using for Rust development has access to half of my laptop’s four cores and eight threads. So the best result is likely going to be achieved using four threads. As, expected, we’re seeing a 50%+ reduction in average solve times.
