8퀸 문제란?


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


퀸 배치하기


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

체스판은 64칸(8x8)이므로 처음에 퀸을 1개 배치할 떄는 64칸 중 아무 곳이나 선택할 수 있다.

다음 퀸을 배치할 때는 나머지 63칸에서 임의로 선택한다.


마찬가지로 8번째까지 생각하면 다음과 같이


64x63x62x61x60x59x58x57 = 178,462,987,637,760 가지 조합이 만들어짐.


8퀸문제의 조건을 만족하는지 조사 불가..


퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로 아래와 같은 규칙을 세울수 있다.


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


퀸을 배치하는 조합의 수는 많이 줄어든다.

8*8*8*8*8*8*8*8 = 16,777,216 이다.


같은행에 퀸이 2개 이상 배치되면 안된다.


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


이렇게 하면 조합의 개수가 줄어든다.



1. 가지뻗기를 하며 재귀적으로 각 열에 1개의 퀸을 배치하는 조합을 나열


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package myTest2;
 
public class QuuenB {
    // 가지뻗기
    // 규칙 1. 각 열에 퀸을 1개만 배치한다.
    // 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열
    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[0] = 0
            pos[i] = j;        // 퀸을 j행에 배치한다.
            if(i==7){        // 모든 열에 배치한다.
                print();
            }else{
                set(i+1);    // 다음 열에 퀸을 배치한다.
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);        // 0열에 퀸을 배치한다.
    }
}
cs



결과



가장 마지막에 7 7 7 7 7 7 7 7 모든 퀸이 7행에 배치된 것을 확인할 수 있다.



2. 분기한정법을 사용하여 각 행, 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열


가지뻗기로 퀸을 배치하는 조합을 나열할 수 있지만 8퀸 문제 답을 얻을 수 없다.


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


규칙 2를 적용해 다시 구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package myTest2;
 
public class QuuenBB {
    // 분기 한정법
    // 규칙 1. 각 열에 퀸을 1개만 배치한다.
    // 규칙 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;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);        // 0열에 퀸을 배치한다.
    }
}
cs



결과



flag를 사용하여 같은행에 중복하여 퀸이 배치되는 것을 방지한다.

j행에 퀸을 배치하면 true 배치되지 않는 다면 false이다.


3. 8퀸 문제 구현


퀸이 행방향과 열방향으로 서로 겹치지지 않는 조합을 나열했지만

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package myTest2;
 
public class 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(){
        StringBuilder oneLine0 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine1 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine2 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine3 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine4 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine5 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine6 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine7 = new StringBuilder("□□□□□□□□");
        
        for(int i=0; i<8; i++){
            
            System.out.printf("%2d", pos[i]);
            int value1 = pos[i]; // 4 
            if(value1 == 0){
                oneLine0.setCharAt(i, '■');
            }else if(value1 == 1){
                oneLine1.setCharAt(i, '■');
            }else if(value1 == 2){
                oneLine2.setCharAt(i, '■');
            }else if(value1 == 3){
                oneLine3.setCharAt(i, '■');
            }else if(value1 == 4){
                oneLine4.setCharAt(i, '■');
            }else if(value1 == 5){
                oneLine5.setCharAt(i, '■');
            }else if(value1 == 6){
                oneLine6.setCharAt(i, '■');
            }else if(value1 == 7){
                oneLine7.setCharAt(i, '■');
            }
        }
        System.out.println();
        String whole = oneLine0 +"\n" + oneLine1 +"\n" + 
                               oneLine2 +"\n" + oneLine3 +"\n" + 
                               oneLine4 +"\n" + oneLine5 +"\n" + 
                               oneLine6 +"\n" + oneLine7 +"\n"
        System.out.println(whole);
        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;
                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);
    }
}
cs



결과



flag_b, flag_c 로 방향대각선을 체크하는 배열로 

각각의 대각선 방향에 대해 퀸이 배치되었을 때 체크 하는 배열 인덱스는 flag_b[ i+j ] flag_c[ i-j+7 ] 이다.



소스코드 첨부


myTest1.zip






+ Recent posts