3D pentomino solver program

Some time around 1999, I bought a plastic pentomino set at a game store. The kind with twelve pentomino shaped plastic pieces that you have to arrange in a 6x10 rectangle. On bringing it home, I immediately dumped the pieces out, and found myself unable to arrange the pieces back in the 6x10 rectangle. I spent hour trying to solve it. Worse yet, somebody else solved it on me! I eventually ended up writing a program to solve it for me. The program was a great success, on a P3 700, it could compute all 5000 odd unique solutions to the puzzle in under two minutes. It had not occured to me that there could be that many solutions. over 20,000 solutions if you count flipping the whole puzzle. Ever since, computerized heuristics for physical puzzles have fascinated me.

I subsequently decided to try a greater challenge: 3d pentominos. And by 3d pentominos, I didn't just want to take the flat mentominos and make them out of five cubes. I also included the non-flat pentominos (I guess this does stretch the term "pentomino" a bit). At any rate, my pieces comprised of any unique shape you could make if you glued five cubes together at their faces in various patterns.

Some of the 3d "pentomino" pieces

It turns out there are 12 flat pentominos, and 17 non-flat 3d shapes. This makes for 29 pieces in all. Because 29 is prime, this didn't make for a lot of ways to arrange them in a box. So I added an extra five cubes, in the form of a 1x1x2 plus a 1x1x3 cube piece. Having those extra pieces really helps when solving the puzzle by hand.

With the addition of the extra five cubes, the number of cubes is 29*5+5, which is 150. This divides nicely into several factors. I decided that the challenge should be to put the pieces in a box the size of 10x5x3 cubes.

The box to put the pentominos in

I made a box that these will fit in fairly exactly. The inside of the box is actually 1.5 milimeters bigger in each direction than what the sizes of the pentominos add up to, to allow for imprecisions and size changes in humidity. The basic cube size is 18 mm.

At this point, I hadn't written my computerized 3d pentomino solver yet. However, I did manage to solve the puzzle several times. The addition of the 1x1x2 and 1x1x3 pieces actually makes the puzzle reasonable to solve by hand if you save them till last. At least I managed to solve a few times, where I have yet to ever solve the 2d pentomino problem by hand once. I also have yet to see anybody else hand solve the 3d pentomino set (my pride is regained!). the trick to solving it is to not solve it bottom up, but to start on the narrow side of the box, and work your way to the other side. Also helps to save the pieces that are easy to place till the end, especially the 1x1x2 and 1x1x3.

Around August of 2002, I finally started working on a solver for the 3d pentomino puzzle. I started out by writing an ascii graphics 3d cube pieces renderer.

  +----+
 /    /|
+----+ |
|    | |
|    | +----+
|    |/    /|
+    +    +----+
|   /         /|
|  +----+----+ |
|  |         | |
+--|         | +
   |         |/
   +----+----+

Sample ASCII rendered pentomino

Next step was the solver heuristics. This turned out to be much harder than the 2d solver program. There are more than twice as many pieces, with more than twice as much room to put them in, and a maximum of 24 orientations, vs. only 8 orientations in 2d. I also had to modify the heuristics somewhat, so that the solver would be smarter in terms of backing further out of stupid piece placements once it detected them. With the 2d puzzle, stupid placements became apparent much more quickly, so I didn't have to be as smart about backing out of them fast.

          +----+----+----+----+----+----+----+----+----+----+
         / 13   13 / 4  / 8  / 9  / 29   29   29 / 30   30 /|
        +----+    +----+----+    +----+----+----+----+----+ |
       / 3  / 13 / 11 / 9    9    9  / 17 / 23   23 / 27 /| |
      +----+----+----+----+    +----+    +----+----+----+ | +
     / 2  / 10   10 / 15 / 9  / 17   17   17 / 24 / 26 /| |/|
    +----+    +----+----+----+----+----+----+    +    + | + |
   / 10   10 / 5    5  / 12 / 20   20 / 24   24 / 26 /  |   |
  +----+    +----+----+    +----+    +----+----+----+   +   +
 / 6  / 10 / 6  / 12   12 / 14 / 20 / 19 / 21   21 /|  /|   |
