Knuth on Sudoku | Hacker News Reader

Knuth on Sudoku

www-cs-faculty.stanford.edu

66 pointssublemonic24 comments

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 . 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.

I haven't tried it, but it looks like you're right.

I think that's correct. Presumably this is the Dance he refers to: http://www-cs-faculty.stanford.edu/~uno/programs/dance.w

His paper on dancing links is a delight of a read, too. Highly recommended.

There's also a video lecture at Stanford in which Knuth explains DLX. http://stanford-online.stanford.edu/seminars/knuth/000222-kn...

Excellent, thanks for pointing that out! I hadn't seen that.

Sudoku 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.

Linear integer programming approaches also work well.

Bram Cohen came up with another transformation of Sudoku - to SAT problem:

http://news.ycombinator.com/item?id=873073

Indeed, 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-c...

There is also a wonderful article by Peter Norvig http://norvig.com/sudoku.html with 100-line solver in Python.

The fact that it is in 100 lines really doesn't matter. The particular way that python made his implementation small is interesting though.

Here's a PDF version, via Google Docs: https://docs.google.com/fileview?id=0B1njwImQ2AsFOGRjYmRmYWI...

And a C version: http://gist.github.com/319391

> 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.

The 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.

Only problem - that ain't C. ;)

Oh? What language is it? At first glance it looked like C.

It's CWEB (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/)

I assume this is what CTANGLE produces, in which case your rebuttal of unwind's point is flawed.

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.

I 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.

That's K&R C:

http://en.wikipedia.org/wiki/K%26R_C#K.26R_C

For a tutorial on solving sudoku using Dancing Links, see this tutorial: http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

I find this a bit hard to read. Can somebody render this CWEB(?) file to HTML or PDF for the lazier of us?

That's so quaint that he uses the "register" storage class. Knuth is awesome

Reply on news.ycombinator.com