Javaによるアルゴリズムとデータ構造

演習5-8の解答

■□□□□□□□
□□□□□□■□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
□□□□□■□□
□□■□□□□□

　List 5-9のメソッドprint を改良して、盤面を右のように記号文字を用いて分かりやすく表示するプログラムを作成せよ。

// 演習5-8
// ８王妃問題を解く（盤面を□と■で表示）

class EightQueenEx {

    static boolean[] flag_a = new boolean[8];    // 各行に王妃が配置済みか
    static boolean[] flag_b = new boolean[15];    // ／対角線に王妃が配置済みか
    static boolean[] flag_c = new boolean[15];    // ＼対角線に王妃が配置済みか
    static int[] pos = new int[8];                // 各列の王妃の位置

    //--- 盤面（各列の王妃の位置）を出力 ---//
    static void print() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++)
                System.out.printf("%s", j == pos[i] ? "■" : "□");
            System.out.println();
        }
        System.out.println();
    }

    //--- i列目の適切な位置に王妃を配置 ---//
    static void set(int i) {
        for (int j = 0; j < 8; j++) {
            if (flag_a[j] == false &&            // 横に未配置
                flag_b[i + j] == false &&        // ／対角線に未配置
                flag_c[i - j + 7] == false) {    // ＼対角線に未配置
                pos[i] = j;                        // 王妃をj行に配置
                if (i == 7)                        // 全列に配置終了
                    print();
                else {
                    flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
                    set(i + 1);
                    flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        set(0);
    }
}

戻る