Computing exact cover is known to be NP-complete. So, unfortunately, no. :) Despite that, even without optimizations, it's pretty efficient. For another math problem, I was computing exact covers of subsets of size 100, for example with 900 sets. Robert On Mon, Jul 29, 2013 at 8:01 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
In polynomial time? I think I have a reduction of 3-SAT to an exact cover problem, so this would be *really* useful.
Sincerely,
Adam P. Goucher
----- Original Message ----- From: quad Sent: 07/29/13 02:18 PM To: math-fun Subject: [math-fun] Exact Cover Solver
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun