8퀸 문제란?

1. 각 행에 하나의 퀸
2. 각 열에 하나의 퀸
3. 대각선에 하나의 퀸

---

체스판은 64칸이므로(8x8) 총 조합의 가지 수는?

64 X 63 X 62 X 61 X 60 X 59 X 58 X 57

[규칙1] 각 열에 퀸을 1개만 배치

[규칙2] 각 행에 퀸을 1개만 배치

---

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

/* 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다. */
#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)
{
	int j;
	for (j = 0; j < 8; j++) {
		pos[i] = j;
		if (i == 7) 		/* 모든 열에 배치되었다면 */
			print();
		else
			set(i + 1);
	}
}
int main(void)
{
	set(0);

	return 0;
}

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

가지 뻗기로 8퀸 문제의 해답을 얻을 수 없다.

[규칙2] 각 행에 퀸을 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++) {
		if (!flag[j]) {		/* j행에 퀸을 배치하지 않았다면 */
			pos[i] = j;
			if (i == 7)		/* 모든 열에 퀸을 배치 */
				print();
			else {
				flag[j] = 1;
				set(i + 1);
				flag[j] = 0;
			}
		}
	}
}

int main(void)
{
	int i;
	for (i = 0; i < 8; i++)
		flag[i] = 0;

	set(0);

	return 0;
}

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

---

3. 8퀸 문제 구현

이전까지는 행 방향과 열 방향으로 겹치지 않는 조합을 나열하기만 함.
퀸은 대각선 방향으로 이동할 수 있기 때문에 어떠한 대각선에서 보더라도 퀸을 1개만 배치하는 한정 조작을 추가해야 한다.

/* 8퀸 문제 풀이 */
#include <stdio.h> 

int flag_a[8]; 		/* 각 행에 퀸을 배치했는지 체크하는 배열 */
int flag_b[15]; 	/* 대각선 ↙에 퀸을 배치했는지 체크하는 배열 */
int flag_c[15]; 	/* 대각선 ↘에 퀸을 배치했는지 체크하는 배열 */
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++) {
		if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) {
			pos[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);

	return 0;
}