Jump to content

Talk:Exact cover

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 190.134.148.58 (talk) at 03:54, 14 June 2008 (needs work, needs clear explanation). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

attention tag

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Exact_cover&oldid=219218453"