4 ms·
Knuth on Sudoku
- lpolovets 17y agoTrying 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...
- habitue 17y agoThat's so quaint that he uses the "register" storage class. Knuth is awesome
- vl 17y agoThere is also a wonderful article by Peter Norvig http://norvig.com/sudoku.html http://norvig.com/sudoku.html with 100-line solver in Python.
- icefox 17y agoThe fact that it is in 100 lines really doesn't matter. The particular way that python made his implementation small is interesting though.
- unwind 17y agoThe comp.lang.c FAQ (which is quite well respected as a good authorative source on C, I think) states: Q: What's the correct declaration of main()? A: There are two valid declarations: int main(void) int main(int argc, char **argv) Yet, Knuth states: main() This feels like Knuth has done a Chuck Norris on C.
- jsharpe 17y agoOnly problem - that ain't C. ;)
- X-Istence 17y agoOh? What language is it? At first glance it looked like C.
- voidpointer 17y agoIt's CWEB (http://www-cs-faculty.stanford.edu/~uno/cweb.html http://www-cs-faculty.stanford.edu/~uno/cweb.html) A language based on C devised by Knuth as a language for "Literate Programming" (http://www.literateprogramming.com/ http://www.literateprogramming.com/)
- jedbrown 17y agoI assume this is what CTANGLE produces, in which case your rebuttal of unwind's point is flawed. http://gist.github.com/319391 http://gist.github.com/319391 However, C99 section 6.9.1 "Function definitions" asserts that int f(void) { /* ... */ } is equivalent to int f() { /* ... */ } Note that this is not true of a function declaration since int f(); means function accepting unspecified arguments.
- niyazpk 17y agoI haven't done any C programming for years, so correct me if I am wrong. IIRC main() is interpreted as int main() by some compilers.
- wheels 17y ago
- snprbob86 17y agoI find this a bit hard to read. Can somebody render this CWEB(?) file to HTML or PDF for the lazier of us?
- nex3 17y agoHere's a PDF version, via Google Docs: https://docs.google.com/fileview?id=0B1njwImQ2AsFOGRjYmRmYWItMTJkMy00Yjc1LTkzMTgtNWRmOWJlMzY2YjM5&hl=en https://docs.google.com/fileview?id=0B1njwImQ2AsFOGRjYmRmYWI... And a C version: http://gist.github.com/319391 http://gist.github.com/319391
- apgwoz 17y ago> And a C version I don't mean to be rude, or mean or anything, since you did take the time to extract it and make a gist out of it, but you could have kept the formatting.
- s-phi-nl 17y agoFor a tutorial on solving sudoku using Dancing Links, see this tutorial: http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/ http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/