Nクイーン問題 nQueens Problem

Java

Java で Nクイーン問題  nQueens Problem をプログラミングしてみました。

まず Nクイーン問題とは何か?

ネットでググってみると8クイーン問題ってのがよくとりあげられてます。

Nクイーン問題とはそれを一般化したようです。

では8クイーン問題から調べていきましょう。

8クイーン問題では、王妃(クイーン)8個が用意されています。

チェス盤のサイズは王妃(クイーン)と同じ数とします。

8クイーンでは縦、横8マスです。

そのチェス盤に全ての王妃(クイーン)を配置します。

ただし、それぞれの王妃(クイーン)の利き筋には配置できません。(縦、横、斜めの4ライン)

bord_n

以上の条件を全て満たす王妃(クイーン)の配置パターン及び総数を求めるものです。

それではどうやって解を導き出したらいいのか考えてみることにします。

8個の王妃(クイーン)を全ての組み合わせに配置して上記の条件をクリアするかを確認すればいいだけのことですね。

しかし、その方法だと 8 X 8 = 64 マスあるから

64 X 63 X 62 X 61 X 60 X 59 X 58 X 57 = 178,462,987,637,760 通りもあることになります。

ちょっと多いですね。

王妃(クイーン)の数が大きくなった時のことを考えたら厳しいです。

しかし、全ての組み合わせを調べる必要はなさそうです。

何故なら、同じ列、行に王妃は配置できないからです。

縦、横の利き筋の条件を考慮した結果、各列、行には王妃(クイーン)は 1 個だけしか配置できない!

よって、 8! = 40,320 通りまで激減させることができる。

あと斜めの利き筋2つを利用すれば計算処理はもっと少なくなるだろう。

bord_d_pos 

bord_d_neg

以上のことを考慮した上で次のようなプログラムを作ればいいかもしれない。

private static void trySet(int i) {

     for (王妃の数だけループ) {

         if (利き筋から外れていれば) {

              王妃 i 列 j 行に配置

            if (i == (王妃8個配置できたら) {

                 トータルパターン数をカウントアップ

                 盤面を表示

            }else {

                    王妃の利き筋(行、斜め)をセット

                    次の列を配置(再帰 trySet(i + 1))

                    王妃の利き筋(行、斜め)を解除

                    }
             }
     }
}

 

ってことで作ってみました。

ただ、デバッガでプログラムの流れを追うために王妃(クイーン)の数は 4 としました。

もちろん、王妃(クイーン)の数は一般化できるようにしてあります。

 

nqueensproblem.NQueensProblem.java

 

さて、理屈やコードだけでは解りにくいかもしれないのでこのプログラムの流れをデバッグ実行して確認してみます。

デバッグウィンドウやウォッチポイントの変数の値を確認しながらごらんくださいませ。

 

 

n1

プログラムの流れを見ていると人間の思考原理に非常に良く似ていますね。

とりあえず順番に試してみる。

条件を考慮して無駄なことはせず作業量を減らす。

途中で駄目だと判断できたら戻って次のパターンからやり直す。

それの繰り返しで処理を完了する。

こういったアルゴリズムはバックトラック法って言われているようです。

深さ優先探索アルゴリズムですね。

試行錯誤的に解を探し出すタイプの問題に有効です。

つまり、基本的に全ての選択肢を試してみるしか無い場合なんかには有効のようです。

いつ頃、誰が、どのような理由でこういったアルゴリズムを考えたのか?

考えた人を心から尊敬します。

ちなみに 8王妃問題としてプログラムを実行したい場合は上記プログラムの 9 行目の

private static final int QUEENS = 4; // 王妃数

王妃数を 8 に変更してください。

任意の王妃数をこれによって設定できますがあまり王妃数を大きくすると計算量が指数関数的に増加するでしょうからほどほどに(^_^;

a_001

再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。

再帰アルゴリズム その1

再帰アルゴリズム その2

ユークリッドの互除法 Euclidean Algorithm

ハノイの塔 Tower of Hanoi

Hatena タグ:
このエントリーをはてなブックマークに追加
Share on Facebook

« »

Leave a Reply

* が付いている項目は、必須項目です!

*

次の HTML タグと属性を利用できます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

Trackback URL