エイト・クイーン(1848) — 八つの駒を、互いに利かせず置く。ガウスも数えた盤

はじめに — 縦横斜めに利く駒を、八つ並べる

これは1848年に、ドイツのチェス雑誌に載った問題である。8×8の盤に、クイーンを8個置く。どのクイーンも、ほかのクイーンに取られる位置に立ってはならない。道具は盤と駒だけ。規則は一行で言える。

クイーンは縦にも横にも斜めにも、盤の端まで動ける。一つ置くたびに、その行と列と二本の斜めが塞がる。置ける場所は、見る間に減っていく。それでも、八つ置き切る並べ方は存在する。全部で92通りある。

本稿では、1848年のマックス・ベッツェルから、1850年のナウクとガウス、1874年のグレイシャー、そして1971〜72年のダイクストラまでを辿る。現代では、2024年にLinkedInが公開したQueensにも、よく似た制約が見える。確かめられた範囲だけを、歴史家の目で書く。

八つのクイーンが互いに利かない並び（イメージ・AI生成）

その時代の文脈 — 雑誌の出題、手紙のやりとり、数え上げの競争

1848年、チェス問題の作者マックス・ベッツェルが、ベルリンのチェス雑誌に8クイーンの問題を発表した。ベッツェルは問題作者であり、数学者ではない。盤の上の遊びとして出された問いが、のちに数学の題材になった。

1850年には、フランツ・ナウクが92通りの解を示した。ただし、これで全部だという証明はつけていない。ナウクは、盤をn×nに広げ、クイーンをn個置く一般の問いにも進んだと伝えられる。

同じ1850年、数学者ガウスも、天文学者シューマッハーとの手紙のなかでこの問題を考えていた。ガウスは72通りを見つけた時点で、ナウクの92通りを知ったという。ここまでは、近年の概説論文が述べる経緯である。

全部で92通りという証明は、1874年のJ・W・L・グレイシャーが与えたとされる。同じ年には、S・ギュンターが行列式を使う方法を提案した。ただし、この問題の来歴は書き手によって違う。論文自身も、文献ごとに歴史が異なると断っている。

手紙と盤が並ぶ、十九世紀半ばの机（イメージ・AI生成）

メカニクス — 行ごとに一つ置くと、探す範囲が一気に縮む

置き方の数を数えてみる。64マスから8マスを選ぶ方法は、4,426,165,368通りある。全部を調べるのは、手では無理だ。

ここで気づくことがある。同じ行に二つ置けば、必ず利き合う。だから、各行にちょうど一つ置くことになる。あとは、行ごとに列を決めればよい。列も重ならないなら、並べ方は8の階乗、40,320通りに減る。さらに斜めを調べて、残るのが92通りである。

92通りは、盤を回したり裏返したりして重なるものをまとめると、12種類になる。11種類は8通りずつ、残る1種類は左右上下に対称で4通りだ。11×8+4で92になる。

ダイクストラは1971年8月の「A Short Introduction to the Art of Programming」(EWD316)の第9章で、この問題を扱った。各行の列の位置を配列に記録し、使える列と斜めを真偽値の配列で管理する。行き止まりに着いたら一つ戻って、別の列を試す。この「戻る」手順を、バックトラッキングと呼ぶ。

利き筋の盤と、行き止まりで戻る探索の木（イメージ・AI生成）

現代への系譜 — プログラムの教材から、計算の難しさの研究へ

英語版Wikipediaによれば、ダイクストラは1972年に、この問題で「構造化プログラミング」の力を示した。同年の共著『Structured Programming』(ダール、ダイクストラ、ホーア)が知られる。ダイクストラは1972年にチューリング賞も受けている。授賞理由は構造化プログラミングの提唱だった。

盤の大きさを広げる研究も続いた。27×27の盤までは、2016年までに全部の解が数え上げられている。一方で、解が存在すること自体はやさしい。2と3を除く全てのnで、置ける並べ方がある。

難しくなるのは、一部のクイーンを先に置いた場合だ。2017年、ジェント、ジェファーソン、ナイチンゲールは、この「途中から完成させる」問題がNP完全、かつ#P完全だと示した。古い遊びが、AI研究の性能試験の題材にもなっている。

2024年5月、LinkedInはPinpoint、Crossclimbと並んでQueensを公開した。行と列と色の領域ごとにクイーンを置く遊びである。8クイーンと同じ種類の制約が、ここにも使われている。ただし、開発者が8クイーンから着想したと述べた資料は、確認できていない。系譜というより、同じ型の遊びと読むのが安全だ。

盤から探索、色分け格子、画面へと続く系譜（イメージ・AI生成）

参考文献

本記事で参照した情報源(ベッツェルの原典、ナウクとガウスの書簡、グレイシャーの論文そのものは未確認。歴史の記述は下記の概説と論文による):

・Wikipedia: Eight queens puzzle

・Wikipedia(日本語): エイト・クイーン

・The n-queens problem (arXiv:2109.08083)

・Matemateca IME-USP: 8 Queens problem

・E. W. Dijkstra: EWD316, A Short Introduction to the Art of Programming

・EWD316 第9章: The problem of eight queens

・Wikipedia: Edsger W. Dijkstra

・Gent, Jefferson, Nightingale: Complexity of n-Queens Completion (JAIR 59, 2017)

・Wikipedia: LinkedIn(ゲーム機能の節)

・Aftermath: LinkedIn Games(Queens のルール紹介)

おわりに — 証明のない92と、百七十年後の盤

1850年、ナウクは92通りを手で見つけた。全部だという証明は、まだなかった。証明が出たのは、1874年である。答えが先に出て、理由があとから追いつく。数学の歴史では、よくある順序だ。

1848年の問いは、1971年には「考え方の見本」になり、2017年には「難しさの物差し」になった。2024年には、毎日遊ぶ画面の上にも、よく似た制約が並んでいる。

歴史的にこの盤が示したのは、一行の規則が、百七十年たっても尽きないということだ。駒は八つ、盤は一枚。それでも人は、順を変えて、また置き直す。

夜の盤に立つ、一つのクイーン（イメージ・AI生成）