Tiling pentominoes into a 5x5x5 cube

I have this wooden puzzle composed of 25 y-shaped pentominoes, where the objective is to assemble them into a 5x5x5 cube. After spending quite a few hours unsuccessfully trying to solve the puzzle, I finally gave up and wrote a program to try all possible combinations using backtracking. Analyzing the results revealed that for every solution found, the computer made - on average - 50 million placements and removals of pieces. This is obviously beyond my capabilities as a human, even if I can see a few steps ahead that a partial solution leads to a "dead end".

So, my question is this: given that the puzzle is so symmetrical, is there some way to significantly prune the search tree (maybe even making it possible for me to solve the puzzle on my own)?

(sorry for the poor quality)

Solution 1:

Get Burr Tools. It takes less than a minute to set up this problem, and then a few minutes to generate 1264 solutions. I'm not sure if that's all solutions, the solver tells me 22 minutes are now needed to completely check the solution space. (EDIT -- Total solving time = 24.8 minutes)

A slightly more interesting problem is 25 N pentominos in a cube. There are 4 solutions, found in 2.6 minutes. Many other interesting puzzles are compiled at Puzzles will be played

Solution 2:

First, a few thoughts about this specific box packing problem. It might be possible to pack this box by packing the "y" polycube into 25 cells in 5 identical layers. This corresponds to collapsing this 3-D shape into a polyomino in the plane, and then using it to pack a 5x5 rectangle. However, this polyomino can not tile a 5x5 rectangle. (The terminology for polyominoes is not totally standard but some use the order of a polyomino to mean the smallest number of copies of this shape to tile a rectangle with congruent copies of itself.) The order of this polyomino is 10.

Second, there is lots of material about polyominoes and to a lesser extent box packings in the books:

S. Golomb, Polyominoes: Puzzles, Patterns, Problems, and Packings (Revised Edition), Princeton U. Press, 1994.

G. Martin Polyominoes, MAA, 1991.

Third, there are a variety of papers related to polyominoes and boxes at Michael Reid's very nice site with links to others:

http://www.math.ucf.edu/~reid/Polyomino/

http://www.math.ucf.edu/~reid/Research/index.html

Fourth, there are "complexity" results which govern the general problem of given a collection of tiles (either in 2-D or 3-D) when can one use them to tile some particular shape (say a rectangle or rectangular box). Here is a paper related to this of Erik Demaine:

http://erikdemaine.org/papers/Jigsaw_GC/

Also see:

http://archive.ite.journal.informs.org/Vol5No3/Chlond/index.php

Solution 3:

While you talk about pruning the search tree through symmetry, generally the best way I've seen to approach these problems is by breaking cells down into classes or layers; for instance, many of the classic polyomino non-tiling problems can be solved with suitable colorings, and constraints provided by colorings can help reduce the search space immensely (e.g., the Soma cube result that the 'T' piece must have its spine on an edge of the cube). The thing that jumps out at first glance is the 'intermediate' layer of cells, the 26 cells that are neither on the outermost face of the cube nor the center cell. Whatever piece occupies the center must also occupy at least (and in fact, exactly) three of these cells, and any piece that's not wholly on an outer layer occupies at least one, with many placements forcing several cells to be occupied; it seems intuitively like they might be at a premium and that that's a constraint worth investigating. The section on the Soma cube in the last volume of Winning Ways For Your Mathematical Plays has some discussion of these sorts of colorings, and that might be a good place to start.