Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

alt text

(sorry for the poor quality)

share|improve this question
    
yes you can certainly factor out the symmetries of the cube. It might also be fruitful to consider - for a single cube of the puzzle, that since it must be filled then what are all the possible ways to place a pentomino that fills that cube (now you know that one of these must be the correct one). Another good optimization (which is harder to implement) is to try to find impossibilities as quickly as possible (since that prunes the search tree you will get to the solution quicker). –  anon Aug 21 '10 at 22:21
    
@muad, I'm looking for something really significant. Eliminating symmetries only reduces by a factor of 24. Can you elaborate on finding impossibilities? –  Tomer Vromen Aug 21 '10 at 22:40
    
Actually, I think the wording is not clear. What I'm really looking for is some mathematical property that would eliminate the need to do backtracking on combinations of piece placements. –  Tomer Vromen Aug 21 '10 at 22:42
    
Personally, I would construct the corner presented in the picture, then attempt the second half of the puzzle as normal. This would also prune your search tree considerably given a known starting configuration in which a solution exists. –  Joshua Shane Liberman Aug 22 '10 at 1:24
2  
@muad, the general problem may be NP-hard, but this is but one instance: there is no reason a priory why particular instances of very hard problems can be solved using special tricks adapted to the instance. –  Mariano Suárez-Alvarez Sep 13 '10 at 18:27
show 5 more comments

6 Answers

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

Burr Tools solving y-pentomino

share|improve this answer
add comment

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

share|improve this answer
    
Thanks for the links. I'll take a look at them. –  Tomer Vromen Aug 22 '10 at 15:01
add comment

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.

share|improve this answer
add comment

I realized about 80% through that this answer may have too many parts to implement, so I'm also going to leave a shorter one.

If you prioritize filling some cells over others, you can at least prune the computer's search tree. I suggest filling the center cube, followed by the six face centers, followed by the eight corners, finishing with everything else.

Here, let me number the squares of a Y pentomino:
1
23
4
5
By starting with the Y filling the center cube, the search space can be reduced by a factor of 12 by holding this piece's orientation constant. Note that only cells 2, 3, and 4 can occupy the center of the cube. If 2 or 4 is the center cell, then five face centers will remain to be filled; if it's 3, then all six will remain.

For the five or six centers, the Y occupying each center can be placed in one of 36 ways, disregarding overlap, as follows:

-The "spine" (the cubes 1245) can point in any of four directions
-Again, only 2, 3, or 4 can fill these cubes
-The full Y can lie on the face in three ways for each cube: on either Y face for all three, plus either along the spine for 2 and 4 or alongthe furthest opposing face for 3

Now for the eight corners. Only 1 and 5 can occupy these cubes, so for each of these corners we can work on partial placements for just the spines along the edges. Now, each corner is adjacent to three three-square edges, although some of the twelve edges are certainly part-occupied by Y's placed in the previous phase. The corners to be filled need to be prioritized by fewest available edges.

-If, at any point, an unfilled corner has 0 free edges, then either the last "temporary edge placement" or the entire face-center configuration needs to be advanced to the next one
-Whenever a corner piece is laid along an edge and the other corner sharing that edge is not yet filled, that other corner should be re-prioritized for having one fewer free edge
-If some unfilled corner has only one free edge, a spine is placed along that corner and edge
-And if no unfilled corner has fewer than two free edges, pick and note a "temporary edge placement" to fix if it leads to a contradiction. (I guarantee at least two corners will have no more than two edges. If the first placement is wrong, the second placement should be used but not noted as temporary.)

This gives eight partial placements and six or seven total placements. This leaves eleven or ten Y's to place within a volume of 63 or 58, respectively, which includes at least 26 cubes that are absolutely not filled regardless of how exactly the corner Y's are placed (each one still has up to four possibilities for the placement of the 3 cube), a much smaller search space.

share|improve this answer
add comment

I was inspired by the problem you presented, and wrote a program for finding the solutions. I hope you don't mind me saying, after seeing the program solve this cube with less than 2 million placements and removals per solution on average (with no clever heuristics), the figure of 50 million seems to indicate some kind of problem in the implementation. I'll be glad to share if this could do good to you or anyone.

share|improve this answer
add comment

For a simpler solution path, I again suggest filling the center cube first to reduce symmetries, but make sure cube 1 or 5 is on the top layer (or bottom, depending on which you want to fill first). Then you can fill the first layer (possibly prioritizing the corners), followed by the subsequent layers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.