5-4장 8퀸 문제

1. 8퀸 문제 정의하기 

 

- 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓으세요

- 퀸은 가로,세로, 대각선 방향으로 체스판 끝까지 이동 가능

- 규칙 

1) 각 열에 퀸을 1개만 배치 

2) 각 행에 퀸을 1개만 배치 

 

2. 가지 뻗기(branching)

 

- 가지를 뻗으며 퀸을 배치하는 조합 모두 나열

- 배열 pos는 퀸의 배치를 나타냄 

- i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 함

 

- set함수 

 -> pos[i]에 0부터 7까지의 값을 순서대로 대입하여 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀함수'

 -> 0번째 열에 퀸을 배치 

set(0); //0열에 퀸을 배치

 -> for문에 의한 반복 구문에서는 i값을 0에서 7까지 증가시키면서 pos[i]에 j를 대입함으로써 퀸을 j행에 배치 

 -> 0번째 열이 확정 

set(i+1); //다음 열에 퀸을 배치

 

 ->앞에서 했던 작업을 다음열인 1열에서 수행

 ->i가 7이 되어 8개의 퀸이 모두 배치 될때까지 재귀호출 

 

print 함수 

 - 퀸이 배치된 위치 출력

 - pos의 배열 요솟값 출력

 

//각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열
#include <stdio.h> 

int pos[8]; // 각 열에서 퀸의 위치

//각 열의 퀸의 위치를 출력
void print(void)
{
	for(int i=0; i<8; i++)
		printf("%2d",pos[i]);
	putchar('\n');
}

//i열에 퀸을 배치 
void set(int i) 
{
	for(int j=0; j <8; j++)
	{
		pos[i]=j;
		if(i==7)
			print();
		else
			set(i+1);
	}
}

int main()
{
	set(0); //0열에 퀸을 배치 
	
	return 0; 
}

 

3. 분기 한정법 다루기 

 

- 규칙 2) 각 행에 퀸을 1개만 배치 를 적용하여 분기 한정

- 필요하지 않은 분기를 줄여 불필요한 

 

- flag[]

 -> 같은 행에 중복하여 퀸이 배치되는 것을 방지하기 위한 표시 

 -> j행에 퀸을 배치하면 flag[j]의 값을 1로 하고 배치되지 않은 상태의 값은 0으로 함 

 

-set함수는 퀸을 배치하지 않은 행(flag[i]값이 0인 행)에만 퀸을 배치 

 

-한정 조작(bounding)

 -> 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법 

 

- 분기 한정법 (branching and bounding method)

 -> 가지 뻗기와 한정 조작을 조합하여 문제를 풀어나감

 

ex)

- 0열에 퀸을 배치하기 위해 호출한 set 함수는 먼저 0행에 퀸을 배치 (flag[0] =0)

- 0행에 퀸을 배치했기 때문에 flag[0]의 값을 1로 변경

 

- set(i+1) 호출 -> 1열에 퀸을 배치 

 -> 0행에 퀸 배치?

  flag[0]의 값이 1이므로 배치 x

  set함수 재귀호출 x

 

 ->1행에 퀸 배치?

  flag[1]=0이므로 아직 배치 되지 않은 상태 

  1행에 퀸 배치 

   set함수를 재귀호출하여 다음 열인 2번째에 퀸을 배치 

 

//각 행, 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열
#include <stdio.h> 

int flag[8]; //각 행에 퀸을 배치했는지 체크하는 배열
int pos[8]; //각 열에서의 퀸의 위치 

//각 열에서 퀸의 위치를 출력
void print() 
{
	for(int i=0; i<8; i++)
	printf("%2d",pos[i]);
	putchar('\n');
}

//i열에서 알맞은 위치에 퀸을 배치 
void set(int i) 
{
	for(int 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()
{
	for(int i=0; i<8; i++)
		flag[i]=0;
	set(0);
	
	return 0;
}

 

4. 8퀸 문제를 푸는 프로그램 완성하기 

 

- 퀸은 대각선방향으로도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 1개만 배치하는 한정조작 추가 

 

- flag_b[]

 j행 i열의 값은 i+j

 '/' 방향의 대각선 위에 퀸을 배치했는지 체크 

- flag_c[]

  j행 i열의 값은 i-j+7

 '\' 방향의 대각선 위에 퀸을 배치했는지 체크 

- 각 칸에 퀸의 배치를 체크할 때 1) 같은 행에 퀸을 배치했는지 2) '/' 대각선 방향에 퀸을 배치했는지 3) '\' 대각선 방향에 퀸을 배치했는지 판단

 

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

int flag_a[8]; //각 행에 퀸을 배치했는지 체크하는 배열
int flag_b[15]; // 대각선 /에 퀸을 배치했는지 체크하는 배열
int flag_c[15]; // 대각선 \에 퀸을 배치했는지 체크하는 배열
int pos[8]; //각 열에서 퀸의 위치 

//각 열에서 퀸의 위치를 출력 
void print() 
{
	for(int i=0; i<8; i++)
		printf("%2d",pos[i]);
	putchar('\n');
}

//i열에서 알맞은 위치에 퀸을 배치 
void set(int i) 
{
	for(int 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()
{
	for(int i=0; i<8; i++)
		flag_a[i]=0;
	for(int i=0; i<15; i++)
		flag_b[i]=flag_c[i]=0;
	set(0); //0열에 배치 
	
	return 0; 
}