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: , , ,

4 thoughts on “Don Knuth’s Dancing Links and Algorithm X

  1. Jeff

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

  2. ememheatLew

    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

  3. smakboock

    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 :))

Comments are closed.