8퀸 문제란?
서로 공격하여 잡을 수 없도록 8개의 퀸을 8 * 8 체스판에 놓으세요.
퀸은 가로, 세로, 대각선방향으로 체스판 끝까지 움직일 수 있습니다.
8개의 퀸을 놓는 조합은 모두 체스판은 총 64개 이므로 646362...321으로 매우 많은 조합이 나옵니다. 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로 아래와 같은 규칙을 세울수 있습니다.
규칙1. 각 열에 퀸을 1개만 배치한다.
조합의 수는 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 입니다. 여전히 엄청나게 많습니다.
규칙2. 각 행에 퀸을 1개만 배치한다.
Branching(가지 뻗기)
가지를 뻗으며 모든 조합을 나열하는 프로그램입니다.
밑의 그림과 코드는 규칙1을 적용하여 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다. 이처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 divide and conquer(분할 해결법)이라고 합니다.
배열 pos는 퀸의 배치를 나타냅니다. i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 합니다. 그림과 같이 pos[6]의 값이 1이면, 6열 1행에 퀸이 배치된것입니다. set 함수는 pos[i]에 0부터 7까지의 값을 순서대로 대입하여 i열에 퀸을 하나만 배치하는 8가지 조합을 만드는 재귀함수입니다. 즉, 재귀함수로 열 마다 8가지 조합을 만들어 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 조합이 나옵니다.
#include <stdio.h>
int pos[8]; /* 각 열에서 퀸의 위치 */
/*--- 각 열의 퀸의 위치를 출력 ---*/
void print(void)
{
int i;
for (i = 0; i < 8; i++)
printf("%2d", pos[i]); // 모든 열 출력
putchar('\n');
}
/*--- i열에 퀸을 배치 ---*/
void set(int i) // branching(가지 뻗기)
{
// i : 열, j : 행
int j;
for (j = 0; j < 8; j++) { // 8행 까지
pos[i] = j; // 퀸 i열 j행에 배치
if (i == 7)// 모든 열에 배치를 마침
print();
else
set(i + 1); // 다음 열
}
}
int main(void)
{
set(0); // 0열부터 배치
return 0;
}- 출력결과
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 3
.....
0 0 0 0 0 0 0 7
0 0 0 0 0 0 1 0
.....
7 7 7 7 7 7 7 6
7 7 7 7 7 7 7 7
set(0) : 0열에 1개의 퀸을 배치하는 8가지 조합을 for문에 의해 나열합니다.
set(i + 1) : 앞에서 했던 작읍을 다음 열에서 수행합니다. 이렇게 재귀 호출을 반복하다가 i가 7이 되면 8개의 퀸이 모두 배치됩니다. 그러면 퀸을 더 배치할 필요가 없으므로 print 함수를 호출하여 퀸이 배치된 위치를 출력합니다. 출력값은 pos 배열의 요솟값이며 열별로 출력됩니다. 7열 까지 배치 이후 출력하고 다시 재귀 호출했던 set(i + 1) 함수가 존재하는 for문으로 돌아옵니다. for문의 j행이 1씩 증가하면서 다시 조건식을 만나게 되고 실행이 완료될때까지 반복됩니다.
분기 한정법
이번엔 위의 Branching로 규칙1을 적용한 후 각 행에 퀸을 1개만 배치하는 규칙2까지 적용해봅시다. 분기를 한정하기 위해 정했던 규칙입니다.
/* 각 행, 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다. */
#include <stdio.h>
int flag[8]; /* 각 행에 퀸을 배치했는지 체크하는 배열 */
int pos[8]; /* 각 열에서 퀸의 위치 */
/*--- 각 열에서 퀸의 위치를 출력 ---*/
void print(void)
{
int i;
for (i = 0; i < 8; i++)
printf("%2d", pos[i]);
putchar('\n');
}
/*--- i열에서 알맞은 위치에 퀸을 배치합니다. ---*/
void set(int i)
{
int j;
for (j = 0; j < 8; j++) { // 8행 까지
if (!flag[j]) { // 같은 행에 배치된 퀸이 없을때
pos[i] = j; // i열 j행 퀸 배치
if (i == 7) // 모든 열에 배치 완료
print(); // 출력
else {
flag[j] = 1; // 배치된 퀸중에 같은 행있는지 표시
set(i + 1); // 다음열 조합
flag[j] = 0; // 재귀 호출 끝나면 퀸을 j행에서 제거
}
}
}
}
int main(void)
{
int i;
for (i = 0; i < 8; i++) // 각 행 초기화
flag[i] = 0;
set(0);
return 0;
}- 출력결과
0 1 2 3 4 5 6 7
0 1 2 3 4 5 7 6
0 1 2 3 4 6 5 7
0 1 2 3 4 6 7 5
......
7 6 5 4 3 2 1 0
flag 배열을 사용하여 같은 행에 중복하여 퀸이 배치된 경우에 표시를 하여 불필요한 조합을 줄이는 방법입니다. j행에 퀸을 배치하면 flag[j]의 값을 1로 해주고, 배치 되지 않은 상태의 값은 0으로 합니다. 그런 다음 set 함수를 재귀적으로 호출하여 다음 열에 퀸을 배치합니다. 또 재귀 호출한 set(i + 1) 함수가 끝나면 퀸을 j행에서 제거했기 때문에 flag[j]에 아직 배치 하지 않았음을 나타내는 0을 대입합니다. 그리고 실행이 완료될떄까지 for문을 돌아줍니다.
이처럼 필요하지 않은 분기를 없애 불피욜한 조합을 줄이를 방법을 bounding(한정 조작)이라고 하고, branching(가지 치기)와 bounding(한정 조작)을 합쳐 branching and bounding method(분기 한정법)이라고 합니다.
8퀸 문제
바로 위의 문제는 각 행, 열에 대해 공격이 불가능한 8룩이라고 보면된다.
8퀸 문제는 대각선까지 고려해야 한다. 대각선은 그림과 같이 두 방향이 있으며
대각선의 개수는 15개로 대각선에 배치 검사에 해당하는 flag 배열의 크기는 15개로 잡아주면 된다.
/* 8퀸 문제 풀이 */
#include <stdio.h>
int flag_a[8]; /* 각 행에 퀸을 배치했는지 체크하는 배열 */
int flag_b[15]; /* 대각선 ↙에 퀸을 배치했는지 체크하는 배열 */
int flag_c[15]; /* 대각선 ↘에 퀸을 배치했는지 체크하는 배열 */
int pos[8]; /* 각 열에서 퀸의 위치 */
int cnt = 0;
/*--- 각 열에서 퀸의 위치를 출력 ---*/
void print(void)
{
int i;
for (i = 0; i < 8; i++)
printf("%2d", pos[i]);
cnt++;
putchar('\n');
}
/*--- i열에서 알맞은 위치에 퀸을 배치 ---*/
void set(int i)
{
int j;
for (j = 0; j < 8; j++) { // 8행
if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) { // 행, 대각선↙, 대각선↘
pos[i] = j; // i열 j행 퀸 배치
if (i == 7) // 모든 열 배치 완료
print();
else {
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 1;
set(i + 1);
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 0;
}
}
}
}
int main(void)
{
int i;
for(i=0;i<8;i++)
flag_a[i] = 0;
for (i = 0; i < 15; i++)
flag_b[i] = flag_c[i] = 0;
set(0);
printf("경우의 수 %d", cnt);
return 0;
}위 그림에서 보는 것과 같이 i열 j행에서 각각의 대각선 방향에 대해 퀸이 배치되었는지 확인하는 배열의 인덱스는 flag_a[i + j]와 flag_b[i - j + 7]이다. 각 칸에 퀸의 배치를 체크할때 같은 행에 퀸을 배치했는지 그리고 두 가지의 대각선에 퀸을 배치했는지 검사한다. 어느 방향이든 한개라도 배치되었다면 그 자리에는 퀸을 놓으면 안된다.
- 출력 결과
0 4 7 5 2 6 1 3
0 5 7 2 6 3 1 4
0 6 3 5 7 1 4 2
.......
7 1 4 2 0 6 3 5
7 2 0 5 1 4 6 3
7 3 0 2 5 1 6 4
경우의 수 92
