Talk:Dancing Links

2005 merge discussion

This should not be merged with linked list as they are not the same thing. Linked list is the general name for a programming practice of creating nodes that are linked together, while dancing links is a method of iterating through the links, or so i can gather. 212.179.254.74 04:29, 24 September 2005

• I agree, this should not be merged with linked list. Dancing links is a way of removing elements from and re-inserting elements into a doubly-linked list, which is used in implementing an algorithm for trial-and-error searches for solutions to a problem. This article is about a different topic, and should be expanded on, but not merged. ralmin 20:37, 16 October 2005 (UTC)

• Don't merge. I understand linked lists and was looking for information of dancing links, so I have no interest in reading through the lengthy article on linked lists to.

• Don't merge. Whilst the Dancing Link exploits a particularly interesting characteristic of a category of linked list (the 4 way double linked list) that is the end of the similarity. This Dancing Link is an algorithm for solving a certain class of problem (exact cover problem) whereas a link list is a data structure. Those who want to learn about this algorithm will not want to trawl though lots of information on Linked Lists -- Andy Hedges

• Don't merge. Linked list is a data structure, whilst dancing links is an algorithm that exploits certain properties of a special type of linked list called doubly linked lists. These two are fundamentally different. Mangoshake 15:21, 11 November 2005 (UTC)

• Don't merge. The above positions say it all. --asmodai 11:16, 12 November 2005 (UTC)

Dancing links and Algorithm X

I've read Knuth's paper, and in its current state, this article discusses two aspects:

Knuth's Algorithm X (vaguely) Converting a Sudoku board for use by Algorithm X

The only place in this article where Dancing Links are correctly referred to is where it states that Dancing Links is an algorithm using linked lists. Overall this article is grossly misleading. Read Knuth's paper (linked from the article) to see what I'm talking about.

I think I'll rewrite this even though I'm no expert on the subject; it certainly can't turn out worse.

... Done. The new Algorithm X page will show up... when wikipedia updates their database or whatever needs to happen.

Eneg 19:41, 5 January 2006 (UTC)

It seems to me that we're inventing the term "Algorithm X" for this page; is that true? That might not be the best idea (not doing original research, etc). Glasser 04:35, 8 January 2006 (UTC)

Glasser, please read the original article before making assertions like this. Eneg 19:32, 8 January 2006 (UTC)

You're right, it had been a while since I read the article and only remembered DLX. Sorry. Glasser 21:54, 12 January 2006 (UTC)

I've implemented this algorithm in ML (using only wiki and it didn't take very long...!) but it seems that the sentence "Finally, remove each column (...) in which the selected row has a 1" should also advise writers to remove rows in which the removed columns have a 1 as these rows cannot be in the solution 87.81.240.123 00:06, 19 January 2006 (UTC)

I've edited to clarify this point. --Syperk (talk) 23:13, 18 September 2011 (UTC)

Example needed

Would it be possible to get an example of how a Sudoku puzzle is represented by a matrix? I suppose I could try to figure it out and post it and see if it lasts.

• I think this is a good idea. But I think it makes the most sense to include this as part of a Sudoku example in the exact cover article. See my question/suggestion below about reorganizing related articles. --Rob Zako 17:37, 27 June 2006 (UTC)
• I have done this programmatically, and I should warn you that these matrices are kind of, erm, large. Ish. Shinobu 11:57, 22 November 2006 (UTC)
• Yes, the matrix is large. See the exact cover article for an abbreviated version of this matrix. --Rob Zako 07:31, 3 December 2006 (UTC)

Reorganize Exact cover, Algorithm X and Dancing Links articles?

The exact cover, Algorithm X and Dancing Links articles all discuss similar ideas. The exact cover problem is an NP-complete problem; Algorithm X is a brute-force algorithm that finds all solutions to the exact cover problem; and Dancing Links is a computer implementation of Algorithm X. These related topics have received a lot of interest recently because Dancing Links is the preferred technique for solving Sudoku puzzles quickly by computer. I suggest that all three topics be reoganized so that most of the information about concepts and examples is in the exact cover articles, with the other two articles focusing just on the particulars of the algorithm or the computer implementation. --Rob Zako 16:56, 27 June 2006 (UTC)

Note on the Perl example linked

While I'm flattered (the "Perl example" slide presentation linked was mine), that presentation has nothing at all to do with DLX/Algorithm-X. It was a much more general talk about solving Sudoku in Perl. However, I actually did write an article about using Algorithm-X to solve and generate Sudoku using exact cover in an issue of The Perl Review, a print magazine. I think that I replace the link to the slides with a reference to that print publication. Note, however that it only relates to the exact cover Sudoku solver component of Knuth's paper, and does not employ DLX in any way. 74.109.0.116 14:06, 9 January 2007 (UTC) (fishbot)

