プログラミング入門の定番です。
リカーシブ・アルゴリズムの例題として提示されることも多いのですが、 全数探索の例題としてもよく使われます。

「すべてのケースを洗い出して調べてみる」 しかないと考えられる問題で、

• 漏れなく調べる
• 無意味なケースを上手に排除する

［エイト・クィーンの問題］

チェス盤を一般化して、縦横Ｎマスの盤にＮ個のクィーンを置く問題を Ｎ−Ｑｕｅｅｎ問題といいます。この問題は、Ｎが増加するにつれて 計算の手間が、ｅ^N に比例して増加することで 知られています。Ｎが８とか１０であればあっという間に計算できますが、 Ｎが大きくなるにつれて計算時間が急激に増加します。 このように、問題のサイズが大きくなるにつれて 計算時間が指数関数的に増加する問題をＮＰ問題といいます。

概ね、以下の戦略ですべての組み合わせを網羅します。

• 上から下へ、左から右へ、置ける場所を探す
• ある行に置けたら、その下の行の左から置ける場所を探す
• ある行のどこにも置けないと判ったら、 ひとつ上の行の（置いた位置が間違っていたとして） 置ける場所を探す作業を継続する
• 一番下の行で置ける場所が見つかったら、一丁あがり
• さらに他の解も探すのであれば、ひとつ上の行の続きを探す
  この場合は、一番上の行の置ける位置を全部調べ終わるまで続ける

Ｊａｖａ の メソッド風の書き方で、 「 n 行目に置く」 という checkAndSet( n ) を書いてみましょう。 ｎ 行目の置ける場所を探すには、ｎ 行目以降 一番下まで ちゃんと置けることを確認しなければいけません。
行は ０、１、２、．．．、７ までの８行です。

ｎ行目の ｋ列目にクイーンを置くことを

と表しましょう。たとえば、ｐｏｓ が { 0, 4, 7, 5, 2, 6, 1, 3 } であれば、下図のような盤とクイーンの配置を表すことにします。

クイーンの縦の利き筋は、ｐｏｓに同じ番号がないかどうかで調べられます。 右上がり方向の利き筋は、 行と列の和が等しいことで調べられます。 右下がり方向の利き筋は、 行と列の差が等しいかどうかで調べられます。クイーンを置いたときに、 列の番号をｐｏｓに保存すると同時に、行番号から列番号を引いたものを ｎａ に 行番号と列番号の和を ｎｓ に設定しておくことにします。

行番号つきプログラム・リスト

ソースプログラムは、 EightQueen4.java です。

実行には、次の４つの GIF ファイルが必要です。プログラムと同じフォールダにダウンロードしてください。