[BackTracking] 체스 여왕말 놓기 (N-Queen Problem)

[BackTracking] 체스 여왕말 놓기 (N-Queen Problem)

되추적(Backtracking) 방법을 얘기 할 때 가장 많이 거론 되는 듯한 N-여왕말(N-Queen) 문제이다. 어떤 문제인가하면 서양 장기(Chess:이후 체스)의 여왕말(Queen:이후 퀸)을 서로가 서로의 이동경로가 아닌 위치에 있도록 최대한 많은 퀸을 체스판 위에 놓는 문제이다.

 원래 체스판은 8ⅹ8이지만 간단히 4ⅹ4일 경우에 좌측의 결과와 같이 되는 경우를 찾는 것이 바로 N-Queen 문제 이다.

 4ⅹ4일 경우에는 좌측과 같은 2가지의 경우만 나오지만 체스판이 커지면 커질수록 다양한 경우의 수가 나온다. 우선 정해진 것은 NⅹN의 체스판에 올라갈 수 있는 퀸의 최대 갯수는 언제나 N이 된다는 점이다.

 그렇다면 어째서 이것이 되추적(Backtracking) 방법이 되느냐 하는 것은

① 첫번째 퀸이 (1, 1) 위치에 오게 될 경우

② 두번째 퀸은 (2, 3) 과 (2, 4) 위치에 올 수 있다. 우선 (2, 3) 위치에 퀸을 놓는다면

③ 세번째 퀸을 놓을 수 있는 자리는 없어진다. 그러면 다시 ②로 돌아가서 두번째 퀸을 (2, 4) 위치에 놓게 되면

④ 세번째 퀸을 (3, 2) 위치에 놓을 수 있지만 이렇게 되면 네번째 퀸을 놓을 수가 없어진다. 그렇게 되면 이번엔 다시 ①로 돌아가서 첫번째 퀸을 (1, 2)에 놓고 다시 시작한다.

 위의 과정과 같이 결과값을 찾아가다가 그 방법이 아니라는 것을 알았을 때 이전 단계로 돌아가는 것이 바로 되추적 방법이다.

 N-Queen의 문제의 경우 참고 자료에 있는 책을 본다면 좀 더 쉽게 알 수 있을 것이다. 언제나와 같이 나는 참고자료에 있는 'Foundations of Algorithms.....' 책을 참고로 해서 프로그램을 작성하였다.

 N값을 입력 받아서 결과를 보여주는 N-여왕말 문제 알고리즘

참고자료 

알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

누워서 읽는 알고리즘 - 임백준 저

#include <stdio.h>
#include <malloc.h>
#include <math.h>

void queens(int i, int n, int col[]);   // n개 여왕말 알고리즘
void printqueen(int n, int col[]);      // n개 여왕말의 위치 출력
int promising(int i, int col[]);    // 유망한지 검사하는 함수

int main()
{
	int i;
	int n;
	int* col;

	printf("How many Columns or Rows?\n> ");
	scanf("%d", &n);
	getchar();

	// 여왕말이 해당행의 몇번째 열에 있는지 저장
	col = (int*)malloc(sizeof(int)*n);

	// 뿌리 노드(0)부터 탐색을 시작
	queens(0, n, col);

	free(col);

	return 0;
}

void queens(int i, int n, int col[])
{
	int j;

	if (promising(i, col)) // 유망한가?
	if (i == n) // n개의 여왕말 위치를 찾았나?
		printqueen(n, col); // 여왕말 위치 출력
	else
	for (j = 1; j <= n; j++) {    // (i+1)번째 행에 있는 여왕말을
		col[i + 1] = j;           // n개의 열에 놓을 수 있는지 각각
		queens(i + 1, n, col);    // 검사한다.
	}
}

void printqueen(int n, int col[])   // 보기 편하게 결과값을 출력
{
	int j, k;
	printf("    |");           // 상단 열의 갯수 출력 부분
	for (j = 1; j <= n; j++)
		printf("%3d |", j);
	printf("\n");

	for (j = 0; j <= n; j++)    // 행을 나누는 선 출력
		printf("----+");
	printf("\n");

	for (j = 1; j <= n; j++) {
		printf("%3d |", j);   // 행의 번호
		for (k = 1; k < col[j]; k++) {
			if (((k + j) % 2))
				printf("▩▩|");    // 여왕말이 없는 칸
			else
				printf("    |");    // 여왕말이 없는 칸
		}
		printf("QUEE|");      // 여왕말
		for (k = col[j]; k < n; k++){
			if (!((k + j) % 2))
				printf("▩▩|");    // 여왕말이 없는 칸
			else
				printf("    |");    // 여왕말이 없는 칸
		}
		printf("\n");

		for (k = 0; k <= n; k++)   // 행을 나누는 선 출력
			printf("----+");
		printf("\n");
	}
	printf("\n");

	printf("Press ENTER to continue");
	getchar();  // 결과 값이 많으므로 하나의 결과값마다 멈추도록
}

int promising(int i, int col[]) // 유망한지 판단하는 함수
{
	int k;
	int bSwitch;

	k = 1;
	bSwitch = 1;
	while (k < i && bSwitch) {
		/* col[i] == col[k] 는 같은 열에 있는지 판별한다
		* abs(col[i] - col[k]) == i - k의 경우는
		* 2개의 여왕말간의  행의 차와 열의 차의 절대값이 같으면
		* 같은 대각선상에 있다는 의미이다. */
		if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
			bSwitch = 0;
		k++;
	}
	return bSwitch;
}

출처 : http://egloos.zum.com/sakuragis/v/3468837