導入
| ||||||||||||
| 解決策の例 | ||||||||||||
8 クイーン問題の目標は、チェスのゲームのルール (駒の色は次のとおり) に従って、クイーンが互いに脅かすことができないように、チェスのゲームから 8 つのクイーンを 8 × 8 の正方形のチェス盤上に配置することです。無視されます）。したがって、2 人の女性が同じ行、列、または対角線を共有してはなりません。この問題は数学の問題の領域に属し、チェスの構成の領域には属さないことに注意してください。
単純ですが自明ではないこの問題は、プログラミング手法を説明するための例としてよく使用されます。
歴史
長年にわたり、ガウスを含む多くの数学者がこの問題に取り組んできました。この問題は、1850 年にフランツ・ナウクによって提起されたnクイーンの一般化問題の特殊なケースであり、チェス盤上にn 個の「自由な」クイーンを配置するというものです。 n × n 個のボックス。 1874 年に、S. Gunther は行列式を使用して解を見つける方法を提案し、JWL Glaisher はこのアプローチを洗練させました。
このグリッチは、1990 年代初頭にコンピュータゲーム「 The 7th Guest」で使用されました。
バリエーション
- さまざまなパーツを使って
32 人の騎士、14 人の司教、または 16 人の王を伝統的なチェス盤上に配置できます。妖精のチェスの駒はチェッカーの代わりになります。
- さまざまなチェス盤で
- ポリヤは、トロイダル チェス盤上のn-チェッカーの問題を研究しました。 3 次元のチェス盤など、他のメディアも使用されています。
- 支配の問題
- 問題は、 n × nチェス盤上のすべてのマス目を制御するために必要なチェッカー (または他の駒) の最小数を見つけることです。たとえば、「8×8」チェス盤の場合、この数は 5 に相当します。
- 9人の女王の問題
- 古典的なチェス盤に 9 人のクイーンとポーンを配置し、クイーン同士が奪い合うことを避けなければなりません。この問題は、 n × n 個のチェス盤とr 個のクイーン ( r > n ) を考慮することによって一般化され、クイーンとポーンが互いに脅かされることなくチェス盤上に配置できるようなポーンの最小数を見つける必要があります。
- 魔法陣
- 1992 年に、Demirörs、Rafraf、tanik は、魔方陣をn- queens 問題の解に変換したり、その逆に変換したりする方法を発表しました。
- ラテン広場
- チェスの問題
- チェスの問題の種類
解決策
8 チェッカー問題には 92 の異なる解があり、回転や反射などの変換を考慮すると 12 の解しかありません (バーンサイドの補題による)。