An even faster implementation of the sudoku solver

[Gadiguibou]

I don't know if you're already aware of it, but an even faster sudoku solver exists (tdoku). Just wanted to let you know. Feel free to disregard if this isn't useful.

Link to GitHub repo

Link to the article that describes the algorithm

[Emerentius]

Yes, I am aware of tdoku. I helped tdillon with including this crate in his benchmarks (which are available here, btw).

As you can see there, it's the clear winner in the region of invalid sudokus (0 solutions and to a lesser degree, 2+ solutions) and hard sudokus, but it gets a bit murky outside of that depending on compiler and processor.

I'm unlikely to spend much time on further optimizations anyway (and I'd concentrate on the strategy solver), but if I were, then I'd first start by picking some specific use case to optimize for. For example, when searching for new sudokus (like in the pattern game), you may encounter a lot of easy and invalid sudokus that need to be filtered out. Hard sudokus are rarer, so a tradeoff that makes hard sudokus faster at the expense of easy ones may not be worth it. Without something like that, I'm not sure where I should be choosing the tradeoffs between easy and hard, valid and invalid sudokus.

[Gadiguibou]

That makes a lot of sense! Thanks for the detailed answer. :)