#13. 4주차 과제 3 [Chap05_5-7 ~ 5-9]

5-6에 이은 8퀸 문제 해석 과정...

 

5-7. (QueenB) _ 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열.

 

package practice;
 
public class QueenB_5_7 {
 
    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: 행  ,  j: 열*/
 
    for (int j = 0; j < 8; j++) {
 
    pos[i] = j; //퀸을 j행에 배치
 
    if(i==7) print(); //모든열에 배치가 되었니?
    else set(i+1); //아니면 1증가하고 set 다시 호출
    }
    }
 
    public static void main(String[] args) {
    //시작시 0열에 퀸을 배치하겠다.
    set(0);
    }
 
}
 

---

5-8. (QueenBB) _ 각 행, 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열.

 

package practice;
 
public class QueenBB_5_8 {
    
    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();    
    }
    
    //열의 알맞은 위치에 퀸을 배치한다.
    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;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);
    }
}
 
 

---

5-9. (QueenBB) _ 위 2과정을 토대로 8퀸 문제 풀이

 

package practice;
 
public class EightQueen_5_9 {
     //각 행에 퀸을 배치했는지 체크
    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 cnt=0;
    static int printCnt=0;
 
 
    //----------------------------------
    static void print() {
        printCnt++;
        for (int i = 0; i < 8; i++) {
            System.out.printf("%2d", pos[i]);
        }
        System.out.println("---------------------"+printCnt);
    }
 
 
    //----------------------------------------------    
    static void set(int i) {
        cnt++;
        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총 "+cnt+"번 연산!!");
        System.out.println("총 "+printCnt+"개의 경우가 있음!!");
    }
 
}
 
 

---