Interlocking puzzles.

The story

My interest for Interlocking puzzles began with a challenge between Bram Cohen and Richard Gain (see here for the full story. Also have a look at the interlocking models by Richard Gain and friends in his microcubology website). In short, the challenge was to design a 4x4x4 cube puzzle with 4 pieces, so that you need more than 1 move to remove the first piece. In addition, all pieces must be "printable without support", which means that you can print the pieces with a regular 3d printing machine with no overhang.

Apparently, Bram Cohen found a puzzle where you need 4 moves to remove the first piece (this one). I gave a solution where you need 5 moves to remove the first piece here, which is following.

To find this solution, I wrote a specific algorithm, that I will describe next.

The algorithm

To understand the algorithm, one first notices that a puzzle can be described by a 4x4x4 array of digits: a cell contains the digit N if, in the solution, this cell belongs to the piece number N. If the cell is empty, just put the number 0 (by convention).

First, one needs to solve such a given puzzle. This is not very difficult. For each piece, we compute all the possible moves, and record the position of the puzzle after this move. If one can "remove" a piece from the position, we remove it, and continue the process. We therefore obtain a graph of configurations. The puzzle is solvable if one can remove all pieces, and the score of the puzzle is the minimal number of moves one needs to remove all pieces. I use a standard Dijkstra algorithm on the graph of configurations to compute this number.

Next, we look for the "best" interlocking puzzle, that is the one with the highest score. Unfortunately, the total number of a four-piece puzzle is of the order 4^(4x4x4) ≃ 3 x 10^38... It is therefore impossible to test all puzzles with a computer, and one needs to find another way to explore this large amount of possible puzzles.

I chose a genetic algorithm to do the exploration. This algorithm works as follows. First, we start from a 4x4x4 array with all empty cells, and we repeat the following steps:

• Select a cell at random, and flip its digit also at random.
• Compute the score of the new puzzle.
• If the score is equal or better than the old score, we accept the flip. Otherwise, we cancel the flip.

In practice, if one runs this algorithm, the final puzzle can be quite disapointing. The problem is that it can be stuck in a crap puzzle, with no way of improving it. So one usually needs to run the algorithm a large number of time to find a meaningful puzzle.

Luckily for me, the super-computer of my research lab (Ceremade at University Paris-Dauphine) was available. So I could run the algorithm (an improved version of it) an insance number of times, and I got very interesing puzzles, including the one of the challenge.

I then looked for more interlocking puzzles, with different parameters. Here are some of them.

The 4x4x4 puzzle with 3 pieces.

My favorite one is the following one (here on thingiverse).

This puzzle only has 3 pieces, but it usually takes between 20 minutes to several days to find out how to assemble them. You need 10 moves to remove the first piece, and 4 other moves to remove the second piece.

This puzzle is my favorite one. I am very happy to see that people seems to like as well. Rzvvl2 even made a beautiful wood copy of it here.

Here a colored version of it.

A 5x5x5 puzzle with 3 pieces

This next puzzle also have 3 pieces, but it is larger (5x5x5 cube). You need 13 moves to remove the first piece, and 9 to remove the second one.

A 4x4x4 puzzle with 4 pieces

Finally, here is a 4x4x4 cube with 4 pieces (here). You need 13 moves to remove the first piece, 4 to remove the second one, and 7 to remove the last piece). You will need some time to solve it...

What next

In my algorithm, I did not consider the possible rotation of the pieces. It would be awesome to program such moves in order to find beautiful and hard puzzles. Unfortunately, I have no idea how to neatly compute the rotations... Please contact me if you have some ideas

Back to my puzzle page.