Chapter 05-4. 재귀 알고리즘_8퀸 문제

8퀸 문제(8-Queen problem)

서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓기

퀸은 현재 놓여 있는 지점에서 가로, 세로, 대각선의 8가지 방향으로 직선 이동 가능

퀸 배치하기 조건(대각선 규칙 제외)

• 각 열에 퀸을 1개만 배치 - 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로
• 각 행에 퀸을 1개만 배치 - 자신과 같은 행에 있는 다른 퀸을 공격할 수 있으므로

 

분기 조작, 가지 뻗기(branching)

가지가 뻗어 나가듯 문제를 나누어 푸는 과정

먼저 모든 조합을 나열하는 코드 작성

 

각 열에 퀸 1개를 배치하는 조합을 재귀적으로 나열

package ch05_4;

// 각 열에 퀸 1개를 배치하는 조합을 재귀적으로 나열
public class Ex01_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열에 퀸 배치 - i는 열, j는 행
    static void set(int i) {
        for (int j = 0; j < 8; j++) {
            pos[i] = j; // 퀸을 j행에 배치
            if (i == 7) { // 모든 열에 배치
                print();
            }
        }
    }

    public static void main(String[] args) {
        set(0); // 0열에 퀸 배치
    }
}

 

분할 정복법(divide and conquer method)

문제를 작게 나누고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법

 

한정(bounding)

앞에서 분기를 한정하기 위해 정했던 규칙 적용하는 것과 같이 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법

 

분기 한정법(branching and bounding method)

분기 조작과 한정 조작을 조합하여 문제를 풀어 가는 방법

 

각 행과 열에 퀸 1개를 배치하는 조합을 재귀적으로 나열

package ch05_4;

// 각 행과 열에 퀸 1개를 배치하는 조합을 재귀적으로 나열
public class Ex02_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();
    }

    // i열의 알맞은 위치에 퀸을 배치
    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; // 해당 행 배치 표시
                    set(i + 1);
                    flag[j] = false; // 재귀호출 후 해당 행 배치 제거
                }
            }
        }
    }

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

 

8퀸 문제 풀이

package ch05_4;

// 8퀸 문제 풀이
public class Ex03_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 && // 가로(j)에 아직 배치하지 않음
                    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);
    }
}

 

8퀸 문제 풀이(배치 상황을 □와 ■으로 출력)

package ch05_4;

// 8퀸 문제 풀이(배치 상황을 □와 ■으로 출력)
public class Ex04_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 && // 가로(j)에 아직 배치하지 않음
                    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);
    }
}

 

8퀸 문제 비재귀적 풀이(배치 상황을 □와 ■으로 출력)

package ch05_4;

// 8퀸 문제 비재귀적 풀이(배치 상황을 □와 ■으로 출력)
public class Ex05_eightQueenN {
    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) {
        int j;
        int[] jStk = new int[8];

        Start : while(true) {
            j = 0;
            while (true) {
                while (j < 8) {
                    if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) {
                        pos[i] = j; // 가로, /대각선, \\대각선에 배치되지 않았을 경우 해당 위치에 배치
                        if (i == 7) {
                            print(); // 모든 열 배치 완료하면 출력
                        } else {
                            flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
                            jStk[i++] = j; // i열의 행을 push
                            continue Start; // Start 부분부터 실행
                        }
                    }
                    j++; // if문 조건에 걸리지 않았을 경우(가로, 대각선에 배치되어 있을 경우) j증가
                }
                // 모든 열 배치 완료 후 j가 8이되면 while문 빠져나와 아래 실행 - 배치판단 초기화
                if(--i == -1) return;
                j = jStk[i]; // i열의 행을 pop
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
                j++; // if문 flag 판단 위해 증가 - 모든 가로, 대각선 초기화 될때까지
            }
        }
        
        /*for (int j = 0; j < 8; j++) {
            if (flag_a[j] == false && // 가로(j)에 아직 배치하지 않음
                    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);
    }
}