+----+----+----+----+----+----+----+----+----+----+ | + | + |
|    |    |    |         |    |    |    |         | | | |/| |
| 6  | 10 | 6  | 12   12 | 14 | 20 | 19 | 21   21 | + | + | +
|    |    |    |         |    |    |    |         | | |/  |/
+    +----+    +----+    +    +    +    +----+    + | +   +
|              |    |    |    |    |    |    |    | |/|  /
| 6    6    6  | 0  | 12 | 14 | 20 | 19 | 25 | 21 | + | +
|              |    |    |    |    |    |    |    |   |/
+----+----+----+    +----+    +    +----+    +    +   +
|                   |         |    |         |    |  /
| 0    0    0    0  | 14   14 | 20 | 25   25 | 21 | +
|                   |         |    |         |    |/
+----+----+----+----+----+----+----+----+----+----+

A solution to the puzzle

However, just printing the finished solution still didn't make it clear how the solution actually fit together, because many pieces would be hidden from view. So I then had to write more code to actually generate assembly instructions for any one solution. I did this by sorting the pieces by some arbitrarily chosen measure of Z order, and then showing the partially assembled solution, and the piece to be placed next at each step. The piece shown separate is the next piece to be placed, and the shaded piece in the partial solution is where that piece is to be placed.

            +----+
           /    /|
    +----++----+ |
   /      |    | |
  +----+  |    | +
  |   /   |    | |
  |  +----+    + |
  |  |         | |
  +--|         | +
     |         |/
     +----+----+
          +----+----+----+----+
         / 13   13 / 4  / 8  /|
        +----+    +----+----+ |
       / 3  / 13 / 11 /|    | |
      +----+----+----+----+ | +----+----+----+----+
     / 2  / 10   10 / 15 /| |/ 16   16   16 / 22 /|
    +----+    +----+----+ |-+----+    +----+----+----+
   / 10   10 / 5    5  /| |  11 / 16 / 18 /|   / 28 /|
  +----+    +----+----+ | ++----+---+----+ | 2+----+ |-+
 / 6  / 10 / 6  /|    | |// 14 /|   |    | |  |    | |/|
+----+----+----+ | 5  | ++----+ |16 | 18 | +--| 28 | +----+
|    |    |    | |    |/||    | |   |    |/ 22|    |/ 28 /|
| 6  | 10 | 6  | +----+ || 14 | +---+----++----+---+    + |
|    |    |    |/ 0  /| ||    | |  / 18 //\\\\/|2 / 28 /  |
+    +----+    +----+ | ++    + |-+----++----+\|-+----+   +
|              |    | |/ |    | |/\\\\\\|\\\\|\| |    |  /
| 6    6    6  | 0  | +--| 14 | +----+\\|\\\\|\+ | 28 | +
|              |    |/ 14|    | |\\\/\\\|\\\\|\| |    |/
+----+----+----+    +----+    + |\\+----+\\\\+\|-+----+
|                   |         | |\\|\\\\\\\\\|\|
| 0    0    0    0  | 14   14 | +--|\\\\\\\\\|\+
|                   |         |/   |\\\\\\\\\|/
+----+----+----+----+----+----+    +----+----+

You can look at a Sample Solution with assembly instructions of the whole puzzle here. This is basically what my program spits out for a solution.

Its very satisfying to assemble a solution like this, especially when you know how hard it is to solve by hand.

I have also given away several pentomino sets like the one I made as gifts. Having a ready solution to actually pack it up with helps - it would be unconvincing to give a puzzle away in an unsolved state, and I can't solve the puzzle at will - its very much a matter of luck. The puzzle is very tempting. If its lying on the table unassembled, there are few people that won't attempt to put the pieces back in the box.

You can downlowd the 3d-pentomino.c source code here. Compiles fine with Microsoft visual C or Gnu C compilers, run under Windows and Linux unmodified. Should run on just about any system that has a C compiler, as it does all of its output in ascii.

You can also play with my 2D pentomino solver I mentioned 2d-pentomino.c. After I wrote that one, I looked on the web and found other 2d pentomino solvers, but none was as fast as this one. Also note that the 2d pentomino solver uses unaligned access, so it won't work on computers based on the Dec Alpah or ARM architecture, both of which are extremely rare for general purpose comuters.

Back to technical hacks page