53x15

5 ms·

1.
by 53x15 4y ago
If the solution is unique then there is a logical path to it, though maybe not one feasible to discover for an agent with bounded time and (especially for humans) bounded working memory. Consider the search tree of a backtracking algorith
2.
by 53x15 4y ago
> A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. The number of minimal Sudoku puzzles is estimated (with 0.065% relative error
3.
by 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). Rel
4.
by 53x15 6y ago
I think neel_k was referring to the fact that when a DPLL or CDCL solver concludes UNSAT you can take the trace its backtracking activity and rewrite it from the bottom up as a resolution refutation. So in this sense the solvers are finding
5.
by 53x15 7y ago
Sudoku may be a poor example for illustrating some of the overarching points of this series of blog posts, which I take to be that modern SAT solvers are, as someone described them in a previous thread, "little diamonds of engineering&
6.
by 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&
7.
by 53x15 7y ago
This sounds like Crook's Algorithm ( https://www.ams.org/notices/200904/tx090400460p.pdf ), which is a perfectly reasonable thing to do, especially for pencil-and-paper puzzle solving since pigeonhole inference
8.
by 53x15 7y ago
It's easy to see why this puzzle has no solution. Looking at columns 4-6 we see that none of the digits 1,5,6 can occur in cells G4,H4,I4 or G6,H6,I6. So some permutation of these digits occupies G5,H5,I5 and all digits other than 1,5,
9.
by 53x15 7y ago
It can be done with just depth first search, but if you want it to be fast you can go pretty far down the rabbit hole. The details of your representation, your heuristics, and the kinds of constraint propagation you support all matter a l
10.
by 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