Nクイーン問題

IT用語辞典バイナリ

Nクイーン問題

読み方：エヌクイーンもんだい
【英】n queens puzzle

Nクイーン問題とは、エイトクイーン問題と呼ばれる数学的パズルを応用した問題で、1辺のマスの数と使用する駒の数を任意に変更し、「盤上に互いの移動先を妨げないように配置する」という条件を満たす解の数を求める問題のことである。

エイトクイーン問題では、使用するマスの数はチェスの盤と同じ8×8マスであり、使用する駒の数は8個である。Nクイーン問題では、N×Nマス上で、N個の駒を用いる。数が多くなると解の数やパターンは飛躍的に増加する。例えば「12クイーン問題」では解の数は1000を優に超えるとされる。

Nクイーン問題は、シンプルであり、問題設定の拡張も容易であるため、プログラミング技術を習得する際の課題として利用されることも多い。

---

参照リンク
バックトラック法の解説 - （アドバンスド プログラミング）
Visualgos: N Queens - （英語）

情報処理のほかの用語一覧

アルゴリズム：

Levy曲線  モード  モンテカルロ法  Nクイーン問題  ラウンドロビンアルゴリズム  連結リスト  離散化

>>アルゴリズムカテゴリの他の用語