The discussion revolves around Knuth's Algorithm X, specifically addressing the selection of rows in the algorithm's example and the reasoning behind the exclusion of row "A" from the final solution while rows "B," "D," and "F" are included. Participants explore the algorithm's mechanics and the conditions for achieving an exact cover.
Participants express uncertainty regarding the algorithm's selection process and the reasons for the termination of certain branches. There is no consensus on the interpretation of the algorithm's behavior or the implications of selecting row "A."
Participants discuss the algorithm's mechanics without resolving the underlying assumptions about the exact cover problem or the specific configurations of the rows.
woundedtiger4 said:Hi all, at http://en.wikipedia.org/wiki/Knuth's_Algorithm_X in the example I don't understand that why not "A" is in the final solution & only B, D & F are in the final solution whereas "A" was selected at Level 1
woundedtiger4 said:[STRIKE]bump[/STRIKE]
plus why at the level 1 the branch containing "D" (i.e. containing 0, 1, 1, 1 in columns 2, 3, 5 & 6) was terminated unsuccessfully?
NemoReally said:The intent, as far as I understand it, is to find a combination of rows that include every number from 1 to 7 but where each number only occurs in at most one row.
The algorithm seems to work by picking the row (A) that has the most numbers in it and then trying to find a combination of the other rows that have the numbers that aren't in A.
Having selected A (in this case), it proceeds by removing any sets that have a number in common with A (in this case, B,C,E and F). This is because any combination of B,C,E or F with A will have at least one multiple of '1', '4' or '7'. This only leaves row D as a possible match for A.
However, row D doesn't contain a '2' and neither does A, so the combination of A and D is not an exact cover, hence the algorithm terminates and goes to test for another combination.
NR