Technologies:

• C++
• GitHub

Summary

This was my first personal project after learning how to code. While working for the University Police, I met a scientist who had an affinity for puzzles and there was only one in his collection that he had never solved. Nor had the previous owner, nor had anyone he ever met!

Later I found this game vendor that said they do not know if anyone has ever solved it without using the solution! Perhaps I should contact them… anyways.

So naturally I was intrigued. I jotted down a few notes about the puzzle. I had completed 3 programming courses at this point and thought it might be worth it to try.

After analyzing the pieces I realized that there were 72 different ways to lay a single piece! No wonder no one had solved it before!

With 25 blocks, this problem has an upper bound complexity of: $$O(25 ^{72})$$

For about eight hours I planned and tried a few different strategies. Then I wrote a recursive algorithm that could produce an answer in a little over 2 minutes. I brought it back to the researcher printed on a piece of paper and built the puzzle with him in his office. I also had the missing piece 3D printed at the library.

Little did I know at the time but I actually used brute force algorithm classified as a “branch and bound” that is used for tackling NP problems.

While I see now that the code is extremely poorly written, I am very proud that I was able to map a real world problem to an algorithm and actually succeed. Especially after several trusted colleagues warned me that the complexity was so high it might not be solvable in a reasonable time period (and had I not used branch and bound, they’d have been correct).

Other questions I have been meaning to explore about this puzzle include:

• Who made it and how did they do it?
• I know that there are at least 6 solutions, but are there more?
• How long would it take to find all solutions?

Here is a link to my repository (please don’t judge how bad the code is. I was young, I didn’t know any better). A friend helped me put together the information and it’s a bit more detailed on how it works there in the readme.

And here is the completed puzzle, constructed as the output of the program specified.