8퀸 문제

• 재귀 알고리즘에 대한 예제로 자주 등장하며 문제는 아래와 같다.

서로 공격하여 잡을 수 없도록 8개의 퀸를 8 x 8 체스판에 놓으세요.
(퀸은 서 있는 지점에서 체스판으로 어떤 지점으로든 여덟 방향으로 직선 이동이 가능하다.)

• 퀸을 배치하기 위해 다음과 같은 규칙을 세울 수 있다.
  • [규칙 1] : 각 열에 퀸을 1개만 배치한다. → 가지 뻗기로 퀸을 배치하는 조합을 나열
  • [규칙 2] : 각 행에 퀸을 1개만 배치한다. → 분기를 한정하기
• 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정(bounding) 조작이라고 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법을 분기 한정법(branching and bounding method)이라고 한다.

//8퀸 문제 풀이
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() {
        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_a[j] == false &&            //가로(j행)에 아직 배치하지 않았습니다.
                flag_b[i + j] == false &&        //대각선 ／에 아직 배치하지 않았습니다.
                flag_c[i - j + 7] == false) {    // 대각선 ＼에 아직 배치하지 않았습니다.
                
                pos[i] = j;                     //퀸을 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);
    }
}