チェス盤の上の数学

チェスの盤は、8×8の64マスの小さな世界です。でも、そこにクイーンを置いたり、ナイトを歩かせたりすると、数学者を何百年も悩ませた問題が出てきます。

エイトクイーン（このサイトの「エイトクイーン」）

クイーンは、縦・横・ななめに何マスでも進めます。そのクイーンを8つ、おたがいに取り合わないように8×8の盤へ置けるでしょうか。 答えは92通りです。回転したり裏返したりして重なるものを同じと数えると12通りになります。 どちらも、このサイトのプログラムで盤を全部調べて確かめました。

盤の大きさを変えて数えると、解の数は不規則に増えます。このサイトのプログラムで確かめた数は、次のとおりです。

盤の一辺	解の数
4	2
5	10
6	4
7	40
8	92
9	352
10	724

6のとき解は4通りしかなく、5より少なくなっています。大きくなるほど増える、という単純なものではありません。

出題と、ガウスの話

この問題は、1848年にベルリンのチェス雑誌で、マックス・ベッツェルが出題したとされています。 1850年には、フランツ・ナウクが92通りの解を示し、問題を「n個のクイーン」へ広げました。ただしナウクは、それで全部だという証明まではつけていません。

数学者のガウスもこの問題に取り組んでいます。友人への手紙で論じたのですが、ガウスが問題を出したわけでも、完全に解いたわけでもありません。 この点は教科書でも何度も間違って書かれ、1977年にキャンベルという研究者がその誤りを整理しました。「有名な人が解いた」という話は、歴史の中でよく間違って広まる、よい例です。

1972年ごろには、ダイクストラが、この問題を使って「行き止まりまで試して、だめなら戻る」というやり方（後戻り）をていねいに説明したとされています。 いまもプログラミングの定番の練習問題です。

ナイトの巡回（このサイトの「ナイトの巡回」）

ナイトは「L字」に跳ぶ駒です。同じマスを2度通らずに、全部のマスを1回ずつ回る道を「ナイトの巡回」と呼びます。 このサイトのプログラムは、5×5、6×6、8×8の盤で、隅から出発して全マスを回る道を作れることを確かめています。

古くからある遊び

ナイトの巡回の記録は古く、9世紀ごろのアラビアのチェス（シャトランジ）の名手の巡回が、14世紀の写本に残っているとされています。 インドでは、9世紀の詩人ルドラタが、盤の半分の巡回を詩の形式として織り込んだ、とも言われています。巡回が詩の中に隠れていたのです。 「だれが最初か」は言い切れないので、記録に残る古い例の一つ、という言い方になります。

オイラーは、1759年にベルリンの学士院でこの問題を詳しく論じ、1766年に出版したとされています。数学として本格的に調べた人ですが、発見した人ではありません。

ウォンスドルフの規則

「次に行ける先の数がいちばん少ないマスへ進む」という経験則が、1823年に記されたとされています（ウォンスドルフの規則）。 上手に巡回ができることが多いのですが、いつでもうまくいくわけではありません。大きな盤では失敗することもあります。 証明された手順ではなく、経験にもとづくコツです。盤に出る補助の数字は、この規則を使うための手がかりになります。

13兆通りの数え方

8×8の盤で、最後のマスから最初のマスへ1手で戻れる「閉じた巡回」は、向きを区別しないで数えると13,267,364,410,532通り、つまり13兆あまりです。 向き（時計回りか逆回りか）も区別すると、その2倍の26,534,728,821,064通りになるとされています。 最初に発表された数は間違っていて、1997年にブレンダン・マッケイが正しい値を出しました。

数え方で数が変わるので、巡回の数を言うときは条件がかかせません。「閉じた巡回だけか」「向きを区別するか」で答えが変わります。 なお、閉じた巡回は、縦も横も奇数のマスの盤には存在しません。

魔方陣になる巡回はあるか

巡回の順番を、各マスの数字にしてみましょう。行や列の和がそろうものは見つかっていますが、対角線までそろった魔方陣になる巡回は、8×8の盤には存在しません。 2003年に、コンピューターによる全部の探索が終わって確かめられました。もっと大きな盤では、完全な魔方陣になる巡回が存在するとされています。 1848年に作られた巡回は、行と列の和がそろう「半魔方陣」だったとされています。

考え方

• エイトクイーン：1行に1つずつ置く、と考えると、探す範囲がぐっと減ります。置けないマスが出たら、ひとつ戻ってやり直します。
• ナイトの巡回：行き止まりになりやすい隅や端のマスを、早めに通っておくと、あとが楽になります。
• どちらも：「何通りあるか」を数えるときは、数える条件を先にはっきりさせます。

エイトクイーンでは、8×8で回転・裏返しをまとめた12種類の解を集められます。ナイトの巡回では、盤に出る補助の数字（移動先からさらに進める未訪問マスの数）を手がかりにしてみてください。