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

インスタント・インサニティ（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とする。
次に、それぞれのキューブを表すグラフを作る。それぞれのグラフは、4つの点で構成され、4つの点にはそれぞれ「赤」「緑」「青」「黄」のラベルがふられる。つまり、1つの点が1つの色に対応する（どの点にどの色のラベルを振っても構わない）。白黒のグラフを使った場合は、各点の隣に「赤」「緑」「青」「黄」などの文字を書くことになるが、Wikipediaはフルカラーが使えるので、単に4つの点をそれぞれ「赤」「緑」「青」「黄」の色で塗ることにする。
それぞれのキューブを表すグラフが持つ辺には、そのグラフを表すキューブのキューブ番号が割り振られることになる。白黒のグラフを使った場合は、各グラフの辺の隣にそのグラフのキューブ番号を書くことになるが、Wikipediaはフルカラーが使えるので、見てわかりやすいように、キューブ1を表すグラフの辺は「黒」、キューブ2は「水色」、キューブ3は「柿色」、キューブ4は「紫色」で描くことにする。もし、「柿色」の辺が「赤」と「緑」の2つの点を接続していた場合、互いに向かい合った「赤」と「緑」の面が「キューブ3」に存在するということを意味する。
最後に、4つのグラフを足す。出来上がったグラフは図2の通りで、4つのキューブにおける向かい合った面同士の色の配置の状況を、1つのグラフで示すことに成功している。
その2、2つの有向部分グラフの制作.
縦一列に積み上げられた4つのキューブにおいて、正面・背面・左側面・右側面の各方向の面における4つの色の配置をはっきりと示すようなグラフを作ってみよう。これは、2つの有向部分グラフを使えばいい。
4つのキューブを縦一列に積み上げる場合、各キューブの上になっている面と下になっている面の色はどうでもよくて、正面・背面・左側面・右側面の4方向の色だけが問題になる。つまり、この問題を解くには、キューブを縦一列に積み上げた時に、それぞれのキューブごとに、それぞれの色の面が、自分から見て正面・背面・左側面・右側面の4方向のどちら側に配置されていれば良いのかが把握できればいい。
4つのキューブにおける、全ての向かい合った2つの面の色の配置の情報を表すには、無向部分グラフではなく有向部分グラフが必要となる。なぜなら無向グラフを使った場合、各キューブにおいて「2つの面が向かい合っている」という情報しか示すことができず、その面が正面にあるのか背面にあるのか分からないためである。
1つの有向グラフで、キューブの正面と背面の情報を同時に表すことができ、もう一つの有向グラフで、キューブの左側面と右側面の情報を同時に表すことができる。したがって、2つの有向サブグラフを使えば、各キューブにおいて4方面に配置されるべき面の色の情報、すなわちパズルを解くのに必要となる全ての情報を表すことができる。
ただし、図2のグラフから、2つの色を結んだ辺（部分グラフ）を適当に選んで、新たに作る2つの有向グラフのそれぞれに割り振るようなことはしてはいけない。次のような基準で、割り振る対象の有向グラフを選択する必要がある。
上記のルールに従って、図2のグラフから辺（部分グラフ）を抜き出して新たな2つの有向グラフに割り振った結果、図3のような2つの有向グラフが導かれた。最初の有向グラフは、縦一列に積み上げた4つのキューブにおける、「正面・背面」の2方面の色の情報を同時に示したものである。2番目の有向グラフは、縦一列に積み上げた4つのキューブにおける、「左側面・右側面」の2方面の色の情報を同時に示したものである。
その3、グラフから解を導く.
最初の部分グラフから、対応するキューブの正面と背面の色が導かれる。例えば：
2番目の部分グラフから、対応するキューブの左右の面の色が導かれる。例えば：
3番目の画像は、問題の解であるキューブの積まれ方を示している。このように、グラフ理論を用いることで、簡単にインスタント・インサニティを解くことができた。
一般化.
n個の立方体が存在し、各立方体の面がn色のいずれかで着色され、各色が4つの向きのそれぞれに1回だけ現れるように立方体を積み重ねる問題の解法が存在するかどうかの判定は、NP完全の問題である
キューブスタッキングゲームは、このパズルの2人用ゲームバージョンである。キューブの番号付きリストが用意され、プレーヤーはキューブの上にキューブを段々と積み重ねていく。 4つの面のどれかに既に有る色のキューブを追加してしまったプレーヤーが負けである。RobertsonとMunroは、このゲームがPSPACE完全であることを証明した。これは、NP完全パズルがPSPACE完全ゲームにつながる傾向があることを示している。