インスタント・インサニティ
キューブにすでに色が塗られており、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つのグラフで示すことに成功している。
「共通の辺が存在する」と言うのは、少なくとも1つのキューブがまったく同じ色で構成された向かい合わせの面のペアを持っていることを意味する。例えば、キューブの正面・背面のペアと、左側面・右側面のペアがどちらも赤と青で構成されている、と言うような状況だが、こんなことはあってはいけない。
2つの有向グラフのそれぞれにおいては、図2のグラフの辺のうち、各キューブごとに1つの辺しか引用できないものとする。なぜなら、新たに作る2つの有向グラフのそれぞれの辺は、4つの全てのキューブから引用される必要があるからだ。そもそも、グラフの1つの辺だけで、向かい合わせになった2つの面の情報を完全に示すことができるので、各キューブから引用する辺は1つだけで構わない。
2つの有向グラフにおいては、全ての点は、次数が「2」(つまり、2本の辺が接続されている)でないといけないものとする。これは、次数が2の場合、その点の色は2枚の面にしか現れることがない、ということを意味するからだ。正面4枚と背面4枚(もしくは左側面4枚と右側面4枚)、合計8枚の面の集合において、4種類の色があり、各色ごとに2枚の面がある、と考えれば理解しやすいだろう。
上記のルールに従って、図2のグラフから辺(部分グラフ)を抜き出して新たな2つの有向グラフに割り振った結果、図3のような2つの有向グラフが導かれた。最初の有向グラフは、縦一列に積み上げた4つのキューブにおける、「正面・背面」の2方面の色の情報を同時に示したものである。2番目の有向グラフは、縦一列に積み上げた4つのキューブにおける、「左側面・右側面」の2方面の色の情報を同時に示したものである。
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通り)、この問題の解決に力まかせ探索法を用いた場合は非常に時間がかかる。