[자료구조&알고리즘] 8퀸 문제 - 자바

8퀸 문제란?

8퀸 문제란 8개의 퀸이 서로 공격하여 잡을 수 없도록 체스판에 배치하는 문제입니다.

• 체스판의 크기는 8*8
• 퀸은 체스판의 대각선을 포함한 모든 방향으로 어떤 위치든 직선 이동이 가능

퀸을 배치하는 방법

8개의 퀸을 체스판에 배치하는 경우의 수는 체스판이 8*8 = 64 칸으로 되어있기 때문에 다음과 같습니다.

64*63*62*61*60 ... * 57 = 178,462,987,637,760

보기만 해도 말도 안 되는 저 경우의 수들을 어떤 조합이 조건을 만족하는지 하나하나 살펴보는 것은 상당히 비효율적입니다.

이를 해결하기 위해 규칙 두가지를 세워보도록 하겠습니다.

[규칙 1] 각 열에 퀸을 1개만 배치한다.

규칙 1을 적용하면 경우의 수는 8*8*8*8*8*8*8*8=16,777,216 개로 대폭 줄기는 했지만, 여전히 큰 수이며 같은 행의 퀸을 공격할 수 있기 때문에 규칙 하나를 더 추가합니다.

[규칙 2] 각 행에 퀸을 1개만 배치한다.

가지 뻗기 - 규칙 1(각 열에 퀸 1개만 배치) 만족하기

• 각 열에 1개의 퀸을 배치하는 조합을 재귀를 사용하여 나열한다.
• 아래 코드를 실행해보면 0 0 0 0 0 0 0 0 ~ 7 7 7 7 7 7 7 7 까지 정상적으로 모든 조합이 출력되는 것을 볼 수 있다.

public class Queen {
      //에를 들어 pos 배열이 [7,7,7,7,7,7,7,7]이면 모든 열의 퀸이 7행에 배치되어 있는 것.
    static int[] pos = new int[8]; //각 열의 퀸의 위치

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

    //i열에 퀸을 배치
    static void set(int i) {
        for (int j = 0; j < 8; j++) {
            pos[i] = j; //퀸을 j행에 배치
            if (i == 7) {  //모든 열에 배치 완료
                print();
            } else {
                set(i + 1); //다음 열에 퀸을 배치
            }
        }
    }

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

분기 한정법 - 규칙 2(각 행에 퀸 1개만 배치) 만족하기

• 한정 조작 : 불필요한 분기를 제거하여 불필요한 조합 수를 줄이는 것.
• 분기 한정법 : 가지 뻗기와 한정 조작을 조합하여 문제를 풀어나가는 방법
• 같은 행에 퀸이 중복 배치되는 것을 방지하기 위해 flag 배열을 사용하여 체크한다.

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

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

    //i열에 퀸을 배치
    static void set(int i) {
        for (int j = 0; j < 8; j++) {
            if (!flag[j]) { //j 행에 배치된 퀸이 없다면,
                pos[i] = j; //퀸을 j행에 배치
                if (i == 7) {  //모든 열에 배치 완료
                    print();
                } else {
                    flag[j] = true;
                    set(i + 1); //다음 열에 퀸을 배치
                    flag[j] = false;
                }
            }

        }
    }

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

8퀸 문제를 해결하는 프로그램

지금까지 각 퀸이 행과 열에 중복되지 않도록 배치하는 조합을 구했습니다. 하지만 퀸은 대각석으로도 이동할 수 있기 때문에 마지막으로 각 대각선에도 퀸이 중복되지 않도록 배치하는 한정 조작을 추가해야 합니다.

public class Queen {
    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.print(pos[i] + " ");
        }
        System.out.println();
    }

    //i열에 퀸을 배치
    static void set(int i) {
        for (int j = 0; j < 8; j++) {
            // / 방향 대각선을 체크하는 배열의 인덱스는 i + j
            // \ 방향 대각선을 체크하는 배열의 인덱스는 i - j + 7
            if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) { //j 행에 배치된 퀸이 없다면,
                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);
    }
}

코드를 실행해보면 8퀸 문제를 만족하는 92개의 조합이 출력되는 것을 볼 수 있습니다.

참고

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편