4 ms·

Why is 1ms impressive? How much time does a simple solver take?

• pdonis 5y ago
  The solution time can vary quite a bit depending on the difficulty of the puzzle. 1 ms for a single puzzle for a program written in C could actually be fairly slow for an easy puzzle, but would be quite fast for a hard puzzle. (It would also depend, of course, on how fast a CPU and how much memory was being used to run the program.)
• 53x15 5y ago
  For a casual effort this solver is quite fast. On most datasets it's significantly faster than a C++ port of the Norvig solver and it's often in the same league as well-tuned DLX solvers (though still not in the major league). Relative to DLX it's faster on the easiest puzzles and slower on hard ones, though its performance degrades significantly in two specific still-easy cases: (1) 17-clue puzzles since these punish solvers that don't propagate hidden singles, (2) 0-solution puzzles since the solver doesn't check for consistency during initialization (something the author acknowledges in a comment). For context see these benchmarks from a modern laptop (https://github.com/t-dillon/tdoku/blob/master/benchmarks/results_i7-1065G7/best_results.txt https://github.com/t-dillon/tdoku/blob/master/benchmarks/res...) and compare lhl_sudoku to the other simple solvers tdev_basic_heuristic, zerodoku, fast_solv_9r2, kudoku, and norvig. For details on the solvers and datasets used in these benchmarks see here (https://github.com/t-dillon/tdoku/tree/master/other https://github.com/t-dillon/tdoku/tree/master/other) and here (https://github.com/t-dillon/tdoku/tree/master/benchmarks https://github.com/t-dillon/tdoku/tree/master/benchmarks)