ホームページへ戻る　開発ノートメニューへ戻る

恐怖の1000面パズル「XOR」を解く


　岸和田高校物理部プロジェクトチームが、ASCII誌(1987年7月号)上に発表したという恐怖の1000面パズルゲーム「XOR」のソルバープログラムを作ってみました。現在、このゲームは開発チームのひとりである安岡孝一さんのホームページにおいて、JavaScript版のXORが公開されており、ネット上から直接遊ぶことが可能です。このゲームがどのようなものなのか、是非２・３面解いてみてからこのページを読まれることをお勧めします。
■　ルールの補足説明

　ネット検索で調べてみると「XOR」というこのゲームは「エクサー」と呼ぶらしいです。
　ルールの説明がちょっと不充分で「画面上のΩの周りをクリックしてΩを上下左右に動かし、道を制限歩数以内で塗りつぶして下さい。」としか書かれてなくて最初は戸惑いましたが、XORがエクスクルーシブ・オア、つまり「排他的論理和」を意味していると理解すると、このゲームのルールがよく見えてきます。
　「空きマスに進入するとその地点が塗りつぶされ、塗りつぶされた地点に進入すると空きマスに戻ってしまう、という法則の元に総てのマスを塗りつぶして下さい。」ということになります。しかし、一見して一筆書きのようなゲームですが「排他的論理和」のルールが加わっただけで難易度は一気に高くなります。第１面から既に難しいと感じた人も多いと思います。

■　ソルバー開発の方針

　ソルバープログラムを作ろうと思えば、最初に思い付くのは幅優先探索か反復深化を使い最適解(最短歩数解)を求めたいと考えるのが一般的でしよう。しかし実際にやってみるとこのゲームの探索空間は想像以上に大きなものでした。
　幅優先探索では直ぐにメモリーがパンクし、反復深化では何時間待っても答えが返ってきません。やり方が悪かったのではと言われるとそれまでですが、私は最適解を得ることを断念し、ヒューリスティックスな手法を用いることにしました。
　何題か自力で解いてみるとこのゲームは、「本線(最も重要なルート)を見つける問題」と「本線が取りこぼした空きマスの穴埋め問題」に分割して考えることが出来る事に気付きます。

■　本線について

　本線とは、一筆書きのルールに近く私は本線というものをこのように定義しました。
本線は進行方向を１８０度転換する動きはしない。ただし、本線が交差することは有り得る。
　言い換えると、本線とは今来た道を引き帰すことなく交差点をどのように渡り歩くかということになります。３差路に来れば次ぎの選択肢は２つ、４差路に来れば選択肢は３つ、それ以外は選択の余地がないということになり、探索空間は随分と狭められることになります。

■　穴埋めについて

　次に本線が取りこぼした空きマスの穴埋めですが、ひと繋がりの空きマスを「島」と呼ぶことにし、島の穴埋めを行う方法は大きく分けて２つの技法があるように思います。
方法１「２つの島の間を往復してそれぞれの島の１マスずつを塗りつぶす。」

方法２「マスの数が偶数個の島ならその島単独で塗りつぶすことが出来る。」

　マスの数が奇数個の島には必ず最低１回(奇数回)は方法１を使う必要があります。マスの数が偶数個の島なら方法２だけを使うか、方法１を偶数回使うことを併用することになります。

■　穴埋めの消費ステップ数

　方法１は２つの島の間を往復するのですから「２つの島の距離×２」ステップ消費することは明らかです。
　しかし、方法２は少し複雑で２マスを埋めるのに消費するステップ数は２か４か６の場合があります。
　空きマスには「一度も本線が通過していない空きマス」と「本線が偶数回通過して空きマスになった」ものがあります。２マス連続した空きマスを埋める場合、本線が一度も通過していないなら６ステップ必要ですが、２マスの内どちらかでも本線が通過したことのある場合は２ステップの消費で済みます。
　そしてこの方法で連続した２マスを埋めていくと、島の形状に交差点を含む場合は島が分断されることがあり、その場合は方法１に習って２マス埋めるのに４ステップ消費する場合も生じます。

