エイト・クイーン

エイト・クイーンとは

エイト・クイーンは、チェスの盤面とクイーンの駒を使ったパズルゲームです。このパズルの目的は、チェス盤上に8個のクイーンを、どのクイーンも他のクイーンに取られないように配置することです。

ルール

チェス盤上でクイーンは、縦、横、斜めの8方向に、他の駒に遮られることなく進むことができます。この動きは、将棋の飛車と角行を合わせたものに相当します。エイト・クイーンでは、このクイーンの動きの特性を利用して、互いに攻撃できない位置に8つのクイーンを配置することが求められます。

例えば、4つの駒で説明すると、以下のような配置が考えられます。

例A (正しい配置): どの駒も他の駒に攻撃されない位置にあるため、これは正しい配置です。
例B (誤った配置): 2つの駒が互いに攻撃できる位置にあるため、これは誤った配置となります。

歴史

このパズルは1848年にチェスプレイヤーのマックス・ベッツェルによって考案されました。その後、カール・フリードリヒ・ガウスをはじめとする多くの数学者がこの問題に挑戦しました。1874年には、グンターが行列式を用いて解法を提案し、イギリスの数学者グレイシャーが、基本となる解が12個であることを確認しました。

解

エイト・クイーンの基本解は12種類存在します。これらの解は、回転や鏡像操作によって様々なバリエーションを生み出します。具体的には、11個の基本解はそれぞれ8通りの変形が可能で、残りの1つは点対称であるため4通りの変形しか持ちません。したがって、エイト・クイーンの総解数は92通り (8×11 + 4 = 92) となります。

n-クイーン

エイト・クイーンの拡張版として、盤面の一辺のマス数をnとした「n-クイーン」というパズルも存在します。例えば、「4-クイーン」は4×4の盤面に4つのクイーンを配置する問題です。このn-クイーンの解法は、盤面が大きくなるにつれて組み合わせが爆発的に増加します。

2-クイーンと3-クイーンには解が存在しません。しかし、4-クイーン以上では、盤面の一辺のマス数と等しい数のクイーンを配置できます。nが増加するにつれて解の数は一般的には増加しますが、n=5からn=6のように解の数が減少する場合もあります。

2009年には、ドレスデン工科大学によって26-クイーンの解が計算され、2016年にはQ27 Projectによって27-クイーンのすべての解が求められました。以下は、n=27までの解の数です。

大衆文化

エイト・クイーンは、そのパズルとしての面白さから、様々な大衆文化作品にも登場しています。

ザ・セブンス・ゲスト: コンピューターゲーム「ザ・セブンス・ゲスト」には、「ザ・クイーンズ・ジレンマ」というエイト・クイーンをモチーフにしたパズルが登場します。
レイトン教授と不思議な町: ニンテンドーDS用ゲーム「レイトン教授と不思議な町」には、「クイーンの問題5」というエイト・クイーンをベースにしたナゾが登場します。

関連項目

力まかせ探索: 全ての可能性を試す探索アルゴリズムの一種。
バックトラッキング: 解を探索する際に、探索の途中で解が見つからないと判断した場合に、探索をやり直すアルゴリズム。
数学パズル: 数学的な思考を必要とするパズル。
利かずの駒並べ: チェスや将棋の駒を特定の条件に従って盤面に並べるパズルの一種。

外部リンク

NQueens Project：n-クイーンパズルの解を求める分散コンピューティングプロジェクトのウェブサイト
General method n queens with implementation in java：Javaによるn-クイーン問題の実装方法に関する情報
* 8Queens in C,Java,C++：C, Java, C++での8クイーンの実装例

もう一度検索