In a moment's whim I took apart one of my friend's burr puzzles. I thought that assembling it would be easy, since it had a clean symmetric shape. That was a big misjudgement.

Each of the 18 pieces is full of asymmetry, and no two pieces look the same. I'm not an expert on these kind of puzzles and even after a good hour of working the best I got was 8 pieces assembled. It was quite clear that I wouldn't ever be able to solve it by hand. And more, it turned out that the puzzle hadn't even come with a solution leaflet.

I hate to leave things lying apart, so I wrote a program that solves the damn thing. Naive analysis tells me that there are%$12!\cdot6!\cdot8^{18}\cdot\frac{2}{6}\approx2.072e27$% possible configurations to have the pieces in, which by itself is too huge a space to go through. Fortunately I don't have to search all of it, but the question is how effectively can the tree be pruned? I implemented a basic backtracking solver that would examine the state space and look for a collision-free solution. From there, I still would have to figure out the proper assembling order, but I supposed that's something I could work out by myself.

Knuth's work is something that never lets you down on Computer Science. I read Vol.4, Fasc. 2 of TAOCP on permutations, which gave a solid base for a simple tree-pruning search technique. I added in a few "optimizations" of my own to even better reduce the possible tree size. The solver required approximately 1200 lines of code and one night of coding, and soon the search was on.

Since last Monday, the program has been churning out through permutations and orientations of the 18 pieces, day-and-night. The current status can be seen in the above picture - 17 pieces, but the last one doesn't fit! In fact, so far I've found more than 12 different configurations of 17 pieces, but none can fit the last piece. Then yesterday, the solver finally reported that it had exhausted the whole search space and no solution was found. Great, so that meant either my shape input data was wrong to begin with or that I was pruning the tree too aggressively and lost the real solution in the process.

To assure that the placement of the blocks was correct, I wrote another program to visualize the shapes in their proper configurations. With that aid, I could easily check that each position and rotation of the blocks matched the problem correctly. It all turned out to be fine, which meant that the problem must lie in the search method. How catastrophic!

Debugging the correctness (and optimality) of a tree-pruning stack-based backtracking search is not the easiest thing. The "optimizations" I mentioned above were a bunch of ad-hoc rules, like "if the 4 pieces on a single major axis block the line-of-sight of the 4x4 inside cube, go to next orientation." This kind of check could be done with a single comparison of the current block orientations without having to plot any blocks on the search grid. It provided to be a huge speed-up, but unfortunately my implementation of it was logically faulty in more than one way. Finally I realized that the check had too many corner cases (literally!) to actually be useful and for now I've disabled it.

The current progress is that I'm still searching. Estimated time required to go through the whole search space is about 24 days on a 1.6GHz desktop computer. To speed up the search, I've broken up the search space into several work packets and have distributed the workload on several computers. I suspect I will have the solution in a few days, although it is not guaranteed.

Edit: Barely after finishing this entry, Mutjake contacted me with his results. His computer has found the correct solution already! Thanks to Andemoni, Au-heppa, DH-, Gexi, hcp, Larsse, Maastonakki, Markku, Mutjake, NoXiouS, Tice and everyone else for participating in the distributed search, it was a fun project! You can see the final result below.

Last Updated (Wednesday, 28 November 2007 02:41)