ほどいてください - LazyLife@Diary

pya!経由でこういうflashゲームがあることを知った。
http://www.planarity.net/
※なぜか手元のOpera8ではいつまで経っても表示されないので、そういう人はpya!の方で

要するに、青い玉を適宜移動させて玉の間に引かれた線が交差することがないようにせよ、というもの。
親切なことに、玉をクリックするとそれと線で結ばれている玉が赤く表示される。

レベル3からやたらと玉(と線)の数が激増するのでこりゃ高レベルのやつは手に負えない・・・・・・と思ったら、必勝法があるらしくレベル30やら40でも人力で解いた人がいるようだ。
そこで、その必勝法を自力であみ出してみた。

以下ネタバレにつき見たい人のみどうぞ。

※以下の記述は厳密性を求めたものではないので了承ください。

暗黙の前提として、玉と線によって図示されたグラフが平面グラフ(平面上に、辺を交差することなく描けるグラフ)に同型であることを仮定する。
これが真でないと話にならない。

まず(玉が移動できる)画面の領域を3つに分ける。それぞれ領域1、2、3として、
1.完全に整理されたグラフの領域
2.完全ではないがある程度整理されたグラフの領域
3.整理されていないグラフの領域
を意味する。
また、以下では玉→頂点、線→辺、線で結ばれた→隣接した　のように表現する。

１．円形に並んだ頂点を全て領域3に移動する。その作業の間に、お互いが隣接した3つの頂点の組を見つけたらその組を一つ領域1に移動させる。

２．領域1にある頂点に隣接する頂点を領域2に移動する。このとき、適度に見やすいような位置に置いておくとよい。
領域1と2にある頂点とそれらを結ぶ辺のみで、領域1に含まれる頂点同士を結ぶ辺を少なくとも1つ含む閉路が作れるならば、その閉路に含まれる領域2に属する頂点を領域1に移動する。
このとき、領域1に含まれる頂点とそれら同士を結ぶ辺で構成されるグラフの辺が交差しないように配置する。領域1の頂点とその他の領域の頂点を結ぶ辺は無視する。
(この時、領域1に属する頂点を移動しなければならないことがたまにあるが、そう難しくはない)

３．手順2で閉路が見つからなかった場合、領域2に属する頂点に隣接する領域3の頂点をいくつか領域2に移動させる。手順2に戻る。

手順2を繰り返した状態。

終了。

これを繰り返すだけで十分時間をかければどんな問題でも解けるはず。
とりあえずレベル12まで解いたところで「スクリプトが長時間応答しないよ」とのエラーダイアログが出たので終了。