gareth_rees ([info]gareth_rees) wrote,
@ 2008-01-10 21:50:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Knuth is 70

Donald E. Knuth is 70 years old today.

There are nice posts about him from Luca Trevisan, Scott Aaronson, and David Eppstein.

I’ll add my own piece to the festivities by referring you to my article on the generation of sudoku puzzles for Zoonami’s video game Zendoku. The puzzle generation runs as quickly as it does thanks to Knuth’s “Dancing Links” technique for implementing a backtracking solution to an exact cover problem.

“Covering” a column in Knuth’s “Dancing Links”

“Covering” the leftmost column in the Dancing Links implementation of Algorithm X.

(4 comments) - (Post a new comment)


[info]gjm11
2008-01-11 02:22 am UTC (link)
Nice article.

(Reply to this)


[info]gjm11
2008-01-11 02:22 am UTC (link)
Your dancing links link is broken, though.

(Reply to this) (Thread)

[info]gareth_rees
2008-01-11 12:03 pm UTC (link)
Fixed.

(Reply to this) (Parent)

[info]nickbarnes
2008-01-11 11:04 am UTC (link)
A festschrift, how splendid and appropriate.

(Reply to this)

(4 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…