Talk:Exact cover
From Wikipedia, the free encyclopedia
Contents |
[edit] attention tag
Needs sources and context, and better organization. --Trovatore 01:51, 4 October 2005 (UTC)
[edit] Many Thanks for the prompt clarifications of 2006 04 01 put into the article
This has enabled me to now read the article with a reduced sense of contradiction between the 'definition' and the matrix example given (for the case where the set of elements in the universe is finite). I also feel the revised article gives me a better understanding of the topic. But even now, this arises, at least in part, from an assumption of mine, that is that what follows is true (that "every" should be replaced with "each"):
I have a suggestion for one further improvement. I believe it may be quicker for readers such as me to grasp the intended meaning of the Definition if, instead of saying (2nd sentence):
"An exact cover is a set of some of the sets S1, S2, ..., Sn such that every element of the universe U is contained in exactly one of them."
this sentence is modified to read:
"An exact cover is a set of some of the sets S1, S2, ..., Sn such that each element of the universe U is contained in exactly one of them."
i.e. replacing the word "every" by the word "each".
?
thinkact thinkact 10:44, 12 April 2006 (UTC)
[edit] Linguistics
Replacing every with each doesn't seem like it would make any more sense to me. We want to convey the sense that every element in the universe is contained and while each is technically correct it conveys less of a sense of holisticness?
Meh, either way though really. I'm not sure it matters :)
[edit] Nice article, please expand
This article could use some expansion, I think. It ought to include a description of how the N Queens Problem and SuDoku and other similar puzzles can be reduced to the Exact Cover Problem. Personally, I can instantly see the similarity between N Queens and SuDoku, and can readily see how they belong to a distinct class of puzzles. But it is much more difficult for me to see how they are both "special cases" of the ECP. Someone should provide either a proof of the relationship, or a citation of (or, preferably, a link to) a document containing such a proof. I don't know if either of the references at the bottom of the page contains such a proof, but if one of them does, it should be noted which one, especially since neither of them are very accessible (The Knuth reference links to a pdf file, which doesn't count as being "very accessible". I've never encountered a PDF viewer that doesn't make my computer go to 100% CPU usage immediately upon opening. Hence, I make it a point never to read a pdf document unless I'm quite sure it has the information I'm looking for. A trip to the library is similarly inconvenient.) Comiscuous 06:06, 6 May 2006 (UTC)
- I agree. See my question/suggestion below re reorganizing related articles. --Rob Zako 17:40, 27 June 2006 (UTC)
[edit] Eh?
The first sentence is incomprehensible, imho. The article would be better if the first section was deleted. 220.253.116.234 14:43, 28 May 2006 (UTC)
- I was about to say the same thing! The first section is nonsensical gibberish. What the hell does "combining" mean? Adding? Concatenating? What are "extras"? Xezlec 17:13, 4 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:53, 27 June 2006 (UTC)
