4 ms·
Trying to grok this. Seems like it's not producing a solution, but instead producing a set of possible digits that can be put into each of the 81 squares. This
by lpolovets 17y ago
Trying to grok this. Seems like it's not producing a solution, but instead producing a set of possible digits that can be put into each of the 81 squares. This output is then piped to Dance, which is presumably an implementation of http://en.wikipedia.org/wiki/Dancing_links http://en.wikipedia.org/wiki/Dancing_links . Can someone confirm?
I love the idea of transforming Sudoku to another problem that already has a good solution instead of trying to attack it from scratch.
- jey 17y agoI haven't tried it, but it looks like you're right.
- nkurz 17y agoI think that's correct. Presumably this is the Dance he refers to: http://www-cs-faculty.stanford.edu/~uno/programs/dance.w http://www-cs-faculty.stanford.edu/~uno/programs/dance.w
- mark_h 17y agoHis paper on dancing links is a delight of a read, too. Highly recommended.
- voidpointer 17y agoThere's also a video lecture at Stanford in which Knuth explains DLX. http://stanford-online.stanford.edu/seminars/knuth/000222-knuth-100.asx http://stanford-online.stanford.edu/seminars/knuth/000222-kn...
- mark_h 17y agoExcellent, thanks for pointing that out! I hadn't seen that.
- michael_dorfman 17y agoSudoku is pretty clearly an "exact cover" problem, and there are loads of known ways to attack those; Knuth's DLX being a particularly elegant one. As a general principal, it's always a good idea to see if the problem you are facing resembles other known, solved problems.
- eru 17y agoLinear integer programming approaches also work well.
- ash 17y agoBram Cohen came up with another transformation of Sudoku - to SAT problem: http://news.ycombinator.com/item?id=873073 http://news.ycombinator.com/item?id=873073
- dons 17y agoIndeed, turning sudoku into a SAT problem is how the Cryptol solution works (using the languages SAT checking tools) http://www.galois.com/blog/2009/03/18/solving-sudoku-using-cryptol/ http://www.galois.com/blog/2009/03/18/solving-sudoku-using-c...