12
$\begingroup$

The puzzle contains 25 identical pieces that look like this:

A puzzle piece

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – RobPratt
    Commented Apr 29 at 1:13
  • 1
    $\begingroup$ @RobPratt 960 ways, actually. 15 planes × 8 orientations × 8 positions in a plane. $\endgroup$ Commented Apr 29 at 1:18
  • 1
    $\begingroup$ @ParclyTaxel Indeed, I was counting only 4 orientations. $\endgroup$
    – RobPratt
    Commented Apr 29 at 1:29
  • 2
    $\begingroup$ @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? $\endgroup$ Commented Apr 29 at 1:30
  • 1
    $\begingroup$ Here's a video: youtu.be/3fBY9TyPaEs $\endgroup$
    – JS1
    Commented Apr 29 at 1:40

2 Answers 2

12
$\begingroup$

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

$\endgroup$
9
  • 10
    $\begingroup$ 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 $\endgroup$ Commented Apr 29 at 4:29
  • $\begingroup$ @ApexPolenta same. Dear RobPratt, do you have a tutorial or manual on how you translate these constraints into code? $\endgroup$ Commented Apr 29 at 6:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 29 at 6:49
  • 2
    $\begingroup$ @ApexPolenta welcome to the club :) If anything, RobPratt answers keep increasing my interest to learn ILP, haha $\endgroup$
    – justhalf
    Commented Apr 29 at 7:37
  • $\begingroup$ @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. $\endgroup$ Commented Apr 29 at 11:16
1
$\begingroup$

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.
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – bobble
    Commented Apr 30 at 3:49
  • 1
    $\begingroup$ But it is an answer to "Optionally, I'd like to know how one could go about solving this systematically." $\endgroup$
    – Florian F
    Commented Apr 30 at 8:37
  • $\begingroup$ 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. $\endgroup$
    – Quantum7
    Commented Jun 7 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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