Result of the optimal solution search for Checkerboard Origami Triangle
Kazuki Ohshima†, Ryuhei Uehara‡ and Jun Mitani†
†University of Tsukuba
‡Japan Advanced Institute of Science and Technology
最終更新: 2020/01/04
このページでは、Checkerboard Origami Triangleパズルの最適解をスーパーコンピュータで探索した結果をまとめています。 Checkerboard Origami TriangleパズルはSerhiy Grabarchukにより考案されたパズルで、 小さな正三角形(以降、「セル」と呼びます)9個が3段に積み上げられたパターンを表裏の色が異なる正三角形の紙から折り上げることを目的とするパズルです。 図1に同パズルの解となる手順の例を示します。
このパズルで使うことのできる折りは単純折りのみで、1回の単純折りを1手と数えます。
単純折りは、ある平坦な状態の紙を単一の直線のみによって別の平坦な状態に移す折りのことを指します。
このパズルでは紙が複数重なっていた場合に1回の単純折りで折る紙の層の数に制約はありません(Some-layers simple foldと呼ばれる折り操作です)。
※折り操作に関する補足
ゴールとなるパターンは、各セルに割り当てる色の組み合わせから対称性による重複を取り除くと全部で59あります。 これらの全てのパターンに対して、そのパターンを折り上げるための手順(「解」と呼びます)の存在が確認されています。 1つのパターンに複数の解が存在する場合には、折りの手数が少ないものの方が優れた解であるとします。 また、折りの手数が同じ場合には、元の紙の大きさが小さい方を優れた解であるとします。 これまで、各パターンに対する最も優れた解が石野氏のWebページで公開されてきました。
今回、JAISTのスーパーコンピュータを使用し、元のサイズが4から7の場合について手数6手まで、サイズが8と9の場合について手数5手までの範囲で解の探索を行い、 いくつかのパターンに対して、既知のものより優れた解を見つけることができました。 ここで、「サイズn」というのは正三角形の積み重なっている段数がn段であることを言います。
下記表中のパターンをクリックすると折り手順が表の下に表示されます。
他のリンク
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 選択したパターン | #01 |
| 手数 | 3 |
| 初期のサイズ | 4×4 |
| 解の総数 | 3 |
折り操作に関する補足
石野氏によるこのパズルの解をまとめたページに掲載されている既知の解の手順では、 図2に示す#02と#06の解がサイズ4の正三角形からスタートして3手で解に到達する手順になっています。 一方、本研究の探索結果では、#02と#06に対する最良の解はサイズ4の正三角形からスタートして4手で解に到達する手順となっています。 この違いは折り操作における「1手」の定義の解釈に起因しています。 Origami Checkerboardパズルのページに書かれている折り操作のルールには「1回の折りでできる折り線は、その操作の時点でひとつの線分であること」という項目があります。 例えば、図3のような状態があったとき、2つの白い領域(A, B)を谷折りするのは2手になり(1つずつ折るため)、 黒い領域と白い領域(A, B, C)を同時に折るのは1手になります(黒い領域を折ると、必然的に白い2つの領域が一緒に折られることになるため)。 本研究では折り線の両側それそれで動かさない領域と動かす領域を1つずつ選んだとき、それらの領域の間に折り操作の「ひとつの線分」があると解釈しています。 また、それ以外の領域が動くかどうかは選ばれた2つの領域の動きと位置関係によって決まります。 この解釈に従うと、図4に示すように#02と#06の既知の解の3手目の折りは(a),(b),(c)のいずれかの状態となり、(d)のようなパターンを成す状態になりません。 そのため、探索結果が既知の解と異なっています。
