Talk:Knuth's Algorithm X

The following discussion is an archived debate of the proposal. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the debate was move. —Nightstallion (?) 08:18, 19 January 2006 (UTC)

Requested move

Knuths Algorithm x → Knuth's Algorithm X – {improper capitalization & punctuation} copied from the entry on the WP:RM page

Voting

Add *Support or *Oppose followed by an optional one-sentence explanation, then sign your vote with ~~~~

• Support as per my comment-reply-comment below! --Lox (t,c) 10:13, 15 January 2006 (UTC)

Discussion

Add any additional comments

• Comment: I am not sure why "Algorithm" should be capitalised, I'd rather see it moved to Knuth's algorithm X. Articles tend not to have a capitalised "algorithm" as shown by this search. --Lox (t,c) 14:21, 14 January 2006 (UTC)
• Reply: Lox: You make a good point, and thank you for checking. I was initially taken aback by capitalizing "Algorithm" but not "x". Similarly, your proposal to not capitalize "algorithm" but to capitalize the "X" similarly strikes me as inconsistent. As far as I know, the "X" is always capitalized in the literature when someone refers to "Algorithm X". Indeed, the phrase "Algorithm X" often appears without naming Knuth directly. In this sense, "Algorithm X" is the proper name of a specific algorithm, which is a strong reason for capitalizing this proper name. In constrast, some of the terms your search revealed are general: "Sorting algorithm", "Search algorithm", etc. I understand why "algorithm" isn't capitalized in these cases, consistent with standard Wiki naming conventions. Other terms are algorithm's named after particular people: "Dijkstra's algorithm", "Prim's algorithm", "Euclidean algorithm", etc. These latter terms lose meaning if you remove the name: "Eucleadian algorithm" refers to a specific algorithm (for finding the greatest common divisor of two integers), but "algorithm" without "Euclidean" refers to nothing in particular. Thus the proper name of the person should be capitalized, but whether or not to capitalize "algorithm" is a matter of taste and convention. Wiki convention is to leave "algorithm" uncapitalized. In contrast, "Algorithm X" does refer to a specific algorithm, whether or not Knuth's name is mentioned. In summary, I see "Algorithm X" as a proper name, hence to be capitalized. --Rob Zako 07:56, 15 January 2006 (UTC)

  Thanks for taking the time to reply! I certainly do not oppose the change in capitalisation of "x", it is fairly obvious that it should be "X". As for what you say about "algorithm", I agree that a reference to "Algorithm X" would relate to Knuth's work and on that basis, it seems only correct to capitalise "Algorithm". I support the move, as per my vote! --Lox (t,c) 10:17, 15 January 2006 (UTC)

• Comment: This new article is part of the rewrite of the Dancing Links page, which is blatantly incorrect. --Eneg 15:39, 5 January 2006 (UTC)
• Reply: Eneg: Could you please explain your concerns with the Dancing Links page? --Rob Zako 08:03, 15 January 2006 (UTC)
• Reply: Rob Zako: That DL article was pretty bad before I rewrote it. If you're interested, just check the history. Perhaps the most notable shortcoming with that article beforehand was that it didn't discuss dancing links. User:Eneg 23:12, 15 January 2006 (UTC)

The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

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:54, 27 June 2006 (UTC)

Algorithm X is the wrong name

Knuth uses "Algorithm X" as a temporary name for algorithms during discussion, not as actual referrable names, much as if you may say "imagine a variable x which represents the (unknown) number of articles in Wikipedia". For example, there's another "Knuth's Algorithm X" in The Art of Computer Science, third edition, page 325.

I propose that this article be renamed "Brute Force Exact Cover Algorithm" or better, just combine it with the DLX article.

Somewhat agree. Knuth says, "Let's call it Algorithm X for lack of a better name", which definitely implies to me that he wasn't trying to actually name it. On the other hand, Algorithm X is a generally useful concept, separate from its implementation DLX. If this is to be merged, it should be merged with Exact Cover. As Knuth puts it, "Solving the exact cover problem: [...] Algorithm X is simply a statement of the obvious trial-and-error approach. (Indeed, I can’t think of any other reasonable way to do the job, in general.)" Ben (talk) 10:21, 27 March 2015 (UTC)

References

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

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.

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:

  1 2
A 0 0
B 1 1

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 :-) -- Coffee2theorems (talk) 23:02, 4 July 2008 (UTC)

I think the algorithm is incorrect as in missing the following rule:

2. If there is a column c without any 1s, terminate unsuccessfully, otherwise choose a column c (deterministically). -- 139.18.249.154 (talk) 13:15, 18 October 2011 (UTC)

I totally agree — the rule should be explicitly reported in the scheme box, as the 2nd condition on which the algoritm terminates (this time unsuccessfully). Perhaps, the best place to put it would be right after point 1 (i.e., after the successful the termination condition). While it is obvious why the algorithm should stop unsuccessfully on any matrix having an all-zero column (no complete coverage is possible in this case, since the set element represented by such column belongs to no subset), the way in which the (nice) example is worked out makes the unsuccessful termination of Level 1: Select Row A unnecessarily obscure.Banquo71 (talk) 13:18, 12 December 2013 (UTC)

That's a good point, but I suspect that sort of no-solution matrix (a matrix with at least one column C without any 1s) never actually occurs during normal operation, if we add the precondition:

1. Before starting Algorithm X, check if there is a column c without any 1s. If so, there is no solution, so don't even bother running Algorithm X.

If that situation is checked once before starting Algorithm X, the algorithm never changes a matrix where every column has at least 1 into that sort of problematic matrix, right?

Is "optimizing" this algorithm to do that check only once, rather than every iteration, a premature optimization? --DavidCary (talk) 03:49, 20 February 2016 (UTC)

Quotation without attribution

This article directly quotes Knuth's paper without attribution and has apparently done so since 2006. The article omits Knuth's quotes around "depth first" and one sentence in one of the quoted paragraphs. The text ought to be rewritten to avoid copyright problems. Michael Slone (talk) 03:35, 28 December 2009 (UTC)

...but why?

Would be interesting to see an additional section here indicating the significance of this algorithm (I can't add it as I don't know what the significance is). I assume it has a 'real world' application?

--Mortice (talk) 23:09, 18 January 2013 (UTC)