Solving Foam Cubes

28 Dec 2017
Progress: Complete

This Christmas I was with a couple of friends and exposed for the first time to a little 3D jigsaw puzzle, a collection of EVA foam pieces that assemble into cubes.

These things are deceptively simple-looking, and the hardest of the six colours took me a good bit of thinking to get together. But there were more challenges listed in the instruction book, such as cuboids, one big cube, a podium shape, and – one that caught my eye, because it was labelled as 'difficult' – one small cube using one piece of every colour. That's really hard to brute force, because you've got the biggest number of pieces available, and the smallest structure to build.

Well the suggestion was made to find the solution using computers, and so out came the laptops and the coding began.

I immediately turned to javascript because I'm comfortable with it and in my experience, thanks to the millions that have been poured into it, it's much faster than other scripting languages.

Notation

The first thing to decide is how to represent the pieces in memory. There's a tradeoff between being efficient, being easy to enter, and being easy to use and think about. I went for one string of zeros and ones as my initial notation, starting at the top left corner of a piece and working clockwise. The reasoning was that this is easiest to enter: I could just pick up a piece and type it in quickly, and if the notation doesn't work out we can convert it later.

There are five bits to a side, but the corner bits are shared with the other sides, so they overlap.

Though string manipulation is temptingly easy I immediately split these into arrays of zeros and ones. (It's also tempting to squish them all into one big binary number and do everything bitwise, but working without bitwise addressing would probably make life harder.) Sooner or later we need to flip and rotate these pieces, and one advantage of this method is that to rotate we just shift all the digits along by four. To flip we need to reverse the array, and shift it by one, because the first corner is not repeated at the end.

For simplicity I decided to pre-process all permutations, so the bag contains all 8 possible orientations of a piece and we don't need to keep rotating and flipping pieces when it comes to the algorithm later.

Many pieces have some amount of symmetry, and to reduce the overhead I had it prune the set down to unique pieces after all the permutations had been rendered. For reasons that will become apparent later, this was a silly idea and I changed it back to a full set soon after. Six colours, six pieces per colour, and eight orientations per piece, that's 288 members in our set.

Visualization

I did this as soon as possible because I knew that before long it would get extremely confusing looking at zeros and ones. The sooner we can display what the pieces look like, the sooner we can weed out the mistakes.

The drawing routine is very simple, it could be optimized but we don't care (visualization will be a tiny fraction of the computing power needed to solve the 3D puzzle), it just draws a central rectangle then walks in a loop around the piece and plots a square there if there's a one in the array. It would have been a little more effort to get it to draw the outline of the piece, but this is fine. I also rendered it at half opacity, thinking that we could see if pieces overlap when it comes to sticking them together (but as it turned out I didn't do any rendering like that).

I added a scale parameter, and then visualized the eight orientations of a piece at 1:1 scale, so that I could hold up a piece to the screen and directly verify it was rotating and flipping correctly. It can become all too easy to think it looks right (or wrong) when it's wrong (or right) if you're doing it all in your head.

Connections

Do two pieces fit together? To check this we need to take a slice out of the array of each piece that corresponds to the sides that are touching, and since the notation goes clockwise, one of those slices may need to be reversed. Then we see if the zeros and ones mesh nicely.

This is the perfect time for the XOR operator: we want ones for every slot, from one piece or the other, but not both. Excellent. But it soon turned out to be a little trickier than that. For connecting two pieces together it's fine, but in three dimensions there are three pieces meeting at each corner. The logic for the corners then has to be modified into, well, a triple XOR, but that's not possible to implement when only two pieces are being checked. My solution was to do a NAND for the corners when two pieces are pushed together, meaning that the space can be empty or filled, but not filled by both pieces, and then go back and do an OR for the corner once the third piece is present.

The Net and the Big Tree

Rather than do things in real 3D, I figured it was quickest to lay out the cube as a net where conditions are set for the edges having to match up. The big disadvantage to a net is that there are many different ways of unfolding a cube into a net, even the same shaped net with the cube in different orientation, and our pieces are all preprocessed into different orientations too, and so two nets filled with apparently different pieces in different places might actually represent the same solution. It would take some serious brain power (and maybe computing power) to identify one net being different to another. But thankfully we're not looking for all the different solutions, we're looking for the first solution we can find.

Our algorithm needs to do the following:

• Choose a piece and place it on the net
• Check the conditions for that position on the net.
  • If the piece doesn't fit, remove it from the net, go back and choose another piece
  • If it fits, move to the next position, choose a piece there and check it fits its conditions, and so on

Each time we place a piece we remove it from the bag. At this point I realized I'd shot myself a bit with the preprocessed orientations and removing symmetrical stuff, because we now have a whole load of pieces to remove from the bag. But by not doing the unique filter, and knowing there are 8 orientations per piece and they were added in order, we can just mark the entire block of 8 as used and our problem is solved.

The algorithm sort of makes a tree structure of decisions, because a whole bunch of pieces might fit only to get to a dead end with no pieces left, in which case it has to back out of the loops, removing the pieces as it goes, and then continuing on a different branch.

There are only six places on the net so we could do it with six nested loops, but instead I made a single function with a single loop and some counters. The hitch is that the conditions are different for each position, so I made an array of function pointers which can be called at each position in the net.

To remove pieces as it backs out of a branch, it's easiest to just cache the net and the bag at every branch point and restore it when we take a new piece. The arrays are tiny so it's negligible memory use.

Right, so all that was left at this point was to actually specify the conditions for each piece in the net. Matching the top of one piece to the bottom of another is easy, but where the brain power is needed is that matching a side of one piece, let's say the top of the cross-shaped net, up against the top of another piece, such as one of the arms of the cross, means that one of those edges will need to be reversed. We basically need to specify both the edge and the direction that the pieces are to be matched. And then we have to go and check that the corners are properly filled, like we promised we would up above.

What would make this all much easier is to have a proper notation to describe the net: what edge goes where and which way around. But at this point I was feeling the time pressure – I was about three hours in, and the whole thing is only worth doing if the combined time of developing and running the program is less than the time it takes a human to solve the puzzle manually. So I hastily filled in all the other conditions for the cube net by hand.

The Mucky Run

Finally we ran the program and saw our first net. At this point I'd only inputted the six red pieces, but that's enough for one cube, and the output of the program looked like this.

Ah, a wonderful feeling to reach for the real foam pieces and try this out (and find that it works).

Once that was confirmed I then had to spend the time typing in the details for the rest of the pieces, which didn't take too long, and finishing the visualization bit to draw them in the right colours.

Exciting! There are a lot of mixed solutions, using just a few of one colour and some of another. The program in its hacky inefficient state took about five minutes to find the first 20,000 solutions, among which there will be many duplicates. At the end of that run, the outermost loop was at index 13. There are 48 red piece orientations, so I suppose we can consider there to be about 70 thousand buildable cubes that include one red piece.

Rather than do any more work, I did the fastest thing I could think of here: look through the solutions for anything that featured just one of each colour...

The Answer

Result! First matching solution was at index 3296.

Immediately we turned to the real foam pieces and stuck it together. Hurrah! Mission accomplished.

Just as a last change to the program, I made it mark every element in the block of 48 as used when it places a piece, so that it only finds correct all-colour solutions. There are a lot of valid solutions, some of which are very similar to each other (such as flipping a symmetrical piece).

Since I wrote it all in a synchronous fashion, to get it to run for more than a few seconds I have to keep hitting the 'continue' button since browsers have a watchdog that catches scripts that it thinks have hung. One fix would be to change it all to be asynchronous with a bunch of setTimeout callbacks, but better than that would be to run the routine in a separate thread using a Web Worker. Not to leave the reader disappointed, I chose to do the latter. And here it is – click Start to begin searching for solutions. The animation does slow it down a bit, but it looks cool.

Start

So, that was our little boxing day activity. The next step, if we wanted there to be one, would be to solve the other challenges in that instruction manual, which would mean having a standardized way of inputting a net. Another nice little thing to add would be 3D visualization of the final result.

If you examine the source code, you'll find it to be a complete mess. Which is perfect! This type of project embodies what a lot of people fail to grasp about efficiency and tidiness. The task is to minimize the total combined time spent on developing the program and running it. Since it finds the solution in under a minute, and it took me a few hours to write, any time spent trying to optimize it is time wasted. The source code on this page is left exactly as I left it when we hit the first solution, plus a tiny bit of bodging to get it into the web worker and show the animation.

One more thing

Shortly after writing this I added one extra little bit. There are many, many solutions coming out of that program. Even ignoring symmetry there are repeated solutions. If you imagine rotating the cube before unfolding it out into a net, you can visualize how different two nets might look while actually representing the same cube assembly. But if we make one simple assumption, that there is only one way of assembling any six pieces (and, of course, its complement: turning the cube inside-out) then we can easily throw away the duplicates by listing the unique pieces in the solution. This is as simple as switching each piece in each solution with its base rotation (so modulo 8), and sticking them into an ordered list.

Using this method, the program output just 21 solutions. Interesting! The assumption may be wrong, but this suggests there are just 42 correct answers to the problem.