展開図に基づく折りたたみ方の数え上げを「形態数」と呼ぶこととし、図 1 左のを全て列挙する（1 が割り当ての展開図に対して「形態数は 1 である」られた面が一番下に、N が割り当Countingと言うことにします）。

てられた面が一番上に配置される

theNumberofUnique

ものとする）。

Configurations of Flat-Folded Origami(4) (3)で列挙された順番で面を重ねReconstructed from a Crease Pattern

たときに、同じ形態となるもの除いて、ユニークな形態をのみを数

三谷 純
Mitani Jun

図 1. 形態数 1 の展開図とその折り方

それでは、図 2 左の例ではどうでしょう。2 本の谷折線がありますが、どえ上げる。
以降では、各手順の詳細を説明します。

ちらを先に折るかによって、右側に示

手順(2)は、展開図に含まれる頂点が折紙作品とその展開図の関係は極めすように 2 つの異なる結果となります。

「局所平坦条件」を満たしていれば次て密接で、複雑な折紙作品の創作には従って図 2 左の展開図の形態数は 2 での方法で容易に求めることができます。

展開図に対する深い考察が必要不可欠す。

はじめになものになっています。最近では与え展開図を平坦に折りたたんだ時のられた展開図だけを手がかりに、そこ形状の求め方：ある面を開始面としから形を折りあげる「展開図折り」もて隣接する面を巡回する。その際多くの方に親しまれているようです。に、折線を跨ぐたびに、その折線で図 2. 形態数 2 の展開図とその折り方隣接面を山折りなら 180 度、谷折りれば、それを開いて得られる展開図は

このような簡単な例では、実際に折なら-180 度回転させる。

言うまでもなく 1 通りに定まります。って形態数を数え上げることが可能ででは、その逆はどうでしょう。つまり、すが、複雑な例になると数え漏れが出

