Talk:Knuth's Algorithm X: Difference between revisions

Revision as of 10:37, 18 January 2015

Latest revision as of 07:11, 2 April 2025

(6 intermediate revisions by 5 users not shown)

Line 1:

{{WikiProject banner shell|

{{WikiProject Computer science}}

}}

<div class="boilerplate" style="background-color: #eeffee; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #AAAAAA;"><!-- Template:polltop -->

:''The following discussion is an archived debate of the proposal. <fontspan colorstyle="color:red;">'''Please do not modify it.'''</fontspan> 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'''. &mdash;[[User:Nightstallion|<span style="font-variant:small-caps">Nightstallion</span>]] [[User talk:Nightstallion|''(?)'']] 08:18, 19 January 2006 (UTC)

Line 21 ⟶ 23:

*'''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. <fontspan colorstyle="color:red;">'''Please do not modify it.'''</fontspan> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:pollbottom -->

== Reorganize Exact cover, Algorithm X and Dancing Links articles? ==

Line 33 ⟶ 35:

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.)"'''<ref>{{cite journal

| author = [[Donald Knuth|Knuth, Donald]]

| title = Dancing links

| version = P159

| year = 2000

| volume = 187

| journal = Millennial Perspectives in Computer Science

| arxiv = cs/0011047

| url = http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

| accessdate = 2006-07-11 }}</ref> [[User:Hackerb9|Ben]] ([[User talk:Hackerb9|talk]]) 10:21, 27 March 2015 (UTC)

{{reflist-talk}}

== Algorithm description slightly misleading/inaccurate? ==

Line 64 ⟶ 79:

'''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.[[User:Banquo71|Banquo71]] ([[User talk: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? --[[User:DavidCary|DavidCary]] ([[User talk:DavidCary|talk]]) 03:49, 20 February 2016 (UTC)

==Quotation without attribution==

Line 73 ⟶ 93:

--[[User:Mortice|Mortice]] ([[User talk:Mortice|talk]]) 23:09, 18 January 2013 (UTC)

== "Nondeterministic" seems misleading ==

It is a branching recursion where all branches are explored. [[Nondeterministic algorithm]] is about something else, as far as I can tell. [[User:Ehasl|Elias]] ([[User talk:Ehasl|talk]]) 07:11, 2 April 2025 (UTC)