インスタント・インサニティ

解決された状態のインスタント・インサニティ

インスタント・インサニティ（Instant Insanity）は、4つのキューブを使ったパズル。日本語へは急性精神病や即席狂気製造機と訳されている。

概要

4つあるキューブの各面は、4種類の色（上の画像の例では赤・青・緑・白）のどれかで塗られている。各キューブの色の塗られ方は、それぞれ別々になっている。パズルの目的は、4つのキューブを縦一列に積み重ね、正面・背面・左側面・右側面の4方向において、4種類の色が全て表示されるようにすることである。

この問題を解くにはグラフ理論に基づいたアルゴリズムを使うのが最も簡単である。それぞれの色を示すラベル（上の例においては「青」「緑」「赤」「白」）が付いた4つの点を持つグラフを使用して、それぞれのキューブを表現する。1つのキューブにおいて、2つの色の面が向かい合わせになっている場合は、2つの点の間に辺があると見なし、同じ色の面が向かい合わせになっている場合は、グラフの1点にループがあるとみなす。

グラフ理論を用いずに、別の何らかのアルゴリズムを使って解くこともできる。しかし、4つのキューブの積み方は全部で33万1776通りもあるため（1つのキューブは6つの面を持ち、キューブのそれぞれの面を表示させた場合において4つの回転の向きを取りうるので、1つのキューブにおいて6*4=24通りの積み方がある。さらに、全部で4つのキューブがあるので、24*24*24*24 = 331,776通り）、この問題の解決に力まかせ探索法を用いた場合は非常に時間がかかる。

このパズルにおいて、4色の色の順番はどうでも構わないため、正解となるキューブの積み方は4!=24通りあることになる。 したがって、乱択法を用いた場合、1万3824分の1（331776/24=13824）に等しい確率で解が導出される計算になる。ドナルド・クヌースは、バックトラック法を使用した網羅的な検索手順の実行時間の推定に関する記事においてこのパズルを研究している。

インスタント・インサニティは、キューブがどのような初期配置であったとしても、8手以内で解決できることが分かっている。

このパズルは、アメリカではフランツ・オーウェン・アームブラスター（フランク・アームブラスターの名でも知られる）によって再設計され、「インスタント・インサニティ」の名称で1967年にパーカー・ブラザーズから発売された。1200万個以上売り上げたという。しかしこの形式のパズルは実際は古くからある物であり、その中にはフレデリック・A・ショッソウが1900年に特許を取得した「カッツェンジャマー（Katzenjammer）」パズル、あるいは「グレートタンタライザー（The Great Tantalizer）」パズル（1940年頃、インスタント・インサニティ以前に最もポピュラーだった名前）なども含まれる。

このパズルの日本版はハナヤマや増田屋コーポレーションによって販売されていた。

グラフ理論を用いた解法

その1、向かい合った面の色の配置を示すグラフの制作

キューブにすでに色が塗られており、4種類の色が「赤・緑・青・黄」であると考えて、4つ全てのキューブにおける、向かい合った面同士の色の配置を、1つのグラフではっきりと示すようなグラフを作ってみよう。

まず、各キューブに1から4までのキューブ番号を割り当て、それぞれキューブ1、キューブ2、キューブ3、キューブ4とする。

図1：4つのキューブにキューブ番号を割り振る。それぞれのキューブの各面の色は上の通り。

次に、それぞれのキューブを表すグラフを作る。それぞれのグラフは、4つの点で構成され、4つの点にはそれぞれ「赤」「緑」「青」「黄」のラベルがふられる。つまり、1つの点が1つの色に対応する（どの点にどの色のラベルを振っても構わない）。白黒のグラフを使った場合は、各点の隣に「赤」「緑」「青」「黄」などの文字を書くことになるが、Wikipediaはフルカラーが使えるので、単に4つの点をそれぞれ「赤」「緑」「青」「黄」の色で塗ることにする。

