8-Queen recursion in c

분할 정복(divide and conquer) + 분기한정법(branching and bounding method)

열마다 어느 행에 퀸을 위치시켰는지 출력하기.

#include <stdio.h>

int flag_row[8]; // 행에 퀸을 배치했는지 참 거짓 판단 배열
int flag_diagonal_one[15]; // 대각선에 퀸을 배치했는지 참 거짓 판단 배열 1
int flag_diagonal_two[15]; // 대각선에 퀸을 배치했는지 참 거짓 판단 배열 2
int pos[8]; // 대괄호 안은 열. pos[] 값은 행의 값

// 조건에 맞는 퀸이 위치된 행 출력하는 함수
void print(void)
{
	int i;
	for (i = 0; i < 8; i++)
		printf("%2d", pos[i]);
	putchar('\n');
}

// 8퀸 계산 함수
void set(int i)
{
	int j;
	for (j = 0; j < 8;j++)
	{
		// i는 열. j는 행이다. 판단하고자 하는 자리가 배치할 수 있는 자리인지 판별한다.
		if (!flag_row[j] && !flag_diagonal_one[i + j] && !flag_diagonal_two[i + 7 - j])
		{
			// 조건 만족한다면 배치해주기.
			pos[i] = j;
			if (i == 7) // 모든 열(i)에 배치가 완료되었다면
				print(); // 열마다 어느 행에 배치하였는지 출력.
			else {
				// 해당 위치의 행과 대각선들에는 배치할 수 없다는 표식을 해주기.
				flag_row[j] = flag_diagonal_one[i + j] = flag_diagonal_two[i + 7 - j] = 1;
				// 열 증가시키고 recursion.
				set(i + 1);
				// 열마다 다 도는 사이클이 7빼고 끝나면 flag 값 초기화.
				flag_row[j] = flag_diagonal_one[i + j] = flag_diagonal_two[i + 7 - j] = 0;
			}
		}
	}
}

int main(void)
{
	int i;
	for (i = 0; i < 8;i++)
		flag_row[i] = 0;
	for (i = 0;i < 15;i++)
		flag_diagonal_one[i] = flag_diagonal_two[i] = 0;
	set(0);

	return 0;
}

 

결과창.