弊社のパズル事情

Introduction

Happy New Year! Last year, a small puzzle boom occurred at Nature Architects. In this article, we will focus on two particularly popular puzzles: a wooden assembly puzzle and a packing puzzle. We will showcase various approaches to tackling these puzzles using tools like 3D CAD, 3D printers, and optimization solvers.

Wooden Assembly Puzzle

The puzzle boom began with a single wooden assembly puzzle. I borrowed it from a friend during my student days (about 10 years ago) with the intention of returning it once solved, but it is still in my possession. Since many in our company love puzzles, I placed it in the office sample area.

Exhaustive Search with a Computer

After its placement, a few people attempted the puzzle by hand but could not solve it immediately. Soon after, our chief engineer created and shared 3D data, enabling computational approaches to tackle the puzzle.

The steps taken to solve the puzzle are as follows. While this approach might feel like cheating and not in the spirit of the puzzle, after 10 years of failure, no means could be spared:

1. Identify the assembled (completed) state.
2. Enumerate all possible states reachable from the completed state without interference.
3. If a disassembled state is reached, reverse the sequence to obtain the assembly steps.

As a result of the above steps, two completed states and four states reachable from them were discovered. However, a disassembled state could not be reached, making it clear that the puzzle cannot be solved using translational movements alone.

Interlocking Puzzles

One of our engineers introduced a paper [1] about algorithms for generating similar puzzles.

According to the paper, the wooden assembly puzzle we tackled is referred to in the industry as an "interlocking puzzle." The number of steps required to remove the first piece is called the puzzle's "level."

Finding the steps to solve an interlocking puzzle is classified as an NP-hard problem. As the number of blocks increases, the combinations grow exponentially. However, for the size of our puzzle, it was relatively easy to enumerate all possibilities.

The paper introduced a method for efficiently generating puzzles of any level, and the associated software was made publicly available. Taking advantage of this, we generated a company logo puzzle that can be disassembled in six steps (featured in the cover image).

The paper also dealt with translational movements as the sole operation for solving puzzles. While studies considering rotational movements do exist, interference detection becomes significantly more complex, making computational handling extremely challenging.

Using a 3D Printer

As for the wooden assembly puzzle, it was deemed computationally difficult to consider rotational operations. Instead, we explored the possibility of disassembling the puzzle by 3D printing the completed state.

By manipulating the printed models, we discovered several new states reachable through rotational movements in addition to the translational ones. Unfortunately, no solution was found even with this approach.

Does a Solution Exist?

Frustrated by the difficulty, I contacted the friend who lent me the puzzle. They said:

"My father made it as a hobby, so the design might be flawed. However, I feel like it was solvable at some point."

The puzzle may indeed be flawed, or there might be some unexplored possibilities involving rotational movements. While proving the latter is unlikely is difficult, we currently believe the former is more probable.

Later, we discovered a puzzle on the following website that closely resembles this one. The puzzle described on the site is cleverly designed to be solved with rotational movements: https://puzzlewillbeplayed.com/555Cross/Okey3PieceBurr/

In conclusion, it is unfortunate that we could not solve the puzzle. However, we had a lot of fun exploring the fascinating world of interlocking puzzles.

Packing Puzzle

The most popular puzzle in 2024 within the company was undoubtedly this one. The goal of the puzzle is to fit 24 pieces into the box.

Our CTO purchased it at an antique market, and the font on the lid evokes a sense of its era. Since the puzzle has ties to electronic computing, we felt compelled to tackle it as a company committed to human-computer collaboration.

The shapes formed by connecting equilateral triangles are called polyiamonds [4]. There are 24 types of 7-piece polyiamonds (heptiamonds), and what makes this puzzle beautiful is that each piece is used exactly once.

Several people attempted to solve it, but the only successful human solver (as of the blog publication date) was Engineer Y. The approach seemed to involve filling in 2-3 remaining pieces, swapping parts, and gradually finding the solution.

Solving with a Computer

We attempted to solve the puzzle computationally. Once again, our chief engineer promptly created a 3D model.