それぞれのキューブを表すグラフが持つ辺には、そのグラフを表すキューブのキューブ番号が割り振られることになる。白黒のグラフを使った場合は、各グラフの辺の隣にそのグラフのキューブ番号を書くことになるが、Wikipediaはフルカラーが使えるので、見てわかりやすいように、キューブ1を表すグラフの辺は「黒」、キューブ2は「水色」、キューブ3は「柿色」、キューブ4は「紫色」で描くことにする。もし、「柿色」の辺が「赤」と「緑」の2つの点を接続していた場合、互いに向かい合った「赤」と「緑」の面が「キューブ3」に存在するということを意味する。

最後に、4つのグラフを足す。出来上がったグラフは図2の通りで、4つのキューブにおける向かい合った面同士の色の配置の状況を、1つのグラフで示すことに成功している。

図2：4つのキューブの向かい合った面の配置の状況を示すグラフ。キューブ1の辺は「黒」、キューブ2は「水色」、キューブ3は「柿色」、キューブ4は「紫色」で塗られている。

その2、2つの有向部分グラフの制作

縦一列に積み上げられた4つのキューブにおいて、正面・背面・左側面・右側面の各方向の面における4つの色の配置をはっきりと示すようなグラフを作ってみよう。これは、2つの有向部分グラフを使えばいい。

4つのキューブを縦一列に積み上げる場合、各キューブの上になっている面と下になっている面の色はどうでもよくて、正面・背面・左側面・右側面の4方向の色だけが問題になる。つまり、この問題を解くには、キューブを縦一列に積み上げた時に、それぞれのキューブごとに、それぞれの色の面が、自分から見て正面・背面・左側面・右側面の4方向のどちら側に配置されていれば良いのかが把握できればいい。

4つのキューブにおける、全ての向かい合った2つの面の色の配置の情報を表すには、無向部分グラフではなく有向部分グラフが必要となる。なぜなら無向グラフを使った場合、各キューブにおいて「2つの面が向かい合っている」という情報しか示すことができず、その面が正面にあるのか背面にあるのか分からないためである。

1つの有向グラフで、キューブの正面と背面の情報を同時に表すことができ、もう一つの有向グラフで、キューブの左側面と右側面の情報を同時に表すことができる。したがって、2つの有向サブグラフを使えば、各キューブにおいて4方面に配置されるべき面の色の情報、すなわちパズルを解くのに必要となる全ての情報を表すことができる。

ただし、図2のグラフから、2つの色を結んだ辺（部分グラフ）を適当に選んで、新たに作る2つの有向グラフのそれぞれに割り振るようなことはしてはいけない。次のような基準で、割り振る対象の有向グラフを選択する必要がある。

1. 2つの有向グラフにおいては、互いに共通の辺（同じ2色を結ぶ、同じ色の辺）が存在してはいけないものとする。「共通の辺が存在する」と言うのは、少なくとも1つのキューブがまったく同じ色で構成された向かい合わせの面のペアを持っていることを意味する。例えば、キューブの正面・背面のペアと、左側面・右側面のペアがどちらも赤と青で構成されている、と言うような状況だが、こんなことはあってはいけない。
2. 2つの有向グラフのそれぞれにおいては、図2のグラフの辺のうち、各キューブごとに1つの辺しか引用できないものとする。なぜなら、新たに作る2つの有向グラフのそれぞれの辺は、4つの全てのキューブから引用される必要があるからだ。そもそも、グラフの1つの辺だけで、向かい合わせになった2つの面の情報を完全に示すことができるので、各キューブから引用する辺は1つだけで構わない。
3. 2つの有向グラフにおいては、全ての点は、次数が「2」（つまり、2本の辺が接続されている）でないといけないものとする。これは、次数が2の場合、その点の色は2枚の面にしか現れることがない、ということを意味するからだ。正面4枚と背面4枚（もしくは左側面4枚と右側面4枚）、合計8枚の面の集合において、4種類の色があり、各色ごとに2枚の面がある、と考えれば理解しやすいだろう。

