Re: [math-fun] Exact Cover Solver
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 http://cp4space.wordpress.com
----- 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
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
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
I too have an implementation of Knuth's Dancing Links to solve Exact Cover. Since the main interest driving me to write it is the design and solution of 3D block packing puzzles, I've found that the "raw" input in the form of set-of-subsets is far too verbose for easy experimentation. (For example, the classic Soma Cube takes approximately 800 subsets to describe, because you need a different subset for each piece in each orientation.) I'm now working on a "pre-processor" that takes as input the set-of-cells occupied by a piece in one position and orientation, and emits the set-of-set-of-cells occupied by a piece in all positions and orientations (subject to bounding box restrictions). That will make the description of a new puzzle much more tractable. - John
On Mon, Jul 29, 2013 at 3:07 PM, John Aspinall <j@jkmfamily.org> wrote:
I've found that the "raw" input in the form of set-of-subsets is far too verbose for easy experimentation.
Indeed. That is most often the case, that you need to write an auxiliary program to generate the input for an exact cover solver. Fortunately, it's usually not terribly difficult, but sometimes, as with the case of N-queens, it takes a bit of analysis to get right. -Robert
Following up on the mail below from this summer, here is the first interesting result from a search for space-filling puzzles on the cubic lattice. 25 copies of the following 5-cell: {(1,1,1) (2,1,1) (3,1,1) (3,2,1) (2,1,2)} will fill a 5x5x5 cube in a small number of ways. (More on the small number below.) Here's a solution with pieces 1-9 and A-P (more readable in a fixed-width font): Layer 1 2 3 4 5 12688 12577 22559 KL5A9 LLL99 11678 42678 333AB K35A9 KJLAA 14668 4447B 3GFCB KKJCC JJJCD OPMMM OOONM GGFBB IHFED HHHCD PPPMN PONNN IGFFE IGEEE IIHDD The small number of solutions is either 1, 2, or 3, depending on whether there are sub-pieces with their own symmetries. The exact cover solver spits out 96 "solutions"; after dividing by 24 for the symmetries of the cube as a whole we get 4 "solutions" that differ by more than rotation of the entire cube. However if you look at the solution above, you can see that the bottom two rows of the bottom two layers (1 and 2) form an entirely separable 2x2x5 sub-unit (pieces M,N,O,P) with 2 non-isomorphic orientations. I haven't examined all the solutions yet to see if there is: (a) another sub-unit with 2 orientations, yielding only 1 "essential solution"; (b) a second "essential solution" with its own 2-way sub-unit; (c) two more "essential solutions" with no separable sub-units. So now in addition to the pre-processor, it looks like I need a post-processor to put geometry back into the exact cover solution. - John On 07/29/2013 10:12 PM, quad wrote:
On Mon, Jul 29, 2013 at 3:07 PM, John Aspinall <j@jkmfamily.org> wrote:
I've found that the "raw" input in the form of set-of-subsets is far too verbose for easy experimentation. Indeed. That is most often the case, that you need to write an auxiliary program to generate the input for an exact cover solver. Fortunately, it's usually not terribly difficult, but sometimes, as with the case of N-queens, it takes a bit of analysis to get right.
participants (4)
-
Adam P. Goucher -
John Aspinall -
quad -
Victor Miller