エイト・クイーン

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

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

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

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

配置例 A

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

配置例 B

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

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

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

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

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 1

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 2

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 3

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 4

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 5

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 6

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 7

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 8

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 9

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 10

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 11

8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

解 12

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

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

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

さらに見る n, 基本解 ...

$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

閉じる

コンピューターゲームのザ・セブンス・ゲスト（英語版）で、ヘンリー・ストーフの屋敷のゲームルームに、ザ・クイーンズ・ジレンマ（The Queen's Dilemma）という8番目のパズルがある、このパズルは、事実上のエイト・クイーンのパズルである。^[4]^{(pp48-49,289-290)}
ニンテンドーDS用ゲームのレイトン教授と不思議な町で、物語の結末を知る者の部屋にある「クイーンの問題5」という130番目のナゾは、事実上エイト・クイーンのパズルである^[5]。

[1]
“QUEENS@TUD（英語）”. "2016-09-07"閲覧。
[2]
“Q27 Project: Facts（英語）”. "2018-02-10"閲覧。
[3]
“QUEENS@TUD: Facts（英語）”. "2016-09-07"閲覧。
[4]
DeMaria, Rusel (1993年11月15日). The 7th Guest: The Official Strategy Guide. Prima Games. ISBN 978-1-5595-8468-5 2021年4月22日閲覧。
[5]
“ナゾ130　クイーンの問題5”. ゲームの匠. 2021年9月17日閲覧。

NQueens Project^{[リンク切れ]} 「n-クイーン」パズルの解を求める分散コンピューティング
General method n queens with implementation in java
8Queens in C,Java,C++^{[リンク切れ]}

[1] [1]
“QUEENS@TUD（英語）”. "2016-09-07"閲覧。

[2] [2]
“Q27 Project: Facts（英語）”. "2018-02-10"閲覧。

[3] [3]
“QUEENS@TUD: Facts（英語）”. "2016-09-07"閲覧。

[4] [4]
DeMaria, Rusel (1993年11月15日). The 7th Guest: The Official Strategy Guide. Prima Games. ISBN 978-1-5595-8468-5 2021年4月22日閲覧。

[5] [5]
“ナゾ130　クイーンの問題5”. ゲームの匠. 2021年9月17日閲覧。

[1]

[2]

[3]

[4]

[5]

エイト・クイーン

Wikiwand in your browser!

エイト・クイーン

Wikiwand in your browser!

ルール

歴史

解

n-クイーン

大衆文化

関連項目

出典

外部リンク