이 문제도 하노이의 탑과 비슷하게 작은 문제로 나누어 해결하는 문제다.
8퀸 문제란? 8퀸 문제는 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장하고 프리드리히 가우스가 잘못된 해답을 내놓은 문제로도 잘 알려져 있다.
서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓는다.
참고로 퀸은 가로 세로 대각선으로 직선이동만 가능하다.
이 문제의 답이 될 수 있는 조합은 92가지가 있다.
체스판의 가로줄을 행, 세로줄을 열이라고 하고 배열 인덱스에 맞추어 행과 열에 0~7의 번호를 부여한다.
8개의 퀸을 배치하는 조합은 모두 66 x 65 x 64 x 63... x 57 로 총 178,462,987,637,760개가 존재한다.
이 큰 경우의 수를 모두 나열하고 각각의 조합이 8퀸 문제를 만족하는지 조사하는 것은 현실적이지 않기에 조건을 몇 개 추가해 보자,
rule1. 각 열에 퀸을 1개만 배치한다.
어차피 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있기에 가능하다.
이렇게 하면 퀸을 배치하는 조합의 수는 17,777,216가지가 된다. 하지만 여전히 그 수는 지나치게 많다.
또 열뿐만 아니라 행도 1개만 배치해야 한다.
rule2. 각 행에 퀸을 1개만 배치한다.
이렇게 하면 가능한 조합의 개수는 더욱 줄어들게 된다.
분기 조작
분기란 가지가 뻗어 나가듯이 문제를 나누어 푸는 과정을 의미한다.
분기하며 모든 조합을 나열하는 프로그램을 만들어 보자.
정수형 배열 pos[8]을 만든 후, 해당 배열을 이용해서 모든 경우의 수를 체크해 보자.
pos[0 ~ 7]은 열을 나타낸다. pos[0] = 4 라면 0열 4행에 퀸을 두겠다는 소리이다.
이때 set 메서드는 pos[i]에 0부터 7까지의 값을 순서대로 대입하여 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀 메서드'이다. 매개변수 i가 이 퀸을 배치할 열이된다. 이 메서드는 main메서드에서 처음 호출된다.
호출된 set 메서드는 i에 0을 전달받기에 0열에 퀸 1개를 배치하는 모든 경우의 수를 얻는다. 이 대입에서 0열이 확정되고 다음으로 1열을 확정해야 한다. 그래서 다음과 같이 재귀 호출을 하게 된다.
set(i + 1); // 다음 열 퀸을 배치위 메서드로 인해 앞에서 했던 작업을 다음 열인 1열에 대해 수행하게 된다.
public class EightQueenB {
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++) {
pos[i] = j; // 퀸을 j행에 배치
if (i == 7) // 모든 열에 배치
print();
else
set(i + 1); // 다음 열에 퀸을 배치
}
}
public static void main(String[] args) {
set(0);
}
}위 코드를 실행하게 되면 16,777,216개의 조합을 모두 나열하게 된다. (7분 걸렸다)
이런식으로 분기하며 퀸을 배치하는 조합을 모두 나열해 봤다. 이런 방법을 분기 조작 또는 가지 뻗기(branching)라고 한다. 하노이의 탕비나, 8퀸처럼 문제를 작게 나누고 세분화된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 정복법(divide and conquer method)라고 한다. 물론 문제를 작게 나눌 떄는 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출될 수 있도록 지향 설계 해야 한다.
※퀵 정렬과 병합 정렬도 분할 정복 알고리즘 중 하나이다.
분기 한정법
분기 조작으로 퀸을 배치하는 조합을 나열할 수 있겠지만 8퀸 문제의 답은 아니다. 따라서 조건을 추가 해 보자.
rule2. 각 행에 퀸을 1개만 배치한다.
위에서 정의한 2번째 룰이다.
public class EightQueenBB {
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);
}
}규칙을 추가한 코드이다. flag라는 배열을 이용하고, flag는 같은 행에 중복하여 퀸이 배치되는 것을 방지하기 위한 표시이다. j행에 퀸을 배치하면 flag[j]의 값을 true로 하고, 배치되지 않은 상태값은 false로 한다.
set(0)을 먼저 실행하면 flag[0]의 값은 false이기에 0행에 퀸이 하나 배치된다. 그럼 flag[0] = true로 바뀌고, 그런다음 set 메서드를 재귀적으로 호출하기에 다시 돌아올 때 까지 0행에 퀸이 배치되는 일은 없게 된다.
만약 set메서드를 끝내고 돌아오는 메서드가 있다면 flag[x] = false로 고쳐주고 그 다음 행으로 for문에 의해 넘어가게 된다.
이처럼 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정(bounding) 조작이라 하고, 분기 조작과 한정 조작을 조합하여 문제를 풀어나가는 방법을 분기 한정법(branching and bounding method)라 칭한다.
위 코드는 같은 열/행에 2개 이상의 퀸을 배치하지 않게 된다. (pos[x] = y에는 무조건 한 개의 값만 들어갈 수 있으니 열에 대해서는 따로 처리를 할 필요가 없다)
하지만 8퀸 문제를 해결했다고 볼 수는 없다. 동서남북으로 직선움직임을 가지는 유닛은 퀸이아니라 룩(rook)이기 때문이다.
퀸은 대각선 방향으로도 이동할 수 있기에 어떤 대각선에서 보더라도 쿠니을 1개만 배치하는 한정조작을 추가해야 한다.
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]; // 각 열에 있는 퀸의 위치(같은 열에 퀸 배치x)
static int count = 0; // 총 몇개?
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;
if (i == 7) {
print();
count++;
}
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("총 " + count + "개의 경우가 있습니다.");
}
}flag_b와 flag_c는 퀸의 대각선 방향 2줄을 체크하기 위한 boolean형 배열이다.
flag_b(↗↙)는 i + j로 어느 대각선 줄에 속하는지 알 수 있다.
0행 0열은 0번 대각선에 포함된다.
0행 1열과 1행 0열은 같은 1번 대각선에 포함된다.
0행 2열과 1행 1열, 2행 0열은 같은 2번 대각선에 포함된다.
flag_c(↖↘)는 i - j + 7로 어느 대각선 줄에 속하는지 알 수 있다.
7행 0열은 0번 대각선에 포함된다.
6행 0열과 7행 1열은 같은 1번 대각선에 포함된다.
5행 0열과 6행 1열, 7행 2열은 같은 2번 대각선에 포함된다.
flag_a,b,c중 하나라도 true라면 동서남북 대각선 중 한 군데에 다른 퀸이 존재한다는 의미로써 해당 경우의 수는 생각할 필요가 없다. (한정 조작)
이렇게 퀸 문제를 풀 수 있다. 총 경우의 수는 92가지이다.
