재귀(4) - 8-Queen problem

8-Queen problem

8-Queen problem이란 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장한다.
19세기 유명한 수학자 카를 프리드리히 가우스가 잘못 된 해답을 내놓은 것으로도 잘 알려져있다고 한다.

해당 문제는 8 X 8 체스판에 8개의 퀸을 서로가 공격할 수 없도록 배치하는 문제로 92가지가 있다고 한다.
추가적으로 체스에서 퀸은 가로,세로,대각선 방향으로 공격이 가능하다.

---

분기 조작

분기란 가지가 뻗어 나가듯이 문제를 나누어 푸는 과정을 의미합니다.
총 가지수로 봤을 경우 각 퀸은 미리 놓인 자리를 제외한 모든 자리에 놓일 수 있기에  
64 * 63 * 62 ... = 178 =178,462,987,637,760의 경우가 있습니다.

이와같은 경우를 구하기 위해서 각 행 또는 열마다 배치될 수 있는 경우를 전체 문제를 해결하기 위해 작은 문제단위로 풀어가는 것(각각의 경우)을 '분기 조작'또는 '가지 뻗기' 라고하며, 작은 문제의 풀이를 결합해 전체문제를 풀이하는 기법을 '분할 정복법'이라 합니다.

---

  static int[] pos = new int[8];
  
  static void print(){
        result++;
        for(int i = 0 ; i < 8 ; i++)
            System.out.printf("%2d",pos[i]);
        System.out.println();
    }
    
 //모든 경우(178,462,987,637,760가지)
    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);
        System.out.println(result);
    }

 

해당 코드는 8 퀸이 놓일 수 있는 모든 경우의 수를 구할 수 있습니다. 배열(pos)을 통하여 각 열 몇 번째 행에 퀸이 놓여 있는지를 저장합니다. 예를 들어 0번째 열에 7번행에 퀸이 놓일 경우 pos[0] = 7을 저장합니다. 그리고 재귀 호출을 통하여 경우의 수를 구하면 처음은 [0 0 0 0 0 0 0 0]로 모두 0번 행에 각 열에 위치하며, 마지막 열부터 하여 가능한 경우의 수들을 모두 구하며 앞쪽 열로 이동하게 됩니다. 재귀 함수를 이용하였으나, 쉽게 생각하면 다중 반복을 수행하는 것과 같습니다.

---

분기 한정법

분기를 통하여 문제를 풀어나갈 때, 불필요한 분기를 제거하여 조합을 줄이는 방법을 한정 조작이라하며, 분기조작과 한정조작을 함께 조합하여 문제를 풀어가는 방법을 '분기 한정법'이라 합니다.

---

static boolean[] flag = new boolean[8]; //행 중복확인
static int[] pos = new int[8];

	static void print(){
        result++;
        for(int i = 0 ; i < 8 ; i++)
            System.out.printf("%2d",pos[i]);
        System.out.println();
	}
    
  // 같은 행 중복 배치를 제거(40,320가지)
    static void set(int i){
        for(int j = 0 ; j < 8 ; j++){
            if(flag[j] == false){
                pos[i] = j;
                if(i == 7){
                    print();
                }
                else{
                    flag[j] = true;                   
                    set(i + 1);
                    flag[j] = false;
                }

            }
        }
    }

 

8퀸 문제에서는 같은 행에 퀸을 배치한 경우는 제외시킬 수 있다. 같은 행에 퀸이 배치되어있을 경우 서로 공격을 할 수 있게 된다. 이를 위하여 0~7까지 8개의 행에 배치된 퀸이 있는지를 확인하기 위해 배열(flag)를 통하여 퀸이 배치될 경우 현재 행에 배치여부를 변경시키고, 해당 행에 배치되어 있는 경우는 한정(제외) 시키면서 경우의 수를 찾는다. 이렇게 될 경우 각 열에 대해서 반복문을 돌면서 현재 행에 퀸이 배치되어있는지를 확인하고 없을 경우 위치시키게 된다. 그리고 마지막으로 다음 경우를 위해서 현재 각 열에 해당 행 배치여부(flag)에 대해서는 초기화를 해준다. 모든 경우를 구할 경우는 경우의 수를 출력하기 위해서는 시간이 많이 걸리지만 이렇게 한정적으로 제어를 해줄 경우 경우의 수가 현저하게 줄어들게 된다.

 

---

8-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 int result = 0;

    static void print(){
        result++;
        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_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);
        System.out.println("\n[경우의 수] : " + result);
    }

 

기존에 코드에서 ① (↗↙) , ②(↖↘)대각선 방향에 배치여부를 확인하기 위한 2개의 배열을 추가했다. 그리고 (0,0) ~ (7,7)까지 각각의 좌표의 합은 0 ~ 14안에 포함된다.

각각의 대각선 방향에 대해서는 간단하게 생각해 볼 수 있다. ①방향으로 볼 때는 대각선 위치에 있는 모든 좌표상 두 좌표의 합은 동일하다.

예를 들어)

(0,0) : 0 

(0,1) , (1,0) : 1

(0,2) , (1,1) , (2,0) : 2 

이런식으로 ① 방향 대각선 배치는 위와 같이 된다. 그렇기에 이미 배치된 퀸에 대해서 대각선 방향에 놓일 경우 해당 위치는 이미 true이기에 놓일 수 없게 되어 경우에서 제외된다.

 

다음으로 ②경우는 i - j + 7에 같이 같은 곳은 대각선 위치가 된다. 이 경우는 아래 첨부된 이미지를 통해서 확인해볼 수 있다. 최종적으로 8퀸이 서로 공격하지 않도록 배치할 수 있는 경우는 92가지라는 것을 확인했다.