パズルの国のアリス

騎士同士のナイトツアー対決(解答)

 前回の表題は「騎士同士のナイトツアー対決」だった。ナイトツアーという言葉が聞きなれないという読者がおられるかもしれないので,その簡単な説明から始めよう。

 チェスのナイトは,将棋の桂馬の動きを四方八方にできる駒で,途中に邪魔な駒があってもそれを飛び越して進めるという特徴がある。ただ,あるマス目から別のマス目に行こうとすると,そのルートが簡単にはわりにくい面がある。そこで,その難しさを生かした問題として8×8のチェス盤上の全マスを1回ずつ訪問するような経路を問うというパズルがある。これがナイトツアーという問題で,グラフ理論でいうハミルトン路問題の一種である。

 一般のグラフの場合はNP完全という大変な難問のクラスに属するが,ナイトツアーという特殊形に限っては,すでに多くの研究がなされ,元の8×8はもちろん,色々なサイズや形の盤の上で,問題が解かれている。先月号の問題は,全マス目を1回ずつ訪問しろというようなものではないが,かなり深い関わりがあるので,表題に使わせていただいた。

 さて,動きの多いナイトのような駒で最初から考えるのは,厄介なような気もする。まず将棋の桂馬と香車から始めることにしよう。これらの駒はバックや横への動きが不可能だ。だから,盤面にかかわらず先手必勝であることがすぐにわかる。先手はこれらの駒を行き場所のない先頭の段に置けばよい(通常の将棋のルールでは,これらの駒がこの位置に来たとき,そのままでいることは許されず,必ず「成ら」なければならないが,ここではとりあえずそのルールは採用しないでおく)。

 それ以外の駒の場合を考えよう。どの駒もバックや横への動きが可能だから,初めから行き場所のないところに置くという先手の戦略は無効だ。

 まず,ルーク(将棋の飛車),クイーン,キング(将棋の王将),金将の場合だが,これらの場合はいずれも,8×8の盤面では後手必勝,9×9の盤面では先手必勝になる。駒の動きが違うので,同じ結果になるのは不思議な気がするかもしれない。ポイントは,どの駒も左右前後の隣のマス目への移動が可能なことにある。例えば8×8の盤面での後手の戦略だが,次の図のように盤全体をドミノで敷き詰めて考えるとわかりやすい。

 後手の戦略は,先手がどういう手を指そうが,自分の手番では駒を今いるドミノ内で(つまり点線を挟む隣のマス目に)移動するということである。後手がこの動きを続けている限り,(すでに訪問したマス目を再訪できないということから)初手も含めて先手が自分の手番で駒を置くのは,常に新しいドミノのどれかを選んでその一方のマス目ということになる。後手は,同じドミノのもう一方のマス目に駒を移動させることになるから,決して手詰まりになることがない。従って,先に手詰まりになるのは先手ということになる。この戦略は,一般にm×nの盤面においてもmnが偶数であれば有効だから,そのような盤面も後手必勝である。一方mnがともに奇数の場合,右下のマスを除いて盤面全体をドミノで敷き詰めることができる。例えば5×5の場合,下図のようだ。

 従って,先手は,最初に右下のマス目に駒を置き,あとは常にドミノ内でのみ駒を動かすようにしていれば,自然に勝つことができる。ドミノ戦略が使えるのは左右前後に動ける駒の場合だけだが,類似の戦略は他の駒にも有効だ。例えばチェス盤の場合,ビショップや銀将なら下の図の左ように,ナイトなら右のように,マス目を2つずつ対にして考える。

 同じ文字が書いてあるマス同士が対である。左の図ではビショップや銀将が,右の図ではナイトが,対の一方のマス目から他方のマス目へいつも移動可能なことがみそだ。つまり,後手は,先手の動きの結果駒がどの位置に来ようと,次の自分の手ではこの対同士の間で駒を移動するという戦略を取ることで簡単に勝つことができる。

 mnがともに偶数でどちらかが4以上であれば,m×nの盤面では,駒がビショップ,ナイト,銀将のいずれであっても,この戦略を一般化することで後手が勝てることは自明だろう。ビショップやナイトの場合なら,mnの一方が奇数で他方が偶数の場合も,盤面が十分広ければ,それを同様な対に分割することができるので後手勝ちである。5×4の盤面のそのような分割の1つを下に示そう。左がナイトの場合で右がビショップの場合だ。駒がビショップの場合,eマスやjマスのように斜めにすぐ隣り合っていなくても対を作れることが重要で,銀将の場合はこうはうまくいかない。

 一方,mnがともに奇数の場合,盤面が十分広いと,それを対に分割して,最後に1マスだけを残すことができるので,先手は最初のそのマスに駒を配置し,後は対の一方から他方への移動を繰り返すという戦略が取れる。よって先手勝ちである。ビショップとナイトの場合に5×5の盤面のそのような分割を示そう。これも左がナイトの場合で右がビショップの場合だ。

 上の図に従えば,先手は最初に駒を中央の空白のマスに置き,後は同じ文字が書かれているマス間で駒を動かしていれば勝つことができる。駒が銀将でnmが奇数のときは,盤面を上のような対に分割することが簡単ではないから,どちらが必勝かの判定は容易でない。

 最後に,駒が香車や桂馬で,ある領域に入ったら「成る」ことが許される(あるいは「成ら」なければならない)場合も,盤面全体のマス数が偶数なら後手必勝,奇数なら先手必勝になることが多いようだ。その場合の必勝側の戦略のコツは,なるべく早い機会に「成って」,その後は盤面のまだ訪問していないマス目全体をドミノに分割して考えることだ。

問題はこちらです