Algorithm - 8퀸 문제

8퀸 문제란?
서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓는 경우의 수를 찾는 문제

• 체스판에서 퀸은 현재 놓여있는 지점에서 가로*세로*대각선 8가지의 방향으로 직선 이동을 할 수 있다.

언뜻 보면 매우 쉬워보인다.

 

체스판의 가로줄을 행, 세로줄을 열이라고 하고 배열 인덱스에 맞추어 행과 열에 0~7 번호를 부여 한다.

 

퀸 배치하기

STEP1
8개의 퀸을 배치하는 조합은 8x8 총 64칸의 칸이 있다. 
첫번째 퀸을 아무곳이나 배치하고 두번째 퀸을 배치할 땐 63 ..이러한 형식으로
64x63x62x61x60x59x58x57 = 178,462,987,637,760 가지이다.

그러나 이 조합을 모두 나열하기엔 현실상 불가능 하고 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있다.

STEP2
각 열에 퀸을 1개만 배치할 것
이렇게 하면 8x8x8x8x8x8x8x8 = 16,777,216 가지이다.

많이 줄었지만 이 또한 불가능할 것이다.

이 경우 역시 같은 열에 있는 다른 퀸을 공격할 수 있기 때문이다.

STEP3
각 행에 퀸을 한개만 배치한다

이렇게 하면 어떻게든 알고리즘을 만들 수 있다. 하지만 간단하지 않을 것이다.

 

분기 조작

배열 pos는 퀸의 배치를 나타낸다. i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 한다.

예를 들어 pos[0]의 값이 0이면 '0열의 퀸이 0행에 배치된 상태'를 의미한다.

이 때 set 메소드는 pos[i]에 0부터 7까지의 값을 순서대로 대입하여

'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀 메소드'이다.

매개변수 i가 이 퀸을 배치할 열이다.

호출된 set메소드는 매개변수 i에 0을 전달받기 때문에 0열에 퀸 1개를 배치하게 된다.

for문에 의한 반복을 통해 j값을 0->7까지 증가시키며 pos[i]에 j를 대입하는 것으로 퀸을 j행에 배치한다. 

이 대입에서 0열이 확정되고 다음으로 1열을 확정해야 한다.

그렇기에 다음과 같은 set(i+1) 재귀 호출을 한다.

public class queen {
    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){ //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);
    }
}

해당 코드이다. 재귀호출을 거듭 반복하면 결국 i가 7이 되고 8개의 퀸이 모두 배치된다.

그러면 퀸은 더이상 배치할 필요가 없어지기에 print메소드를 호출하여 퀸이 배치된 위치를 출력한다

출력하는 값은 배열 pos의 요솟값이며 이렇게 분기하며 퀸을 배치하는 조합을 모두 나열 했다.

 

이러한 방법을 분기 조작 혹은 가지 뻗기(branching)라고 한다.

하노이 탑 혹은 8퀸 문제처럼 문제를 작게 나누고 세분화하여 그 풀이들을 결합해 전체 문제를 푸는 기법을 분할 정복법이라고 한다.

 

분기 한정법

아까 STEP2 "각 행에 퀸을 1개만 배치한다" 조건을 적용하여 살펴보자

public class queen {
    static int[] pos = new int[8]; //각 행에 퀸을 이미 배치했는지 체크
    static boolean[] flag = new boolean[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){ //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);
    }
}

해당 코드는 flag라는 bool형 배열을 사용한다.

flag는 같은 행에 중복하여 퀸이 배치되는 것을 방지하기 위한 표시이며 j행에 퀸을 배치하면 flag[j]값을 true로 하고,

배치 되지 않은 상태값은 false로 한다.

0열에 퀸을 배치하기 위해 호출한 set메소드는 먼저 0행에 퀸을 배치한다. 단 이때 flag[0]의 값은 false이다.

0행에 퀸을 배치하였기 때문에 flag[0]의 값을 true로 변경한다.

그 후 set메소드를 재귀적 호출을 통해 퀸을 계속 배치한다.

 

195