# Packing 25 three-dimensional N pentominoes into a 5x5x5 cube

The puzzle contains 25 identical pieces that look like this:

To be explicit, the piece is composed of five cubes. In the picture, three cubes form the base, and two cubes form the overhang.

The goal is to fit these 25 pieces into a 5x5x5 cube. When we bought the puzzle, it had a solution inside, but at some point this was lost. The puzzle is now (unsatisfyingly) stored in a jumbled mess in a plastic bag.

What is the solution? Optionally, I'd like to know how one could go about solving this systematically.

• If I understand correctly, there are 480 possible placements of a single piece, and the maximum number of pieces that can be packed is 24, not 25. Are you sure the pieces are identical? Commented Apr 29 at 1:13
• @RobPratt 960 ways, actually. 15 planes × 8 orientations × 8 positions in a plane. Commented Apr 29 at 1:18
• @ParclyTaxel Indeed, I was counting only 4 orientations. Commented Apr 29 at 1:29
• @RobPratt I haven't looked at the puzzle for a few years, but I'm pretty sure they are identical. I'll double check when I get home. In the meantime, why do you think only 24 pieces can be packed? As a basic check, each piece is 5 small cubes, and a 5x5x5 volume is 125 cubes -> 25 pieces. Unless you mean you've found a strategy to check all possible configurations and could only fit 24? Commented Apr 29 at 1:30
• Here's a video: youtu.be/3fBY9TyPaEs
– JS1
Commented Apr 29 at 1:40

You can solve the problem via integer linear programming as follows. For each of the $$960$$ placements $$p$$ of a piece, let $$C_p \subset [5] \times [5] \times [5]$$ be the set of cells covered by $$p$$, and let binary decision variable $$x_p$$ indicate whether placement $$p$$ is used. The problem is to maximize $$\sum_p x_p$$ subject to linear "packing" constraints $$\sum_{p: (i,j,k) \in C_p} x_p \le 1 \quad \text{for all (i,j,k)\in [5]\times[5]\times[5]}$$

The maximum turns out to be $$25$$, as you expected, and one optimal solution is:

{(1,4,2),(1,4,3),(1,5,3),(1,5,4),(1,5,5)}
{(1,1,5),(1,2,5),(1,2,4),(1,3,4),(1,4,4)}
{(1,2,2),(1,3,2),(1,3,1),(1,4,1),(1,5,1)}
{(2,2,4),(2,3,4),(2,4,4),(2,4,5),(2,5,5)}
{(2,1,3),(2,2,3),(2,2,2),(2,3,2),(2,4,2)}
{(3,1,2),(3,1,3),(3,2,3),(3,2,4),(3,2,5)}
{(3,4,1),(3,4,2),(3,4,3),(3,3,3),(3,3,4)}
{(4,4,1),(4,4,2),(4,4,3),(4,5,3),(4,5,4)}
{(5,2,1),(5,2,2),(5,3,2),(5,3,3),(5,3,4)}
{(5,4,2),(5,4,3),(5,5,3),(5,5,4),(5,5,5)}
{(5,1,1),(5,1,2),(5,1,3),(5,2,3),(5,2,4)}
{(4,1,2),(4,1,3),(4,1,4),(5,1,4),(5,1,5)}
{(1,1,4),(2,1,4),(3,1,4),(3,1,5),(4,1,5)}
{(1,1,2),(2,1,2),(2,1,1),(3,1,1),(4,1,1)}
{(3,2,1),(3,2,2),(4,2,2),(4,2,3),(4,2,4)}
{(3,3,1),(3,3,2),(4,3,2),(4,3,3),(4,3,4)}
{(1,5,2),(2,5,2),(2,5,1),(3,5,1),(4,5,1)}
{(2,5,3),(3,5,3),(3,5,2),(4,5,2),(5,5,2)}
{(1,1,1),(1,2,1),(2,2,1),(2,3,1),(2,4,1)}
{(4,2,1),(4,3,1),(5,3,1),(5,4,1),(5,5,1)}
{(1,1,3),(1,2,3),(1,3,3),(2,3,3),(2,4,3)}
{(2,5,4),(3,5,4),(3,4,4),(4,4,4),(5,4,4)}
{(4,2,5),(4,3,5),(3,3,5),(3,4,5),(3,5,5)}
{(2,1,5),(2,2,5),(2,3,5),(1,3,5),(1,4,5)}
{(5,2,5),(5,3,5),(5,4,5),(4,4,5),(4,5,5)}


• At this point I'm starting to get deja vu from the phrase "You can solve the problem via integer linear programming" :) Thanks again @RobPratt Commented Apr 29 at 4:29
• @ApexPolenta same. Dear RobPratt, do you have a tutorial or manual on how you translate these constraints into code? Commented Apr 29 at 6:14
• 3 hours of backtracking reveals only 4 distinct ways of doing this. Although my program had to find each of these 48 times and discard all except 4. Commented Apr 29 at 6:49
• @ApexPolenta welcome to the club :) If anything, RobPratt answers keep increasing my interest to learn ILP, haha Commented Apr 29 at 7:37
• @theonetruepath You can avoid the issue of symmetries by fixing the orientation of the piece containing the center cube. My backtracking program finds 8 distinct solutions in about a minute. Commented Apr 29 at 11:16

I like to use burrtools for this type of 3D packing problem.

1. Define two entities, one for your piece and one for the 5x5x5 box
2. Define a new puzzle, marking the box as the 'Result' and adding 25 copies of the piece. (Make sure not to add 25 separate pieces, as this results in a combinatorial explosion)
3. Solve the puzzle. I get 4 solutions in about 75 seconds after removing mirrored and rotated solutions.
• While this is an interesting way to solve the problem, it does not, per se, contain a solution to the puzzle. Perhaps you could edit in a representation of one of the solutions? Commented Apr 30 at 3:49
• But it is an answer to "Optionally, I'd like to know how one could go about solving this systematically." Commented Apr 30 at 8:37
• Unfortunately it's a little difficult to export solutions from burrtools. You basically have to look at it in the 3D view. I didn't have enough time to convert the 4 solutions to a nice image like RobPratt's diagram. Commented Jun 7 at 8:26