Slight adjustment of algorithm description needed

As the poster at IP 87.81.240.123 observed, it is necessary to finally remove every row containing a 1 in **any** of the columns that the chosen row contains a 1, to avoid conflict (i.e., multiple 1s in a column). Could someone change the text please? (Otherwise I will have a go myself in a few days...) —The preceding unsigned comment was added by 130.123.128.114 (talk) 07:29, 7 April 2007 (UTC).

I have also noticed the incorrect description in the "Exploring" section. I will be happy to reword this myself once I clarify my thoughts a little. Pauldoo (talk) 14:48, 16 July 2009 (UTC)

I've edited the algorithm description to correct / clarify this point. --Syperk (talk) 23:14, 18 September 2011 (UTC)

Reverse arrow?

What does the reverse arrow (←) mean?  —CobraA1 01:58, 17 June 2008 (UTC)

It appears to mean that the variable on the left hand side is being assigned the value on the right. Most modern programming languages use an equal sign for this, but it's rather different from mathematical equality so some writers prefer other notations such as this one. —David Eppstein (talk) 04:43, 17 June 2008 (UTC)

It should changed, I was confused by it too. I thought it meant traversing a pointer. (i.e. C/C++/etc pointer notation) --Voidvector (talk) 05:53, 30 October 2008 (UTC)

This should not be changed by any means. It's a very common notation in algorithms literature. We should at most point out to a glossary, or mention that somewhere in the text. --NIC1138 (talk) 01:07, 10 May 2011 (UTC)

Difficult to understand, and suggestions for expansion

For some reason, I find that this article (combined with the Algorithm X article) difficult to understand, and does not give me quite sufficient details to implement DLX in my own codes. On the other hand, Knuth's paper is to the point, contains sufficient examples, making it easily understandable for me to implement DLX. My suggestion is to merge the two pages, and to reproduce the pseudocode from Knuth's paper on this page.

Further, the following two links could contain additional information that allows this article to be expanded:

• How to find a random solution using DLX in the context of generating full Sudoku grids.
• Algorithm Y by David Eppstein, which improves Algorithm X if the aim is to find a single solution. (I haven't properly digested this though.)

--unkx80 (talk) 14:01, 13 November 2009 (UTC)

DLX is not synonymous with Dancing Links

If you read the Knuth paper, you'll see that "Dancing Links" is the technique for quickly undeleting an element from a doubly linked list. He claims it to be extremely useful in general and then shows an example by applying it to Algorithm X. He say, "When algorithm X is implemented in terms of dancing links, let’s call it algorithm DLX." Ben (talk) 10:02, 27 March 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Dancing Links. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20101206221635/http://hadoop.apache.org/common/docs/r0.20.2/api/org/apache/hadoop/examples/dancing/package-summary.html to http://hadoop.apache.org/common/docs/r0.20.2/api/org/apache/hadoop/examples/dancing/package-summary.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 00:18, 4 September 2017 (UTC)

Question: If Knuth implemented a sparse matrix "where only 1's are stored" -- isn't that actually what they call a dense matrix instead? --User:Faulknerfan —Preceding undated comment added 06:17, 21 December 2018 (UTC)

List of size 1

The passage "This works regardless of the number of elements in the list, even if that number is 1." is confusing. If there is only one element in the list, then either x.left or x.right is this one element. If x.left is the one element in the list, then x.right is either ill-defined or null, and thus x.right.left is definitely ill-defined. Or if x.right is the one element in the list, x.left is either ill-defined or null, and thus x.left.right is definitely ill-defined. Perhaps we could just delete the passage "This works regardless...". Alternatively, please add text, pseudocode, and/or links to other Wikipedia pages to explain. — Preceding unsigned comment added by 100.35.194.211 (talk) 02:47, 23 May 2020 (UTC)

These are circular doubly linked lists with a “list head” node. So a one-element list (with node "x") will look like:

[head] -> [x] ->

circling around. That is x.left = head, and x.right = head too, and similarly head.left and head.right are both x. So for deleting, "x.left.right ← x.right" sets "head.right ← head", and "x.right.left ← x.left" sets "head.left ← head", which is how an empty list is represented. Conversely for undeleting, doing “x.left.right ← x” sets “head.right ← x” and “x.right.left ← x” sets “head.left ← x”, which is the one-element list. If this is not clear, see the figures in Section 2.2.5 of Volume 1 of TAOCP, or section 7.2.2 (part of Volume 4 Fascicle 5, published last year). This article should probably have one such figure, agreed. Hopefully someone can add it; not sure whether it's ok to just take a screenshot and stick it into this article.... Shreevatsa (talk) 06:30, 23 May 2020 (UTC)