Daily Archives: 3/15/2007

Don Knuth’s Dancing Links and Algorithm X

Tom does probably as much if not as more code tinkering as I do, and his is probably more interesting. At lunch today he mentioned that he implemented Knuth’s Algorithm X for solving the exact cover problem. I couldn’t remember what that was, but I did recall it was related to Knuth’s Dancing Links, which I know my friend Jeff had implemented before as part of his exploration of polyominoes, but I didn’t recall what it was about either. So, to help me, I dug out the link below, which I’ll share with y’all.

Link to the pdf.

Technorati Tags: , , ,