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

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


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

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

■ ソルバー開発の方針

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

■ 本線について

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

■ 穴埋めについて

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

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

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

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

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

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

■ 解の表示形式

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

※※※※※※※※※※※※※※※
※※※※※┌────┐※※※※
※※※┌─┘※※A※│※※※※
※┌─┘※口口A┌─┘※※※※
※│※@口口※※│※※┌─┐※
※└─┐※※┌─田田─┘※│※
※※※│※※│※※│※┌─┘※
※※※E※※│※※│※│※※※
※※※@S─┘※※└─┘※※※
※※※※※※※※※※※※※※※

■ 本線の終着点

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

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

※※※※※※※※※※※※※※※
※※※※※※┌─┐※※※※※※
※※※※※┌┘※└┐※※※※※
※※※※┌┘※※※└┐※※※※
※┌──┘※※※※※└──┐※
※│※※A※※※※※@※※│※
※└──┐※※※※※┌──┘※
※※※※└E※※※┌┘※※※※
※※※※※A@S─┘※※※※※
※※※※※※※※※※※※※※※

■ 本線探索の枝刈り

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

■ プログラミング

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

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

■ 実行結果

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

プログラム名実行結果 備 考
buzzstylebuzz.txtとにかく解ければよい
RingMyBellring.txt制限歩数の更新を試みる
  CPU = AMD Athlon 1.0GHz
  メモリ = 128MB (PC133,CL=3)
  O S = Windows Me (DOS窓)
  コンパイラ=Visual C++ 5.0 (実行速度で最適化)

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

■ おわりに

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

■ 追記(2002/04/26)

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

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

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


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


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