エイト・クイーン

エイト・クイーンとは、チェスの盤とコマを使用したパズルの名称である。

ルール

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。

4駒で簡略に解説すると、

例Aではどの駒も他の駒に取られない位置にあるので正しい配置。例Bでは20pxの2駒が互いに取られる位置にあるので誤った配置となる。

歴史

このパズルは、1848年にチェスプレイヤーのマックス・ベッツェルによって提案された。ガウスを含む多くの数学者がこの問題に挑戦した。1874年に Gunther が行列式を用いて解く方法を提案し、イギリスのグレイシャー(Glaisher)が全解が12個であることを確認した。

解

基本解は12種類ある。下記の解1〜11は、回転と鏡像でそれぞれ8種類の変形がある。解12は点対称なので、4種類の変形しかない。したがって、解の総数は 92（＝8×11＋4）になる。

n-クイーン

一辺のマスをnとした変形版を「n-クイーン」パズルという。例えば「4-クイーン」では4×4のマスで4個の駒を使用する（他にも縦横比が1:1ではない矩形や、ペグ・ソリティアの盤面、不定形などいろいろ考えられるがここでは言及しない）。

• 2-クイーンと3-クイーンには解がない。
• 4-クイーン以上なら一辺のマス数に等しい数のクイーンが置ける。

単純に見てnが増えるのに従って、全マス数n²個に対し置く駒の数はn個であるから、置ける場所（の候補）の増え方により、解の数には組合せ爆発が起きる（ただしnが5から6に増える場合は解の数が減少する）。2009年にドレスデン工科大学で26-クイーンが計算された。現在すべての解が判明している最大のものは、2016年にQ27 Projectによって計算された27-クイーンである。
n=27までの解は次の通り。

n	基本解	バリエーション解
1	1	1
2	0	0
3	0	0
4	1	2
5	2	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724
11	341	2 680
12	1 787	14 200
13	9 233	73 712
14	45 752	365 596
15	285 053	2 279 184
16	1 846 955	14 772 512
17	11 977 939	95 815 104
18	83 263 591	666 090 624
19	621 012 754	4 968 057 848
20	4 878 666 808	39 029 188 884
21	39 333 324 973	314 666 222 712
22	336 376 244 042	2 691 008 701 644
23	3 029 242 658 210	24 233 937 684 440
24	28 439 272 956 934	227 514 171 973 736
25	275 986 683 743 434	2 207 893 435 808 352
26	2 789 712 466 510 289	22 317 699 616 364 044
27	29 363 791 967 678 199	234 907 967 154 122 528

関連項目

• 力まかせ探索
• バックトラッキング
• 数学パズル

外部リンク

• NQueens Project 「n-クイーン」パズルの解を求める分散コンピューティング
• 8Queens in C,Java,C++