Hello: I just wanted to announce that I wrote a program to find the exact cover of a set S = {0, ..., n-1}. It uses Knuth's Algorithm X with his Dancing Links strategy. The code is here in Lisp: https://bitbucket.org/tarballs_are_good/dancing-links Example: Given the sets A = {0, 3, 6} B = {0, 3} C = {3, 4, 6} D = {2, 4, 5} E = {1, 2, 5, 6} F = {1, 6}, find all disjoint unions of the above that equals S. This is an exact cover problem for n = 7. Input into the program is easy:
(exact-cover 7 '((0 3 6) ; A (0 3) ; B (3 4 6) ; C (2 4 5) ; D (1 2 5 6) ; E (1 6))) ; F
It will think, and spit out Solution #1 at depth 3: 6 1 5 2 4 3 0 and then return the total number of solutions found (1) and the total number of "positions" checked (5). Note that the solution above corresponds to F, D, and B respectively, just the elements were permuted. Note that they are indeed disjoint and their union is S. The program still needs a little polishing, but may be useful to some people who want to solve pentomino or n-omino packing, sudokus, or whatever. If anyone is interested in having it as a stand-alone binary that takes a file as input, let me know, and I can probably accommodate. :) Cheers, Robert Smith