Optimal Solution Search for Checkered Origami Triangle Puzzles
Abstract
In this study, we accomplished the enumeration of solutions for each of the patterns of the Checkered Origami Triangle Puzzle. The Origami Checkerboard Triangle Puzzle is a puzzle with the goal of folding a single one-sided colored equilateral triangle sheet of paper into a pattern in which nine equilateral triangles are stacked in 3 rows in as few steps as possible. There are 59 kinds of patterns, and solutions have been found for all of them, however it remained unclear whether better solutions than known solutions exist prior to our research. To clarify this, we conducted an search using a supercomputer. The range of the search is up to 6 steps for start sizes 4 to 7, and up to 5 steps for start sizes 8 and 9. As a result we obtained better solutions for several patterns than the known solutions.
概要
本研究では、Checkerboard Origami Triangleパズルの解の列挙を試みた。 Checkerboard Origami Triangleパズルは、表裏2色の正三角形の紙からできるだけ短い手順で正三角形が3段に9個積み重なったパターンを折り上げることを目的とするパズルである。 このパズルのパターンは59個存在し、それら全てに対して解となる手順が見つかっていたが、それらの解より優れた解が存在するかどうかは本研究の以前には明らかでなかった。 この問題を解くために、我々はスーパーコンピュータを用いた探索を行った。 探索範囲は、サイズ4から7の正三角形からスタートする場合は最大手数6手、サイズ8と9の正三角形からスタートする場合は最大手数5手の範囲である。 探索の結果、幾つかのパターンに対して既知の解よりも優れた解となる手順を得た。