上記のルールに従って、図2のグラフから辺（部分グラフ）を抜き出して新たな2つの有向グラフに割り振った結果、図3のような2つの有向グラフが導かれた。最初の有向グラフは、縦一列に積み上げた4つのキューブにおける、「正面・背面」の2方面の色の情報を同時に示したものである。2番目の有向グラフは、縦一列に積み上げた4つのキューブにおける、「左側面・右側面」の2方面の色の情報を同時に示したものである。

図3：縦一列に積み上げた4つのキューブにおける、「正面・背面」の色の情報を示す有向グラフと、「左側面・右側面」の色の情報を示す有向グラフ

その3、グラフから解を導く

最初の部分グラフから、対応するキューブの正面と背面の色が導かれる。例えば：

1. 黄色から青色への黒い矢印は、キューブ1の正面が黄色、背面が青色であることを示している。
2. 緑から黄色への青い矢印は、キューブ2の正面が緑、背面が黄色であることを示している。
3. 青から赤へのオレンジ色の矢印は、キューブ3の正面が青、背面が赤であることを示している。
4. 赤から緑への紫色の矢印は、キューブ4の正面が赤、背面が緑であることを示している。

2番目の部分グラフから、対応するキューブの左右の面の色が導かれる。例えば：

1. 赤から緑への黒い矢印は、キューブ1の左側面が赤、右側面が緑であることを示している。
2. 青から赤への青い矢印は、キューブ2の左側面が青、右側面が赤であることを示している。
3. 黄色から青へのオレンジ色の矢印は、キューブ3の左側面が黄色、右側面が青であることを示している。
4. 緑から黄色への紫色の矢印は、キューブ4の左側面が緑、右側面が黄色であることを示している。

3番目の画像は、問題の解であるキューブの積まれ方を示している。このように、グラフ理論を用いることで、簡単にインスタント・インサニティを解くことができた。

問題を解く際に注意すべきポイント

1. 各キューブは、「キューブ1」から「キューブ4」までのどのラベル（キューブ番号）を付けても構わない。というのも、1つの解が導き出せた場合、各キューブにおける各面の色の配置を変えなくても、キューブの積む位置を入れ替えるだけで、さらに追加で23通り（合計24通り）の解を導き出すことができるからで、要するに、縦一列に積み上げた各キューブの積む順番は問題にならないという意味だ。
2. 2つの有向部分グラフにおいて、「正面から背面へ」を表す有向部分グラフは、「背面から正面へ」を表すのだと考えることもできる。同時に、「左側面から右側面へ」を表す有向部分グラフは、「右側面から左側面へ」を表すのだと考えることもできる。言い換えるなら、「背面から正面へ」と「左側面から右側面へ」は相互に交換することができる。要するに、1つの解が導き出せた場合、各キューブの順番を入れ替えずに、縦一列に積み上げたキューブを回転させるだけで、さらに追加で3通り（合計4通り）の表し方が可能ということになる。そして、上記の「ポイント1」と、この「ポイント2」を組み合わせると、1つの解が導き出せた場合、さらに追加で95通り（24*4=96で、合計96通り）の解を導き出せるということになる。
3. 縦一列に積み上げられた、各キューブの上の面と下の面（底面）のことは、この問題においては重要ではないので気にする必要はない。

一般化

n個の立方体が存在し、各立方体の面がn色のいずれかで着色され、各色が4つの向きのそれぞれに1回だけ現れるように立方体を積み重ねる問題の解法が存在するかどうかの判定は、NP完全の問題である 。

キューブスタッキングゲームは、このパズルの2人用ゲームバージョンである。キューブの番号付きリストが用意され、プレーヤーはキューブの上にキューブを段々と積み重ねていく。 4つの面のどれかに既に有る色のキューブを追加してしまったプレーヤーが負けである。RobertsonとMunroは、このゲームがPSPACE完全であることを証明した。これは、NP完全パズルがPSPACE完全ゲームにつながる傾向があることを示している。

参照

• Slocum; Botermans (1987), Puzzles Old and New, Seattle: University of Washington Press, p. 38, ISBN 0-295-96579-7