エイトクイーン問題について | バックトラックと n クイーン問題

1848年のチェスパズル

ドイツのチェスプロブレム作家マックス・ベッツェルは、1848年にベルリンのチェス雑誌でこのパズルを出題しました。フランツ・ナウクは1850年に92通りの解をすべて発表し、もっと大きな盤でも同じ問いを投げかけました。カール・フリードリヒ・ガウスはこのパズルに関心を持って見守り、手紙の中で論じています。

各行・各列にクイーン1個

互いに攻撃しない8個のクイーンは、8つの異なる行と8つの異なる列に置かれていなければなりません。つまり解は、1から8までの数を並べ替えたもの、すなわち順列に、規則を1つ加えたものです。その規則とは、どの2個のクイーンも同じ斜めの筋に並んではいけない、というものです。40,320通りの順列のうち、条件を満たすのは92通りだけです。

バックトラック

バックトラックは、解を1つずつ組み立てていき、行き詰まった瞬間に後戻りします。クイーンの場合はこうです。次の行の最初の安全なマスにクイーンを置き、安全なマスがない行に来たら、1つ上の行に戻ってそのクイーンを先へ進めます。1972年、エドガー・ダイクストラはまさにこの探索を使い、このパズルで構造化プログラミングを説明しました。

対称性

盤を4分の1回転させても、反転させても、解は解のままです。そのため、1つの解には最大8通りの姿があります。92通りの解は、こうしたグループ12個に分かれます。11個は8つの解を含み、1個は4つしか含みません。その解は半回転させても同じに見えるからです。

n クイーン問題

n×n の盤では、n 個のクイーンで同じ問いを考えます。4以上のすべての n に解があり、その数は急速に増えます。4×4では2通り、8×8では92通り、12×12では14,200通りです。解の数を求める公式は知られておらず、記録となっている値は大規模なコンピューター探索で得られたものです。

PictorX で試す

エイトクイーンを開き、マスをクリックしてクイーンを置きます。もう一度クリックすると取り除けます。「攻撃範囲を表示」は、あなたのクイーンが攻撃するマスに点を付けます。赤いクイーンは互いに攻撃し合っています。「解く」はバックトラック探索を1ステップずつ実行し、あなたが置いたクイーンはそのまま残します。「次の解」はすべての解を順番に表示し、「サイズ」で盤を4×4から12×12まで変えられます。

よくある質問

エイトクイーン問題を考案したのは誰ですか？

ドイツのチェスプロブレム作家マックス・ベッツェルで、1848年のことです。フランツ・ナウクが1850年に初めて解の完全な一覧を発表しました。

解は何通りありますか？

標準の盤では92通りです。回転や鏡像を1つと数えると12通りです。

なぜ6×6の盤は解がこんなに少ないのですか？

解は4通りしかなく、すべて1つのグループに属します。それより小さい5×5の盤には10通りあります。大きな盤ほど解は増え、7×7では40通り、8×8では92通りです。

PictorX は何かアップロードしますか？

いいえ。盤はブラウザーのキャンバスに描かれます。「保存」は PNG をダウンロードし、「編集」はその画像を PictorX のエディターで開きます。

関連ツール

試してみますか？

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エイトクイーンを試す