Nクイーン問題とは
Nクイーン問題は、チェスの盤面 $N \times N$ マスに $N$ 個のクイーンを、どの二つのクイーンも互いに利き筋に入らないように配置する組み合わせパズル、およびそれを解くためのアルゴリズム問題のことであり、制約充足問題（Constraint Satisfaction Problem, CSP）の代表的な例として知られ、バックトラッキング（後戻り）探索アルゴリズムの典型的な適用例としてコンピュータサイエンスで広く研究される問題のことです。
Nクイーン問題の概要とルール
Nクイーン問題は、8クイーン問題（$N=8$ の場合）の一般化であり、与えられた $N$ の値に対して、クイーンの配置がルールの制約を満たす全ての手順を見つけ出すことを目標とします。
1. 問題の定義
$N \times N$ のチェス盤に $N$ 個のクイーンを配置します。
2. クイーンの利き筋の制約
チェスにおけるクイーンの動きに基づき、以下のどの条件も満たしてはなりません。すなわち、どの二つのクイーンも互いに取り合える位置にあってはならないということです。
- 同一行（Row）: どの二つのクイーンも同じ行に配置されてはならない。
- 同一列（Column）: どの二つのクイーンも同じ列に配置されてはならない。
- 同一斜め（Diagonal）: どの二つのクイーンも同じ対角線上に配置されてはならない。
$N$ 個のクイーンを配置する場合、同一行の制約があるため、通常は「各行に必ずクイーンを1つだけ配置する」という前提で問題を簡略化し、探索アルゴリズムの効率を高めます。
主な目的は、$N$ の値に対して、すべての有効な配置の総数（解の数）を求めたり、有効な配置のうちの一つを見つけたりすることです。
Nクイーン問題を解くアルゴリズム
Nクイーン問題の解法は、総当たり（ブルートフォース）探索を行うと計算量が爆発的に増大するため、効率的なバックトラッキング（後戻り）探索アルゴリズムが採用されます。
1. バックトラッキングの基本原理
バックトラッキングは、探索空間を効率的に剪定（せんてい）するための再帰的な探索アルゴリズムです。Nクイーン問題における手順は以下の通りです。
- クイーンの配置: 現在の行 $r$ において、クイーンを配置可能な列 $c$ を順に試します。
- 安全性の確認: クイーンを $(r, c)$ の位置に置いた場合、既に配置されている他のクイーンと衝突しないか（同一列、同一斜め上にないか）を確認します。
- 成功と再帰: 衝突しない場合、そのクイーンを配置し、次の行 $r+1$ の探索を再帰的に呼び出します。
- 失敗と後戻り: 次の行 $r+1$ でクイーンを安全に配置できる場所が見つからなかった場合、または現在の位置 $(r, c)$ が衝突する場合、現在のクイーンをその位置から取り除き（後戻り）、現在の行 $r$ における次の列 $c+1$ を試します。
- 終了: 全てのクイーン（$N$ 個）を配置できた場合、解が一つ見つかったとして記録します。すべての列を試した後、探索を終了します。
2. 安全性の数学的表現
座標 $(r_1, c_1)$ に配置されたクイーンと、現在の探索位置 $(r_2, c_2)$ の衝突判定は、以下の条件で確認できます。
- 同一列の制約: $c_1 = c_2$ でないこと。
- 同一斜めの制約: 絶対値を利用して、行の差と列の差が等しいかどうかで判断します。
でないこと。
Nクイーン問題の計算量と解の数
1. 計算量の比較
$N$ 個のクイーンを配置する問題の総当たりで可能な配置の総数は、$N$ 個のクイーンが行を区別しないとして $\frac{(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までお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
