Optimal Solution Search for Origami Checkerboard Puzzles
Abstract
In this study, we accomplished the enumeration of optimal solutions for each of the patterns of the Origami Checkerboard Puzzle in a range of grid size from 4×4 to 9×9 with up to six steps. The Origami Checkerboard Puzzle is a puzzle with the goal of folding a single one-sided colored square sheet of paper into a 3×3 checkerboard pattern in as few steps as possible. There are 50 kinds of patterns, and solutions have been found for all of them, however it remained unclear whether the solutions were optimal prior to our research. To clarify this, we conducted an optimal-solution search using a supercomputer and obtained the optimal solutions for each of the patterns in a range of grid size from 4×4 to 9×9 wip up to six steps.
概要
本研究では、開始格子サイズ4×4〜9×9、最大手数6手の範囲でOrigami Checkerboardパズルの 各パターンに対する最適解の列挙を試みた。Origami Checkerboardパズルは、表裏2色の紙から できるだけ短い手順で3×3のチェッカーボード模様を折るパズルである。ゴールのパターンは50種類あり、 それら全てに対して解となる手順が見つかっていたが、それらが最適解かどうかは本研究の以前には 明らかでなかった。この問題を解くために、我々はスーパーコンピュータを用いた最適解探索を行い、 スタートの格子サイズが4×4から9×9まで、最大手数6手の範囲で、各パターンに対する最適解を得た。