Knuth's Algorithm X: Difference between revisions

Revision as of 11:21, 10 May 2012

Revision as of 09:01, 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 ==