※※※※※※※※※※※※
※※※※※※※※※※※※
※※※※口※※口※※※※
※●●●●●●●●●●※
※※※※※※※※※※※※
方法1: 5(距離)×2＝10step
「２つの島の距離×２」 
※※※※※※※※※※※※
※※※※※口※※※※※※
※※※※※口※※※※※※
※●●●●●●●●●●※
※※※※※※※※※※※※
方法2: 6step (ただし、2つの空きマスの内
どちらかでも本線が通過したことがあれば2step) 
※※※※※※※※※※※※
※※※※口口口※※※※※
※※※※※口※※※※※※
※●●●●●●●●●●※
※※※※※※※※※※※※
方法2+1: 6＋4＝10step (方法2を適用すると
島が分断され、残りは方法1により4step消費)

■　解の表示形式

　本線探索と穴埋めを別に扱っている関係で解の表示は下図の例のようにしています。本線はＳからＥまで進み、穴埋めの方は数字を丸で囲んであるものが方法１によるもので、数字は「ペア関係を識別する番号」になっています。「口」は方法２によるものですが本線が通過したことのある空きマスは「田」と表しています。 

※※※※※※※※※※※※※※※
※※※※※┌────┐※※※※
※※※┌─┘※※A※│※※※※
※┌─┘※口口A┌─┘※※※※
※│※@口口※※│※※┌─┐※
※└─┐※※┌─田田─┘※│※
※※※│※※│※※│※┌─┘※
※※※Ｅ※※│※※│※│※※※
※※※@Ｓ─┘※※└─┘※※※
※※※※※※※※※※※※※※※

■　本線の終着点

　本線の終着点についてまだ触れていませんでしたが、これまでの話から本線の終着点と成り得るための条件が少し見えてきます。先ず、本線が最終的に取りこぼす空きマスの数は偶数でなければなりません。何故なら、穴埋めは常に２マス単位で行われるからです。
　次に終着点は塗りつぶされた状態であるべきです。それは、本線が通過したことのある連続した２つの空きマスは２ステップで埋めることが出来るので、終着点が塗りつぶされていない状態は、その２ステップ前の状態と同値と言えるので無駄なのです。(間違いではありませんが)

　ここから先の話は明確な理論というよりも、おそらくそんなもんだろうという話になるのですが、ドーナツ状のループした島がまだ残っている場合は本線を終了させるには早すぎます。２マス消すのに６ステップも消費するような穴埋めをするよりも、ドーナツ状の島は本線を通過させて埋めていった方がずっと得策だと思われるからです。
　同様の理由により、すぐ目の前に連続した未通過空きマスが２つ以上続いている場合も本線を終了させるには早すぎるだろう、、、と思ったのですが、それは早とちりでした。下のようなケース(第302面)があるので３つ以上続いている場合は本線を終了させるには早すぎると改めました。(←かなりいい加減)

※※※※※※※※※※※※※※※
※※※※※※┌─┐※※※※※※
※※※※※┌┘※└┐※※※※※
※※※※┌┘※※※└┐※※※※
※┌──┘※※※※※└──┐※
※│※※A※※※※※@※※│※
※└──┐※※※※※┌──┘※
※※※※└Ｅ※※※┌┘※※※※
※※※※※A@Ｓ─┘※※※※※
※※※※※※※※※※※※※※※

■　本線探索の枝刈り

　穴埋め時に２マスを２ステップで埋めることが可能な場合があるので、枝刈りとしては、
現在の消費ステップ数　＋　現在の空きマス数　＞　制限歩数
という式で枝刈りさせるしかありません。しかし、これだけでは物足りないので、方法２による穴埋めをそのまま流用した枝刈りを組み入れてみましたが、これは本線探索の枝刈りというよりも、本線の終着点と成り得るための条件に対する枝刈りというべきものかもしれません。

■　プログラミング

