Knuth's Algorithm X: Difference between revisions

Revision as of 09:01, 31 May 2012

Revision as of 15:25, 31 May 2012

Line 26:

== Example ==

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

:* <math>''A'' = {1, 4, 7}</math>;

:* <math>''B'' = {1, 4}</math>;

:* <math>''C'' = {4, 5, 7}</math>;

:* <math>''D'' = {3, 5, 6}</math>;

:* <math>''E'' = {2, 3, 6, 7}</math>; and

:* <math>''F'' = {2, 7}</math>.

This problem is represented by the matrix:

Line 355:

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

In summary, the algorithm determines there is only one exact cover: <math>\mathcal{S}^*</math> = {''B'', ''D'', ''F''}</math>.

== Implementations ==