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.