エイト・クイーン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/11 03:30 UTC 版)
エイト・クイーンとは、チェスの盤とコマを使用したパズルの名称である。
ルール
チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。
クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。
4駒で簡略に解説すると、
|
配置例 A
|
配置例 B
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
例Aではどの駒も他の駒に取られない位置にあるので正しい配置。例Bでは
の2駒が互いに取られる位置にあるので誤った配置となる。
歴史
このパズルは、1848年にチェスプレイヤーのマックス・ベッツェルによって提案された。ガウスを含む多くの数学者がこの問題に挑戦した。1874年に Gunther が行列式を用いて解く方法を提案し、イギリスのグレイシャー (en:Glaisher) が全解が12個であることを確認した。
解
基本解は12種類ある。下記の解1〜11は、回転と鏡像でそれぞれ8種類の変形がある。解12は点対称なので、4種類の変形しかない。したがって、解の総数は 92（＝8×11＋4）になる。
|
8
解 1
|
8
解 2
|
8
解 3
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
8
解 4
|
8
解 5
|
8
解 6
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
8
解 7
|
8
解 8
|
8
解 9
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
8
解 10
|
8
解 11
|
8
解 12
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
n-クイーン
一辺のマスをnとした変形版を「n-クイーン」パズルという。例えば「4-クイーン」では4×4のマスで4個の駒を使用する（他にも縦横比が1:1ではない矩形や、ペグ・ソリティアの盤面、不定形などいろいろ考えられるがここでは言及しない）。
- 2-クイーンと3-クイーンには解がない。
- 4-クイーン以上なら一辺のマス数に等しい数のクイーンが置ける。
単純に見てnが増えるのに従って、全マス数n2個に対し置く駒の数はn個であるから、置ける場所（の候補）の増え方により、解の数には組合せ爆発が起きる（ただしnが5から6に増える場合は解の数が減少する）。2009年にドレスデン工科大学で26-クイーンが計算された[1]。現在すべての解が判明している最大のものは、2016年にQ27 Projectによって計算された27-クイーンである[2]。
n=27までの解は次の通り[3]。
| 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]。
関連項目
出典
- ^ “QUEENS@TUD”. "2016-09-07"閲覧。
- ^ “Q27 Project: Facts”. "2018-02-10"閲覧。
- ^ “QUEENS@TUD: Facts”. "2016-09-07"閲覧。
- ^ DeMaria, Rusel (1993年11月15日). The 7th Guest: The Official Strategy Guide. Prima Games. ISBN 978-1-5595-8468-5 2021年4月22日閲覧。
- ^ “ナゾ130 クイーンの問題5”. ゲームの匠. 2021年9月17日閲覧。
外部リンク
- NQueens Project[リンク切れ] 「n-クイーン」パズルの解を求める分散コンピューティング
- General method n queens with implementation in java
- 8Queens in C,Java,C++[リンク切れ]
エイトクイーン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/21 05:58 UTC 版)
エイトクイーンパズルでは、8つのクイーンが（名前をつけるなどして）それぞれ別のものと考えることができるならば 3 709 440 個の異なる解がある。しかし通常は8つのクイーンはすべて同じものと考えるので「クイーンを入れ替える違いを除いて、独立な解は 92 (= 3 709 440/8!) 個である」ということができる。ここでは異なる配置が、チェス盤の向きはそのまま動かさず、クイーン全体としての配置も変わらずにクイーン同士で入れ替えを行ったものになっているとき、それらの配置が同値であるものとすることになっている。
※この「エイトクイーン」の解説は、「違いを除いて」の解説の一部です。
「エイトクイーン」を含む「違いを除いて」の記事については、「違いを除いて」の概要を参照ください。
- エイト・クイーンのページへのリンク
