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.

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.

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.

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

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 | + | | | | | |/ +----+----+----+----+----+----+----+----+----+----+

+----+ / /| +----++----+ | / | | | +----+ | | + | / | | | | +----+ + | | | | | +--| | + | |/ +----+----+ +----+----+----+----+ / 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.