1 つの展開図が与えられた場合に、そてくるかもしれません。そこで、コンいこから折りあげられる作品は 1 通りにピュータを使って全ての形態数を正確(http://mitani.cs.tsukuba.ac.jp/pukiwiki-決まるでしょうか。もし 1 通りに決まに数え上げることを試みました。そのoripa/) というソフトウェアにも実装さらないとしたら、可能な折り方を全て方法と結果を以降で紹介します。

れており、鶴の展開図に適用した結果折紙作品の形が決まっているのであタを使って答えを見つけよう、というのが今回のテーマです。

コンピュータを用いた数え上げ手法
今回、形態数を数えあげるためにコンピュータに実装した処理の手順を次の(1)～(4)に示します（以降の説明で形態数の数え上げ問題
ここでは対象とする折り方を平坦折りとし、折り線には予め山谷の区別がつけられているものとします。まず簡単な例を取り上げることで、問題をわかりやすくまとめてみましょう。

「面」とは折り線で囲まれた領域を指すこととします）。
(1) 山谷の区別がついた展開図データを用意する。
(2) 展開図を折った後の面の位置と向き（表面が上を向いているか下を図 1 左の展開図は、誰が折っても右向いているか）を求める。

側に示す 1 通りにしか折ることができ(3) 1～N（N=面の数）の重なり順をません（以降では、異なる折り方の数るORIPA

は図 3 のようになります。折りたたま数え上げるにはどうしたらよいでしょうか。この問いに対して、コンピューこの処理は Web 上で一般公開して各面に重複無く割り当てたときに、展開図の山谷条件と矛盾しないもれた後の形を正しく得られることを確認できます。ただし、この時点では面の重なり順は求まっていません。

折り紙を扱う上で非常に厄介な問題上げます。形態は（少しわかりにくいとして、複数の折り線が同じ位置に重表現かもしれませんが）「干渉する位置なる場合の扱いがあります。図 5 のよ関係にある 2 面間の上下関係の集合」

うに一箇所に折り線が重なるケースでで表すことができます。このような関は、F2 と F3 が接続する(a)はよくても係を表すには行列を用いると便利です。

F1 と F3 が接続する(b)は問題となりま

そこで、以下に述べる処理を行います。

す。紙幅の都合で詳しくは紹介できま

まず、折りたたんだ後の 2 次元平面せんが、このような場合でも F1 から順において、2 つの面が互いに干渉するに面を重ねながら、面の向きと折線のか否かを表す N×N 行列 Mmask を作成

山谷、および折線を介して接続する面します。Mmask の各要素の値 mij は次の(a)展開図、(b)面の向きによって色の位置をチェックすることで、F3 までように定めます。

分けされた展開図、(c)折りたたみ後の面の重ねた時点で面の干渉（(b)のケース）位置、(d)透過色で塗りつぶしを行った様子を発見することができます。

⎧1 F とF jが互い干渉する (i ≠ j )mij = ⎨ iそれ以外⎩0

図3

次に、手順(3)で得られた重なり順に手順(3)では、N 個の面に 1～N の重基づいて、面間の上下関係を行列なり順を割り当て、展開図から得られMorder で表現します。Morder の要素 mij

る情報と矛盾するものを省きます。調図 5. 折線が一箇所に集中する場合、面のは次のように定めます。

べるべき順番の割り当て方は単純に考重なり順によって正しく折れる場合(a)とえると N!の場合の数があり、これは面そうでない場合(b)がある。

⎧ 1 (Order ( Fi ) > Order ( F j ))⎪(i = j )mij = ⎨ 0⎪− 1 (Order ( F ) < Order ( F ))ij⎩の数が多くなると爆発的に大きな数にさて、以上に述べた方法で展開図となってしまうことを意味します。たと矛盾の無い重なり順を全て求めること

Order(F)は面 F に割り当てられた重えば、面の数が 18 の兜（図 8(c)）のができます。

なり順で、Order(Fi)>Order(Fj)であれ

例では 18!=6.4x1015 となり、コンピュ

ところが、図 6 のようなケースでは、ば、面 Fi が面 Fj より上の番号を持っータを使ってもとても調べ切れません。

異なる重なり順の割り当て方、ていることを意味します。続いて、次

そこで、面を（スタックに）下から

F1<F2<F3 と F1<F3<F2 が同じ形態を表のような成分同士のかけ算を行う演算します。

× を定義します。
子○

順番に積み重ねていきながら、矛盾が生じた時点で積み重ねを終了し次のケ× B の(i, j)成分 cij = aij bij
C=A○ースに移行する、という処理を行うこ× Morder以上の定義に基づき、Mmask ○とで、無駄な処理を効率的に枝刈りし、を行うと、互いに干渉する位置にある調べあげる対象の数を大幅に減らすこ

面同士の上下関係だけを表した行列とを行います。
「矛盾が生じる」というのは、例えば図 4 のように、上の面が下の面の折線を覆い、正しく折りたためないようなケースを言います。

図 6. 得られる重なり順が 2 つ、形態数が 1 の例（つまり 1 つの形態を表した行列）が得られます。従って手順(3)で得られる異なる重なり順が、同じ形態を表す解を表すそれぞれの Morder に対して理由として、互いに干渉する位置に無× Morder を求め、Mmask○ユニークな解のい面（図 6 では F2 と F3）の存在が挙数を数え上げればよいことになります。

げられます。互いに干渉しない（離れ図 4. 折紙の断面を見たところ（点線は面のつながりを表す）。面 F1 の折線 e は上の面とつながるべきだが、その上に面 F2が覆いかぶさっている。

た位置にある）面にとっては、どちら数え上げの具体例の重なり順が上でも折りたたまれた結先に述べた手順(4)の説明を改めて具果には影響を与えないのです。

体例を元に説明します。対象として図そこで手順(4)によって、重複するものを除き、ユニークな形態だけを数え7 の折りたたみ方を考えることにしましょう。

1]⊗ Μ maskΜ [orderことが判明しました。兜の例では、4=Μ万近くの妥当な重なり順が求まりまし[ 2]order⊗ Μ mask3]= Μ [order⊗ Μ mask

たが、最終的には 9 つの形態が見つか⎛ 0 − 1 − 1 − 1⎞⎜⎟
⎜ 1 0 0 − 1⎟=⎜
1 0 0 0⎟⎜⎟⎜1 1 0 0 ⎟⎝⎠りました。この値が果たして正しいものであるか、試しに折ってみたところ、
図 9 に示すように、確かに 9 通りある

このとことから、図 7 に示す展開図の形ことが確認できました。

態数は 1 であることがわかります。

図 7. 面が４つの例題

まず手順(2)で折りたたみ後の各面の位置を算出し、面の位置から互いに干渉す実験結果る面の対を調べます。図 7 の例では、F1

今回提案した手法を実際に図 8 に示と{F2,F3,F4}が重なっており、F2 と{F1,F4}、す 4 つの展開図に対して実行した結果

F3 と{F1}、F4 と{F1,F2}が重なっているので、は表 1 のようになりました。

Mmask は次のようになります。
⎛0⎜⎜1Μ mask = ⎜1⎜⎜1
⎝

100
1

1000

図 9. 例題。(a)(b)は単純な例、(c)は兜、(d)1⎞⎟1⎟0⎟⎟0 ⎟⎠は鶴の展開図の半分鶴の半分の展開図では、ただ 1 通りしかないことがわかりました。

手順(3)で述べた総当たりの方法で得おわりにられる重なり順の解は以下の 3 通りです。
解[1]: F1<F3<F2<F4

鶴の半分の展開図では、ただ 1 通り

解[2]: F1<F2<F3<F4しかないことがわかりましたが、では

解[3]: F1<F2<F4<F3

鶴の全体の展開図ではどうでしょうか。

これらの解のそれぞれの行列 Morder は

実は、実験を行ってみたのですが、今
図 8. 例題。(a)(b)は単純な例、(c)は兜、次のように表されます。
⎛ 0 − 1 − 1 − 1⎞⎟⎜
⎜ 1 0 1 − 1⎟1]=⎜
Μ [order1 − 1 0 − 1⎟⎟⎜
⎜1 1 1 0 ⎟⎠⎝(d)は鶴の展開図の半分⎛ 0 − 1 − 1 − 1⎞⎟⎜⎜ 1 0 − 1 − 1⎟[ 2]
Μ order = ⎜1 1 0 − 1⎟⎟⎜⎜1 1 1 0 ⎟⎠⎝(a)424(b)

8(c)(d)Μ[ 3]order⎛ 0 − 1 − 1 − 1⎞⎜⎟
⎜ 1 0 − 1 − 1⎟=⎜
1 1 0 1⎟⎜⎟
⎜1 1 −1 0 ⎟⎝⎠それぞれの行列に対し、Mmask との演× を施すと、次のようにすべてが同じも算○のになります。

回提案した手法でも、調べるべき場合の数が爆発的に増えてしまい、丸 3 日間コンピュータに計算させ続けました#Ans'timeが、残念ながら調べきれませんでした。

110.22

ここからは、私の手による実験結果で4.0x104

330.31

すが、図 10 の丸で囲った領域を尾186.4x1015

2778

91.0（脚？）の部分に差し込むことができ

26

4.0x1026

5.0x1051110

ることがわかりました。図の手前側とNN!

#Ans

表 1. 図 8 の例題に適用した結果奥側でそれぞれ 2 通りの差し込み方が表中の N は面の数、#Ans は手順(3)あるので、通常の鶴とあわせて 5 通りで得られた解の数、#Ans’は手順(4)での形態数があることがわかります。と最終的に得られた形態数、time は計算

ころが尾の立ち上がり方が急な図 10に要した時間（秒単位）です。の右側の例の場合、このような差し込単純な例題である図 7(b)については、みができないので、形態数はただ 1 つ

一見すると中割り折りであると判断でと言うことができそうです。尾の角度きますが、他に 2 通りの折り方があるによって、得られる形態数が異なる、という興味深い結論が得られました。

是非、実際に折って試してみてください。

図 10. (a), (b)鶴の展開図から得られる異なる形態 (c) 形態数が 1 になる場合

鶴の展開図の形態数については、最終的に人の手によって得られたものですが、実このような解は、プログラムをデバッグしているときに発見したものなので、コンピュータを用いることが役立ったとも言うことができます。
今後は、今回紹介したアルゴリズムを改良し、面の数が多い複雑な展開図
でも、実用的な時間で答えを求められるようにしたいと考えています。