Talk:Dancing Links
From Wikipedia, the free encyclopedia
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)
[edit] 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)
[edit] 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)
[edit] 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)
