Knuth's Algorithm X - Example

Example

For example, consider the exact cover problem specified by the universe U = {1, 2, 3, 4, 5, 6, 7} and the collection of sets = {A, B, C, D, E, F}, where:

• A = {1, 4, 7};
• B = {1, 4};
• C = {4, 5, 7};
• D = {3, 5, 6};
• E = {2, 3, 6, 7}; and
• F = {2, 7}.

This problem is represented by the matrix:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Algorithm X with Knuth's suggested heuristic for selecting columns solves this problem as follows:

Level 0

Step 1—The matrix is not empty, so the algorithm proceeds.

Step 2—The lowest number of 1s in any column is two. Column 1 is the first column with two 1s and thus is selected (deterministically):

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Step 3—Rows A and B each have a 1 in column 1 and thus are selected (nondeterministically).

The algorithm moves to the first branch at level 1…

Level 1: Select Row A

Step 4—Row A is included in the partial solution.

Step 5—Row A has a 1 in columns 1, 4, and 7:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Column 1 has a 1 in rows A and B; column 4 has a 1 in rows A, B, and C; and column 7 has a 1 in rows A, C, E, and F. Thus rows A, B, C, E, and F are to be removed and columns 1, 4 and 7 are to be removed:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Row D remains and columns 2, 3, 5, and 6 remain:

	2	3	5	6
D	0	1	1	1

Step 1—The matrix is not empty, so the algorithm proceeds.

Step 2—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.

The algorithm moves to the next branch at level 1…

Level 1: Select Row B

Step 4—Row B is included in the partial solution.

Row B has a 1 in columns 1 and 4:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Column 1 has a 1 in rows A and B; and column 4 has a 1 in rows A, B, and C. Thus rows A, B, and C are to be removed and columns 1 and 4 are to be removed:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

Rows D, E, and F remain and columns 2, 3, 5, 6, and 7 remain:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Step 1—The matrix is not empty, so the algorithm proceeds.

Step 2—The lowest number of 1s in any column is one. Column 5 is the first column with one 1 and thus is selected (deterministically):

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Step 3—Row D has a 1 in column 5 and thus is selected (nondeterministically).

The algorithm moves to the first branch at level 2…

Level 2: Select Row D

Step 4—Row D is included in the partial solution.

Step 5—Row D has a 1 in columns 3, 5, and 6:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Column 3 has a 1 in rows D and E; column 5 has a 1 in row D; and column 6 has a 1 in rows D and E. Thus rows D and E are to be removed and columns 3, 5, and 6 are to be removed:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

Row F remains and columns 2 and 7 remain:

	2	7
F	1	1

Step 1—The matrix is not empty, so the algorithm proceeds.

Step 2—The lowest number of 1s in any column is one. Column 2 is the first column with one 1 and thus is selected (deterministically).

Row F has a 1 in column 2 and thus is selected (nondeterministically).

The algorithm moves to the first branch at level 3…

Level 3: Select Row F

Step 4—Row F is included in the partial solution.

Row F has a 1 in columns 2 and 7:

	2	7
F	1	1

Column 2 has a 1 in row F; and column 7 has a 1 in row F. Thus row F is to be removed and columns 2 and 7 are to be removed:

	2	7
F	1	1

Step 1—The matrix is empty, thus this branch of the algorithm terminates successfully.

As rows B, D, and F are selected, the final solution is:

	1	2	3	4	5	6	7
B	1	0	0	1	0	0	0
D	0	0	1	0	1	1	0
F	0	1	0	0	0	0	1

In other words, the subcollection {B, D, F} is an exact cover, since every element is contained in exactly one of the sets B = {1, 4}, D = {3, 5, 6}, or F = {2, 7}.

There are no more selected rows at level 3, thus the algorithm moves to the next branch at level 2…

There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 1…

There are no more selected rows at level 1, thus the algorithm moves to the next branch at level 0…

There are no branches at level 0, thus the algorithm terminates.

In summary, the algorithm determines there is only one exact cover: = {B, D, F}.