Nクイーン問題

Nクイーン問題は、チェスの盤面 N×Nマスに N個のクイーンを、どの二つのクイーンも互いに利き筋に入らないように配置する組み合わせパズル、およびそれを解くためのアルゴリズム問題のことであり、制約充足問題（Constraint Satisfaction Problem, CSP）の代表的な例として知られ、バックトラッキング（後戻り）探索アルゴリズムの典型的な適用例としてコンピュータサイエンスで広く研究される問題のことです。

Nクイーン問題の概要とルール

Nクイーン問題は、8クイーン問題（N=8 の場合）の一般化であり、与えられた N の値に対して、クイーンの配置がルールの制約を満たす全ての手順を見つけ出すことを目標とします。

1. 問題の定義

N×Nのチェス盤にN個のクイーンを配置します。

2. クイーンの利き筋の制約

チェスにおけるクイーンの動きに基づき、以下のどの条件も満たしてはなりません。すなわち、どの二つのクイーンも互いに取り合える位置にあってはならないということです。

• 同一行（Row）: どの二つのクイーンも同じ行に配置されてはならない。
• 同一列（Column）: どの二つのクイーンも同じ列に配置されてはならない。
• 同一斜め（Diagonal）: どの二つのクイーンも同じ対角線上に配置されてはならない。

N個のクイーンを配置する場合、同一行の制約があるため、通常は「各行に必ずクイーンを1つだけ配置する」という前提で問題を簡略化し、探索アルゴリズムの効率を高めます。

主な目的は、Nの値に対して、すべての有効な配置の総数（解の数）を求めたり、有効な配置のうちの一つを見つけたりすることです。

Nクイーン問題を解くアルゴリズム

Nクイーン問題の解法は、総当たり（ブルートフォース）探索を行うと計算量が爆発的に増大するため、効率的なバックトラッキング（後戻り）探索アルゴリズムが採用されます。

1. バックトラッキングの基本原理

バックトラッキングは、探索空間を効率的に剪定（せんてい）するための再帰的な探索アルゴリズムです。Nクイーン問題における手順は以下の通りです。

1. クイーンの配置: 現在の行 r において、クイーンを配置可能な列 c を順に試します。
2. 安全性の確認: クイーンを (r, c) の位置に置いた場合、既に配置されている他のクイーンと衝突しないか（同一列、同一斜め上にないか）を確認します。
3. 成功と再帰: 衝突しない場合、そのクイーンを配置し、次の行 r+1 の探索を再帰的に呼び出します。
4. 失敗と後戻り: 次の行 r+1 でクイーンを安全に配置できる場所が見つからなかった場合、または現在の位置 (r, c) が衝突する場合、現在のクイーンをその位置から取り除き（後戻り）、現在の行 r における次の列 c+1 を試します。
5. 終了: 全てのクイーン（N 個）を配置できた場合、解が一つ見つかったとして記録します。すべての列を試した後、探索を終了します。

2. 安全性の数学的表現

座標 (r_1, c_1) に配置されたクイーンと、現在の探索位置 (r_2, c_2) の衝突判定は、以下の条件で確認できます。

• 同一列の制約: c_1 = c_2 でないこと。
• 同一斜めの制約: 絶対値を利用して、行の差と列の差が等しいかどうかで判断します。

でないこと。

Nクイーン問題の計算量と解の数

1. 計算量の比較

N 個のクイーンを配置する問題の総当たりで可能な配置の総数は、N 個のクイーンが行を区別しないとして ((N^2)!) / (N! * (N^2 – N)!)通りとなりますが、行を区別する場合、各行で N 通りの選択肢があるため N^N通りの配置が考えられます。

しかし、「各行に1つのクイーン」の制約を適用すると、可能な配置はN個のクイーンを N列に配置する組み合わせ、すなわち Nの階乗 N!通りに限定されます。

バックトラッキングアルゴリズムを用いると、早い段階で不可能な経路を剪定するため、実際の計算時間は $N!$ よりも大幅に効率的になります。

2. 解の数の例

Nが大きくなるにつれて解の数は急速に増加しますが、解が存在しない Nの値も存在します。

N	解の数
1	1
2	0
3	0
4	2
5	10
8	92
10	724

N=2および N=3の場合は、ルールを満たす配置が存在しないことが知られています。

関連用語

お問い合わせ

システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。