2013 | ゆっちのBlog

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

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

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

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

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

８クイーン問題では、王妃（クイーン）８個が用意されています。

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

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

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

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

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

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

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

しかし、その方法だと 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 通りまで激減させることができる。

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

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

private static void trySet(int i) {

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

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

王妃 i 列 j 行に配置

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

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

盤面を表示

}else {

王妃の利き筋（行、斜め）をセット

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

王妃の利き筋（行、斜め）を解除

                    }
             }
     }
}

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

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

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

nqueensproblem.NQueensProblem.java

package nqueensproblem;

/**
 *
 * @author Yucchi
 */
public class NQueensProblem {

    // 王妃数
    private static final int QUEENS = 4;
    // 王妃の配置位置 
    private static final int [] VERTICAL = new int [QUEENS];
    // 行に王妃が配置されてるかチェック用  
    private static final boolean [] HORIZONTAL = new boolean [QUEENS]; 
    // 右４５度斜めラインに王妃が配置されているかチェック用
    private static final boolean [] DIP_POSITIVE = new boolean [QUEENS * 2 -1]; 
    // 左４５度斜めラインに王妃が配置されているかチェック用
    private static final boolean [] DIP_NEGATIVE = new boolean [QUEENS * 2 - 1];
    // 安全 
    private static final boolean SAFE = false;
    // 危険 
    private static final boolean OUT = true;
    // トータルパターン数 
    private static int counter; 

    public static void main(String[] args) {
        trySet(0);
        if(counter < 1){
            System.out.println("配置不可能でした。");
        }else{
            System.out.println(counter + " パターン配置可能でした。");
        }
    }
    
    // 全ての可能な王妃の配置位置を取得、そしてトータルパターン数も取得する。
    private static void trySet(int i) {
        for (int j = 0; j < QUEENS; j++) {
            // 行 ( j )、／右４５度斜めライン ( i + j )、＼左４５度斜めライン (i - j + ( QUEENS -1 )) 配置チェック
         if (HORIZONTAL [j] == SAFE && DIP_POSITIVE [i + j] == SAFE && DIP_NEGATIVE [i - j + ( QUEENS -1)] == SAFE) { 
            VERTICAL [i] = j; // 王妃 i 列 j 行に配置
            if (i == ( QUEENS -1)) { // 王妃の配置完了
                 counter++; // トータルパターン数カウンター
                 printBoard(); // 盤面を表示
             }else {
                // 王妃の利き筋（行、斜め）をセット
               HORIZONTAL [j] = DIP_POSITIVE [i + j] = DIP_NEGATIVE [i - j + ( QUEENS -1)] = OUT;
               // 次の列を配置
               trySet(i + 1);
               // 王妃の利き筋（行、斜め）を解除
               HORIZONTAL [j] = DIP_POSITIVE [i + j] = DIP_NEGATIVE [i - j + ( QUEENS -1)] = SAFE;
            }
         }
      }
    }

    // 全ての可能な王位配置位置を出力　●が王妃が置かれた場所である。
    private static void printBoard() {
        System.out.println("第 " + counter + " パターン"); 
        for (int i = 0; i < QUEENS; i++) {
         for (int j = 0; j < QUEENS; j++) {
                System.out.printf("%s", j == VERTICAL [i] ? "● " : "□ ");
            }
         System.out.println();
      }
      System.out.println();

    }
}

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

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