Content deleted Content added
Line 31:
I propose that this article be renamed "Brute Force Exact Cover Algorithm" or better, just combine it with the DLX article.
== Algorithm description slightly misleading/inaccurate? ==
At first I thought that my fellow editors were a bit sloppy in some inessentials, but upon skimming Knuth's paper from Arxiv I noticed that the same problem seems to be there, too(!). Both the article and the paper say "If the matrix A is empty, the problem is solved; terminate successfully" and "Any systematic rule for choosing column c in this procedure will find all solutions". Now consider this part in the example (sorry for the quick&dirty notation):
<pre>
The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:
2 3 5 6
D 0 1 1 1
Thus this branch of the algorithm terminates unsuccessfully.
</pre>
However, here we were supposed to be able to pick any column, so let us pick column 3 instead. The algorithm will remove row D (and columns 3-6), which should result in an empty matrix by normal understanding, and we should get a successful result instead of failure. A remedy to this is to consider the resulting matrix as a non-empty 0x1 matrix (instead of empty 0x0 matrix), because while all rows have been removed, one column (2) wasn't ''explicitly'' removed by the algorithm.
But, then consider this new example:
<pre>
1 2
A 0 0
B 1 1
</pre>
Whichever column you pick, you end up with choosing the row B and reducing the matrix to a 1x0 matrix (because both columns get removed, but the row A doesn't). Yet this is a solution to the problem, right? So we should consider a 1x0 matrix to be empty but a 0x1 matrix to be non-empty. Everything works fine if an empty matrix is defined to be any matrix with 0 columns (and considering 0xn and nx0 matrices where n is not 0 as different from the 0x0 matrix in the first place). It is a somewhat peculiar notion of "empty", though, and I'm not quite bold enough to be sure that I've understood everything correctly on such a quick peek here. After all, it's Knuth's paper, and I don't have any citations for any of this. Hopefully someone else has the energy to look at this someday :-) -- [[User:Coffee2theorems|Coffee2theorems]] ([[User talk:Coffee2theorems|talk]]) 23:02, 4 July 2008 (UTC)
| |||