Knuth Algorithm X: Selecting B,D & F over A

[woundedtiger4]

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]

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

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

[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?

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

 

[woundedtiger4]

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

thank you sooooooooooo much, you really helped me in understanding it.

 

[LudusRex]

Thank you for bringing up this question. Knuth's Algorithm X is a backtracking algorithm used for solving exact cover problems, where the goal is to find a subset of a given set that satisfies a set of constraints. In this particular example, the given set is a matrix with rows representing possible solutions and columns representing constraints. The goal is to find a subset of rows that satisfies all the constraints, or in other words, to find an exact cover.

In the first level of the algorithm, we select a column with the lowest number of 1s, which in this case is column A. This means that we want to include row A in our solution. However, as we move on to the next level, we encounter a conflict where row A shares a 1 with row C in column C. This means that if we were to include row A in our solution, we would not be able to include row C, and therefore not satisfy the constraint for column C.

In order to find an exact cover, we need to backtrack and try a different combination of rows. This is where the algorithm selects row B in the second level. By selecting B, we are able to satisfy the constraint for column A and also include row D in our solution. Moving on to the third level, we encounter a similar conflict with row F sharing a 1 with row E in column E. This leads us to backtrack again and try selecting row D in the fourth level, which finally allows us to include row F and satisfy all the constraints.

In summary, the reason why "A" is not in the final solution is because it creates a conflict with other rows in the matrix. Knuth's Algorithm X is designed to find an exact cover, and in this case, the combination of rows B, D, and F is the only one that satisfies all the constraints. I hope this explanation helps clarify the selection process in this example.