　本線探索には最良優先探索を使用しましたが、本線は交差しない方が評価が高いという程度のものです。
　それから、方法１による穴埋めはバックトラッキングを使い、方法２よる穴埋めは演繹的な方法(制約伝播)を使いました。
　XORの作者(特にランキング登録によるHPを開設している安岡さん)に迷惑がかかるので、私の書いたプログラムを公開することは出来ませんが、全1000面を解くことに成功しています。
　ヒューリスティックスな手法なので最適解の保証はありませんが、解けなくなるまで制限歩数を４ステップずつ小さくして探索を繰り返すと最適解に限りなく近い解を求めることも可能になります。(下の追記を参照)

　尚、このページでの説明は主要な部分だけを書きました。実際にはかなり細かい部分にまで様々なアイデアを投入しないと全問制覇は困難かと思われます。そういった部分に関してはここでは触れませんし質問されてもお答えできません。

■　実行結果

　私のソルバープログラムに「buzzstyle」という名前を付けて、問題面の収集とソルバープログラム開発を目的として全1000面を解かせてみた結果を下に置きました。
　それから、解けなくなるまで制限歩数を小さくして行く方法で解かせたソルバー「RingMyBell」を実行させた結果も置いておきます。★印のあるものは制限歩数を下回って解けてしまったもので、合計で63面の制限歩数を更新しましたが、制限歩数を更新すると安岡さんのHPでの制限歩数が自動で更新記録に書き換えられる仕組みになっているようです。従って、RingMyBellが通過してしまった今の状態からの制限歩数の更新は、かなり困難かも知れません。(不可能という意味ではありません)

プログラム名実行結果　備　考
buzzstylebuzz.txtとにかく解ければよい
RingMyBellring.txt制限歩数の更新を試みる
 　　ＣＰＵ ＝ ＡＭＤ　Athlon 1.0GHz
　　メモリ ＝ １２８ＭＢ　(PC133,CL=3)
　　Ｏ　Ｓ ＝ Windows Me　(DOS窓)
　　コンパイラ＝Visual C++ 5.0 (実行速度で最適化)

【実行結果表の見かた】
面番号：本線ステップ数＋穴埋めステップ数＝合計ステップ数　（制限歩数）／本線探索消費バケット数　穴埋め探索を試みた回数　実行時間(秒)
尚、合計ステップ数の後ろに「★」のあるものは制限歩数を更新したものです。

■　おわりに

　このページの公開にあたって、安岡孝一さんの承諾を頂くことが出来ました。心より感謝申し上げます。
　それにしても全1000問とは、まさに恐怖をいう形容詞が見事に当てはまります。面の作者が約２０名いたようですが、量だけの問題ではなく内容的にも関心させられる問題が多数あり、とても楽しませて頂きました。ありがとうございます。
　尚、今回の私のプログラムには理論的に曖昧な部分が幾つかあり、それが心残りです。機会があれば「完全最適解」を目指して再チャレンジしてみたいと思っています。

■　追記(2002/04/26)

　最適解に近い解を求める時、制限歩数を「４ステップずつ小さくしてよい」という報告が、としひでさんからありました。ありがとうございます。

−−−−【としひでさんの説明に加筆】−−−−

　盤面に白黒の市松模様を付けます。終着点が白マスだったとして、−１歩では白マスの偶奇性が反転します。かと言って−２歩で白マスの偶奇を元に戻すことは出来ません。何故なら移動経路は必ず「黒白黒白…」と交互に辿るので−２歩では黒マスの偶奇性を反転させる結果になってしまいます。従って、これらの偶奇を元に戻すにはさらに−２歩を必要とし、結局４ステップ単位でしか歩数を更新することは出来ない。


　ところがその後、安岡孝一さんを通して、本家のＸＯＲ開発チームがゲーム制作中の1985年頃に、この事は既に発見していて、より明快なその証明方法と、さらにもう１つの規則性があることを教えて頂きました。ここをご覧下さい。
ＸＯＲ開発チームによる「XORの法則」

ホームページへ戻る　開発ノートメニューへ戻る