Talk:Exact cover

Is It Possible the Example Oversimplifies Some Steps, or Leaves Out Some Critical Detail?

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)

needs work

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)

attention tag

Needs sources and context, and better organization. --Trovatore 01:51, 4 October 2005 (UTC)

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)

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

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)

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)

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)

First of all, people tend to put far too much weight on NP complete. You can't infer from A) exact-cover is NP complete, and B) Sudoku is an instance of an exact-cover problem, that C) Sudoku is NP-complete. Most likely Sudoku is NP-complete, but I could certainly invent a class of exact-cover problems that wasn't.

The complexity measure is likewise beside the point if the interest is not associated with a telescopic quantity N. Sudoku over an N^2 x N^2 board is of human interest for N=3, maybe 4, and 5 on a rainy day after a blue moon aligns with Mars and Venus. Anyone solved a Rubick's tesseract lately?

As far as the brute-hood of Algorithm X is concerned, if I had a deterministic choice heuristic for a family of exact-cover problems with N log (N) performance characteristics, I would characterize that instance of Algorithm X as a highly-directed depth first search. It wouldn't be hard to set up an exact cover problem with such a highly effective choice heuristic. The knapsack problem is NP-complete, but if I give you only bricks that are powers of 2 in size, solution time is linear.

Dancing links is a relatively recent paper from Knuth. I'm sure the majority of the interest derives from Sudoku, but I would have pursued this quite independently, as I have an exact cover problem of my own interest. You would never know this on the surface, because Sudoku serves as the perfect proxy for me to discuss my interest in this algorithm with others.

It's worth bearing in mind that Sudoku could have been introduced in 3000 B.C. using nine moons of the Mayan or Babylonian calendar and it would have been entirely comprehensible, esp. if you managed to convey that a properly arranged Sudoku board portends a good hair day. In short, Sudoku happens to be a perfectly formed human proxy for problems of the exact-cover OCD itch. Even if the fad for Sudoku wanes, that won't change. The Rubick's cube remains a perfectly formed human proxy for entry-level group theory.

I'm totally in agreement with the parent comment, but not if the end result only serves to make the NP-complete pronouncement sound more profound than it is, or to isolate the serious material from the fadish Sudokuites. MaxEnt 03:00, 16 August 2007 (UTC)

Algorithms other than Knuth's

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)

(Pre)conditions

The article should highlight two trivial (pre)conditions. First, if the union of the subsets in the collection ${\mathcal {S}}$ 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 ${\mathcal {S}}$ 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)

Generalizations

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)

NP-complete

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)

Special cases

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)

Please ignore re: review pentomino tiling solution coordinates

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

What is a collection?

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)

Yes, this is probably intended to be a clearer wording but instead it only confuses. A wiki search for collection results in 0 math related entries. --134.130.4.241 (talk) 15:36, 4 June 2015 (UTC)

A collection is just the same thing as a set. We just use the word "collection" rather than "set" when the things in the collection (set) are complex. We do this especially when talking about "sets of sets". In this case, we prefer to instead talk about "collections of sets" so that we have one word (collection) for the higher-level set, and a different word (set) for the sets that are in it. -- Addemf (talk) 02:55, 27 July 2021 (UTC)

Isn't an exact cover just the same thing as a partition?

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)

You're right, and the article does say so: "Equivalently, an exact cover of $X$ is a subcollection $S^{*}$ of $S$ that partitions $X$." Arguably, the article should be renamed to Exact cover problem as that's what it really is about: a decision problem, namely to decide whether a given a collection $S$ of subsets of a set $X$ contains a subcollection that partitions $X$. It's really more about computer science than about mathematics. – Tea2min (talk) 11:37, 27 July 2021 (UTC)

An exact cover is a partition formed out of given sets, rather than some other kind of partition. I prefer article titles that name the fundamental underlying object (exact cover) rather than titles that name the question of how to find that object ("exact cover problem"), name the algorithms for solving that problem ("exact cover problem algorithm") or name the amount of time used by any of these algorithms ("exact cover problem algorithm exponential time complexity"). That way lies madness. Let's only include title words that provide significant information to readers. —David Eppstein (talk) 16:27, 27 July 2021 (UTC)