5-4. 8퀸 문제(Eight Queens Problem)

8퀸 문제란?

• 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장
• 19세기 유명한 수학자 카를 프리드리히 가우스(C. F. Gauss)가 잘못된 해답을 낸 사실로도 잘 알려진 문제

서로 공격해 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.

 

*퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능

 

 

 

 

92가지 조합의 정답 중 한 방법

 

 

 

 

 

퀸 배치하기

8개의 퀸을 배치하는 조합은 

64 x 63 x 62 x 61 x 60 x 59 x 58 x 57 x = 178,462,987,637,760 가지

 

 

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

8 x 8 x 8 x 8 x 8 x 8 x 8 x 8 = 16,777,216 가지

 

 

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

 

-> 경우의 수는 더욱 감소

 

 

 

 

 

가지 뻗기(Branching)

: 가지를 뻗으며 모든 조합을 나열하는 프로그램 만들기

 

 

pos[i] = j

• i열의 퀸이 j행에 배치된 상태
• 이때 set 메서드는 pos[i]에 0부터 7까지의 값을 순서대로 대입해 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀 메서드'
• set 메서드는 가장 먼저 main 메서드에서 다음과 같이 호출

set(0);

 

• 호출된 set 메서드는 매개변수 i에 0을 전달받고, 0열에 1개의 퀸을 배치하는 8가지 조합을 for문에 의해 나열
• j값을 0부터 7까지 1씩 증가하며 다음과 같이 재귀 호출

set(i + 1);

 

• set(i + 1)에 의해 앞에서 했던 작업을 다음 열인 1열에서 다시 수행
• i가 7이 되면 9개의 퀸이 모두 배치, print 메서드를 호출해 퀸이 배치된 위치를 출력(pos의 배열 요솟값)
• 이렇게 프로그램을 실행하면 총 16,777,216개의 모든 조합이 나열

 

 

 

[실습 코드]

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++) {
            pos[i] = j;
            if(i == 7)
                print();
            else
                set(i + 1);
        }
    }
    
    public static void main(String[] args) {
        set(0);
    }

 

하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 분할 정복법(divide and conquer)이라고 한다.

 

 

 

 

 

분기 한정법

가지 뻗기로 8퀸 문제의 답을 얻을 수는 없다. 아래의 개념을 추가로 적용한다.

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

 

 

 

[실습 코드]

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;
                }

 

 

 

 

 

8퀸 문제를 푸는 프로그램

퀸은 대각선 방향으로도 이동하기 때문에 어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정 조작을 추가해야 한다.

 

 

 

[실습 코드]

//i열의 알맞은 위치에 퀸을 배치
    static void set(int i) {
        for(int j = 0; j < 8; j++) {
            if(flag_a[i] == 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;
                }