4 ms·

There is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks https://github.com/t-dillon/tdo

There is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks https://github.com/t-dillon/tdoku/tree/master/benchmarks How fast they are depends on the difficulty of the sudoku and on your machine, but it's typically a few thousand/s on the hardest known and several 100k/s to a million/s on very easy.

53x15 7y ago
I'm the author of Tdoku and maintainer of those benchmarks. If anyone has a well optimized DLX implementation I'd love to add it to the comparison. The few I've sampled from github were not competitive, but I have no idea how much effort when into them. This page from 2011 has some comparisons of backtracking and DLX solvers from that era, but it would be interesting to update: https://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/ https://attractivechaos.wordpress.com/2011/06/19/an-incomple...
- CJefferson 7y ago
  Thanks, it's nice to have something to point to about DLX, other than "mine was slow".
- OskarS 7y ago
  Seems pretty competitive to me if the third fastest in your benchmark uses dancing links. I do think it's probably true that dancing links wont be literally the fastest, but the neat thing is that it's a generic algorithm that solves ALL total cover problems, not just Sudoku. Of course a tuned Sudoku solver could probably beat it (optimizing around the Sudoku-specific parts), but it's nice to see that it's at least in the running.
  - 53x15 7y ago
    Bear in mind that JSolve was 5x faster than the fastest DLX solver in the attractivechaos 2011 benchmarks, and today there are several solvers that are 2x faster than JSolve (https://github.com/t-dillon/tdoku/tree/master/benchmarks https://github.com/t-dillon/tdoku/tree/master/benchmarks). If the difference is really an order of magnitude, that's pretty non-competitive. I certainly don't mean do disparage DLX. It's a powerful and general algorithm. But if you need a fast Sudoku solver (for puzzle mining or studying Sudoku research questions) then it's not the tool I'd reach for. The backtracking solvers just get a lot of mileage out of tuning their representation to play nicely with hardware. They also blow general purpose CDCL SAT solvers out of the water, at least for 9x9 Sudoku.
sjaak 7y ago
I see, do those solvers explore the entire solution space to also validate that a puzzle has exactly 1 solution? That's one of the cool things about a dlx solver: it can do that while still being very fast.
- emerent 7y ago
  All of them do.

53x15 7y ago

I'm the author of Tdoku and maintainer of those benchmarks. If anyone has a well optimized DLX implementation I'd love to add it to the comparison. The few I've sampled from github were not competitive, but I have no idea how much effort when into them. This page from 2011 has some comparisons of backtracking and DLX solvers from that era, but it would be interesting to update: https://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/ https://attractivechaos.wordpress.com/2011/06/19/an-incomple...

CJefferson 7y ago
Thanks, it's nice to have something to point to about DLX, other than "mine was slow".
OskarS 7y ago
Seems pretty competitive to me if the third fastest in your benchmark uses dancing links. I do think it's probably true that dancing links wont be literally the fastest, but the neat thing is that it's a generic algorithm that solves ALL total cover problems, not just Sudoku. Of course a tuned Sudoku solver could probably beat it (optimizing around the Sudoku-specific parts), but it's nice to see that it's at least in the running.
- 53x15 7y ago
  Bear in mind that JSolve was 5x faster than the fastest DLX solver in the attractivechaos 2011 benchmarks, and today there are several solvers that are 2x faster than JSolve (https://github.com/t-dillon/tdoku/tree/master/benchmarks https://github.com/t-dillon/tdoku/tree/master/benchmarks). If the difference is really an order of magnitude, that's pretty non-competitive. I certainly don't mean do disparage DLX. It's a powerful and general algorithm. But if you need a fast Sudoku solver (for puzzle mining or studying Sudoku research questions) then it's not the tool I'd reach for. The backtracking solvers just get a lot of mileage out of tuning their representation to play nicely with hardware. They also blow general purpose CDCL SAT solvers out of the water, at least for 9x9 Sudoku.

sjaak 7y ago

I see, do those solvers explore the entire solution space to also validate that a puzzle has exactly 1 solution? That's one of the cool things about a dlx solver: it can do that while still being very fast.

emerent 7y ago
All of them do.