This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
I'm implemented 2 different sets of code (one using linked lists, the other using numpy) They both work with the toy example presented in this wikipedia page. However, that same code fails when run against an even slightly more complex answer.
I keep following the algorithm, and it seems to nuke all the rows. I've done 2 completely different implementations, but it now seems to me the the LOGIC of what's shown in this wiki example almost guarantees a failure like I'm seeing.
I've tried to detail this in Stack Overflow: https://stackoverflow.com/questions/63066395/debugging-exact-cover-pentominoes-example-clearly-im-misunderstanding-somethin — Preceding unsigned comment added by Ttennebkram ( talk • contribs) 00:05, 31 July 2020 (UTC)
I have been searching the intertubes and I can't find a decent explanation of how to translate the sudoku problem(or any other NP problem for that matter) into an exact cover problem, even Knuth's paper is not cristal clear, everybody "ass-u-mes" it is evident, everybody seems to automagically "get it", and now I feel stupid, it would be great if you could explain the _why_ as if you were talking a little baby. Thanks —Preceding unsigned comment added by 190.134.148.58 ( talk) 03:54, 14 June 2008 (UTC)
Needs sources and context, and better organization. -- Trovatore 01:51, 4 October 2005 (UTC)
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)
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 :)
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)
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)
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)
Exact cover has been well-known for decades, but Knuth's publication of Dancing links and Algorithm X is recent. The 'Finding Solutions' section mentions only Algorithm X, but I feel sure that there must be other good algorithms, especially for some specific exact cover problems where algorithms can be tailored to features of the matrix. I guess it's possible that Knuth's algorithm is a clear winner among the general algorithms? The Eight Queens problem page lists a number of good and bad algorithms for that (similar) problem - I wonder if something like that would be suitable here? Chrisjohnson 23:06, 13 September 2007 (UTC)
The article should highlight two trivial (pre)conditions. First, if the union of the subsets in the collection is a proper subset of the universe U, then trivially there is no exact cover. Thus it is typical to require that the union is exactly U. Second, if one of the subsets in the collection is the null set, then it makes no difference whether it is included or excluded in the exact cover. Thus it is typical to exclude the null set. In the matrix representation of the exact cover problem, these two conditions are that each column have at least one 1 and that each row have at least one 1, respectively. -- Rob Zako ( talk) 20:19, 22 June 2008 (UTC)
The article should be edited to highlight two different kinds of generalizations.
First, there are problems that are precisely equivalent to the exact cover problem, for example, the exact hitting set problem and the matrix representation of exact cover. These are not so much generalizations of exact cover as they are different representations or interpretations of the same basic logic. Fundamentally, a collection of sets isn't essential but only two sets that have some relation between them, or equivalently a bipartite graph. The article should describe the formal definition of exact cover in terms of a collection of subsets, but then make clear equivalent problems. Perhaps there should be a section titled Equivalent problems.
Second, in his paper " Dancing Links", Donald Knuth talks about a simple generalization of the exact cover problem with primary and secondary constraints. Primary constraints must be satisfied exactly once, but secondary constraints can be satisfied once or not at all. In particular, the N queens problem is a generalized exact cover problem. In the matrix representation, one technique for making a column into an optional constraint is to add a row with a single 1 in that column. (It would be appropriate to also talk about the significance of a columns with a single 1.) The generalization is minor and it is a simple matter (and more efficient) to modify Algorithm X or Dancing Links to handle secondary constraints directly without the need for added rows. The article should be expanded to explain this simple generalization, and the N queens problem should be added back in. Perhaps there should be a section titled Generalizations. — Rob Zako ( talk) 20:44, 22 June 2008 (UTC)
The article should be expanded to better explain that exact cover is NP-complete. The article should also make connections to other NP-complete problems and to complexity theory. For example, exact cover is trivially equivalent to exact hitting set. Exact cover is also one of Karp's 21 NP-complete problems. The article should provide a proof that exact cover is NP-complete by describing the appropriate reduction. Perhaps it would be useful to include a standard sidebar in articles on NP-complete problems, or at least Karp's 21 NP-complete problems, showing the relation of the problem to other NP-complete problems. — Rob Zako ( talk) 21:04, 22 June 2008 (UTC)
I added two examples of special cases of the exact cover problem in the "See also" section: perfect matching and 3-dimensional matching. We could explain this connection in more detail; maybe we could have a section on special cases just like we have a section on generalisations? — Miym ( talk) 22:24, 3 April 2009 (UTC)
. Scott Barnes ( talk) 20:21, 24 September 2012 (UTC) Coordinates are in row, column form. They look ok after all. Scott Barnes ( talk) 20:27, 24 September 2012 (UTC)
The article's very first sentence states that an exact cover is a collection. What is that? In particular, is a collection allowed to include an element more than once, i.e., is it a multi-set? Or is it just a set? Or a list? As far as I know, the term "collection" is not standard mathematics terminology. I think the term "family" would be more appropriate, as it is commonly used to refer to a set of sets. 2A02:1205:5078:1F10:9D12:8732:AF0:1B8F ( talk) 18:26, 24 January 2015 (UTC)
In mathematics we just call this concept a partition, unless there's something I'm missing. So should this page get merged with the page on partitions? Or at the very least, should this page say something like "An exact cover is a structure studied in computer science. Although it is conceptually the same as a partition in mathematics, computer scientists are interested in different questions about this structure."? — Preceding unsigned comment added by Addemf ( talk • contribs) 02:59, 27 July 2021 (UTC)