Don Knuth’s Dancing Links and Algorithm X

March 15, 2007 | General | By: Mark VandeWettering

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.

[tags]Don Knuth, Programming, Exact Cover, Polyominoes[/tags]

Comments

Comment from Jeff
Time 3/15/2007 at 2:08 pm

Dancing links is just a simple way of removing an item from a doubly linked list, and then putting it back. Algorithm X uses such lists to solve the exact cover problem, removing things from the lists as it builds a possible solution, and putting them back as it backtracks. Dancing Links reduces the overhead of backtracking considerably. I implemented Algorithm X as described in the Dancing Links paper and used it to solve several kinds of polyomino problems. An opportunity to impress ones friends with sheer computing power shouldn’t be wasted. Fun Stuff. 🙂

Comment from Steve VanDevender
Time 3/15/2007 at 4:20 pm

“Algorithm X” can also be applied to solve Sudoku puzzles algorithmically.

http://www.bluechromis.com/stan/sudoku.html

Comment from ememheatLew
Time 3/2/2008 at 6:02 am

Hello,

I pine for to buy Dedicated Server with harsh DDoS charge in Europe.

Anybody be familiar with is there any punctilious dedicated servers with ddos protection against HTTP and SYN inundation attacks?

Our server has been stodgy attacked, and i am looking for reliable ddos protected hosting in Europe.

For now I only got recommendation for Dragonara.net

Comment from smakboock
Time 10/19/2008 at 3:22 am

Hi people!
The interesting name of a site – brainwagon.org
I today 0 hours
looked in a network So I have found your site 🙂
The interesting site but does not suffice several sections!
However this section is very necessary!
Best wishes for you!
Forgive I is drunk :))