About 10 years ago I wrote a discrete hill climber to solve exact cover problems (only when there really *was* an exact cover). I found that for some of the hard pentomino tiling problems that it was a fair amount faster than Knuth's dancing links. This is good when you're only interested in finding one solution, rather than to find them all (as DL does). Victor On Mon, Jul 29, 2013 at 11:10 AM, quad <quadricode@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun