8퀸 문제 (재귀 호출)

8개의 퀀을 8x8판에 배치시키는데 서로가 잡힐 수 없도록 배치하는 가지수를 찾아내는 것이다.

퀸은 자신과 같은 열에 있는 다른 퀸을 공격하므로 각 열에 퀸을 1개만 배치해야 한다.
pos라는 배열은 각 배열의 인덱스가 열이 되고, 각 인덱스의 값들이 행이 된다.
즉 한 줄로 8x8의 배치 형태를 표시할 수 있다.


문제에 접근하기 앞서 순차적으로 문제에 접근을 해보자.
이것은 단순히 하나의 열에 퀸이 있다면 그 열에는 퀸이 있을 수 없다는 규칙만을 적용하여 도출된 계산이다.
pop[0]에 0이 있다면 퀸은 최상단좌측에 한개가 위치한 것인데 0열은 또 다른 퀸이 들어갈 수 없으므로 그 다음 열에 퀸이 들어갈 경우의 수가 8가지가 된다.
이런식으로 계산을 하면 $8^8$ 가지의 퀸의 배치 경우의 수가 도출된다.
이것은 단순 가지 뻗기 방식의 퀸의 배치방법이다.

* 가지 뻗기 식의 퀸의 배치

public class QueenB {
    static int[] pos = new int[8]; //각 열의 퀸의 위치를 숫자로 저장

    //각 열의 퀸의 위치를 출력합니다.
    static void print() {
        for (int i = 0; i < 8; i++)
            System.out.printf("%2d", pos[i]);
        System.out.println();
    }

    //i열에 퀸을 놓습니다.
    static void set(int i) { //i:열
        for (int j = 0; j < 8; j++) {
            pos[i] = j; //j:행, 퀸을 j행에 배치합니다.
            if (i == 7)
                print(); //배치된 퀸들을 출력한다.
            else
                set(i + 1); //다음 열에 퀸을 배치한다.
        }
    }
    public static void main(String[] args) {
        set(0); //0열에 퀸을 배치한다.
    }
}

여기서 각 열에 퀸을 1개를 배치하는 조건 뿐만이 아니라 각 행에도 퀸을 한개씩만 배치하여야 하는 조건을 추가해 보자.

public class QueenBB {
    static boolean[] flag = new boolean[8]; //각 행에 퀸을 배치했는데 체크하는 배열
    static int[] pos = new int[8]; //각 열의 퀸의 위치

    //각 열의 퀸의 위치를 출력합니다.
    static void print() {
        for (int i = 0; i < 8; i++)
            System.out.printf("%2d", pos[i]);
        System.out.println();
    }

    static void set(int i) {
        for (int j = 0; j < 8; j++) {
            if(flag[j] == false) { //j행에 퀸을 배치 하지 않았다면
                pos[i] = j; //퀸을 j행에 배치한다.
                if(i == 7) 
                    print();
                else{
                    flag[j] = true; //j행에 배치했으니 flag를 true로 변경
                    set(i + 1); //그리고 다음 열에 퀸을 배치할 때 0행에는 배치가 되지 않는다.
                    flag[j] = false; //그리고 다시 j행은 false 로 변경한다
                }
            }
        }
    }
    public static void main(String[] args) {
        set(0); //0열에 퀸을 배치한다.
    }
}

퀸은 가로 세로 뿐만아니라 대각선으로도 이동할 수가 있다.
따라서 퀸이 배치가 되면 배치된 퀸에서 대각선으로도 퀸을 배치하지 않도록 해야한다.

public class EightQueen {
    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++)
            System.out.printf("%2d", pos[i]);
        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;
                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); //0열에 퀸을 배치한다.
    }

}

대각선 방향에 퀸이 배치가 되었는지 체크하는 배열의 길이가 15개인 이유는 8x8 정사각형의 대각선 방향은 2가지 인데 각 방향마다 15개의 사선이 그려진다.
맨 처음 퀸이 위치하면 가로와 대각선방향으로는 퀸이 위치해서는 안된다. ↗대각선 방향의 사선들 중에 하나의 ↗은 ↗에 배치된 퀸의 행(j)과 열(i)의 합이 동일하다.
고로 flag_b[i + j]를 true로 만든 후 경우의 수를 제거해야한다.
이러한 방법으로 ↘대각선 방향도 규칙을 찾아내어 공식으로 만들면 된다.