Initially, some engineers tried solving it using the CAD environment Rhinoceros/Grasshopper and the optimization tool Tunny, which they frequently use in their work. However, this approach proved difficult. Tunny is a black-box optimization tool typically used for problems with unknown function properties. For a problem like this, where the inner workings are clear, a more suitable approach seemed necessary.

According to a paper [5], burrtools is commonly used as a solver for puzzles, but for problems like this one, general-purpose solvers for integer programming are faster. Therefore, we decided to use Python-MIP, an open-source tool for mixed-integer programming.

Referring to the paper, we formulated the problem as follows. One difference from the paper was that the shapes of the pieces in our puzzle are all distinct, so we added an additional constraint.

1. Assign a number (0–167) to each equilateral triangle in the box shape (see diagram below).
2. Variables
   • The possible placements of piece i are represented using binary variables \(p_i(a,b,c,d,e,f,g)\) based on the triangle numbers on the board.
     (To ensure unique representation, \(a < b < c < d < e < f < g\).)
   • A variable value of 1 indicates that the piece is placed, while 0 indicates it is not.
   • For example, if piece 0 is placed as shown in the yellow area below, \(p_0(0,5,6,16,17,18,34)=1\).
   • The total number of variables equals the total number of placement options for all pieces: 13,667 in total.
3. The following conditions are necessary and sufficient for solving the puzzle:
   • Constraint 1: (Every location is covered by exactly one piece)
     • Constraint for location 0:
       (The sum of variables corresponding to all placements covering location 0) = 1
       That is, \(p_0(0,5,6,16,17,18,34) + p_0(0,6,7,18,19,20,38) + … = 1\).
     • Constraint for location 1:
       (The sum of variables corresponding to all placements covering location 1) = 1
     • ……
   • Constraint 2: (Every piece is used exactly once)
     • Constraint for piece 0:
       (The sum of variables corresponding to all placements of piece 0) = 1
       That is, \(p_0(0,5,6,16,17,18,34) + p_0(0,6,7,18,19,20,38) + … = 1\).
     • Constraint for piece 1:
       (The sum of variables corresponding to all placements of piece 1) = 1
     • ……

The implementation involved preparing solver input based on the shapes in Rhino/Grasshopper, solving the problem with a Python component, and visualizing the solution in Rhino/Grasshopper.

The solution was found in about 10 minutes on a laptop PC.

With 13,667 variables, a brute-force search would require evaluating 2^13,667 = 1.50297×10^4114 combinations, which is impractical. However, the CBC algorithm used by Python-MIP proved to be highly efficient in finding the solution, which is quite remarkable.

From the observed execution speed, it seems likely that humans use an even more efficient algorithm to solve such puzzles. This suggests there is room for further improvement in computational search methods.

Conclusion

In my usual work, I often deal with highly nonlinear analyses and tend to rely on black-box optimization. This experience has been a valuable reminder of the importance of choosing the right method for each problem.

Going forward, I plan to continue enjoying intriguing puzzles with both manual and computational approaches.

References

[1] Rulin Chen, Ziqi Wang, Peng Song, and Bernd Bickel. "Computational Design of High-level Interlocking Puzzles." ACM Transactions on Graphics (SIGGRAPH), 2022. https://sutd-cgl.github.io/supp/Publication/projects/2022-SIGGRAPH-High-LevelPuzzle/index.html.

[2] puzzlewillbeplayed.com. "Okey 3 Piece Burr." https://puzzlewillbeplayed.com/555Cross/Okey3PieceBurr/. (Accessed: January 17, 2025).

[3] Tenyo Co., Ltd. "History of Tenyo." https://tenyo.jp/history.html. (Accessed: January 17, 2025).

[4] Wikipedia. "Polyiamond." https://en.wikipedia.org/wiki/Polyiamond. (Accessed: January 17, 2025).

[5] Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda. "Performance Comparison of Various Solvers Using Formulation of Rep-Tiles." SIG-FPAI-119-01, 2022. https://www.jstage.jst.go.jp/article/jsaifpai/119/0/119_02/_pdf.

[6] @miso_taku. "Mathematical Optimization with Python-MIP Library." https://qiita.com/miso_taku/items/be16af812f3d81486bd4. (Accessed: January 17, 2025).

[7] Python-MIP. https://www.python-mip.com/. (Accessed: January 17, 2025).