[C언어 소스] Backtracking을 이용한 N-Queen 문제 해결법

일단 N-Queen문제가 뭘까? 이 문제의 목적은 잘 모르겠으나 알고리즘을 공부하다 보면 자주 보이는 문제이다.

이 문제를 푸는 방법도 참 여러가지다.

 

일단 이 문제는 이름대로 장기판에 여왕말을 놓는 문제인데, 이 여왕말이 다 적이다. 어떤 여왕말이든 다른 여왕말을 먹을 수 있다는 것이다. 하지만 그걸 못 먹도록 하는게 이 문제의 핵심이다.

즉, 모든 여왕말이 다른 여왕말이 바로 공격할 수 있는 거리에 있는 것이다. 그 말인 즉슨 어떤 여왕말이 다른 여왕말을 먹으면 그 여왕말은 또 다른 말에게 먹히기 때문에 아무도 움직일 수 없는 상태인 것이다.

 

예를 들어 4x4의 체스 판에서는

 

	Q
			Q
Q
		Q

 

이런 구도라면 어떤 여왕말도 쉽사리 움직 일 수 없다. 그리고 5x5라면

 

Q
		Q
				Q
	Q
			Q

 

이런식의 결과가 나올 수 있다.

 

이 문제의 제약사항은 가로, 세로, 대각선줄에 오직 하나의 Queen만 있어야 한다. 근데 신기한건, 정사각형 체스판에서는 가로, 세로, 대각선줄에 오직 하나의 Queen만 있게 할 경우 자동으로 서로 공격을 할 수 없는 상태가 된다. 아마 이런 특성 때문에 N-Queen문제가 여러가지로 풀리는게 아닌가 생각된다. 그래서 어떤 블로그에선 N-Queen문제를 "가로, 세로, 대각선으로 중복되지 않게 말을 놓는 문제" 라고 해 놓는 경우도 봤다.

 

왜 가로, 세로, 대각선으로 중복되지 않게 말을 놓을 경우 그게 공격 불가능한 상태가 되는지 증명은 생략한다. 그냥 그런 특징이 있다고만 알면 된다ㅎㅎ

 

이 문제는 n이 작다면 얼마든지 눈으로도 풀 수 있는 문제이지만 n이 커지면 사람도, 컴퓨터도 풀기 어려워진다. 첫번째 말을 첫번째에 놔 보고 나머지를 다 놔본 다음에 안되면 첫번째 말을 옮기고 나머지 과정을 다시 다 시도해야 되는것이다. 알고리즘이라고 뭔가 특별할게 있나 싶지만 Deterministic Algorithm을 이용한 방법은 그냥 아까 말했던 방법 그대로다. 엄청난 반복수행으로 결과가 얻어진다.

 

먼저 코드를 보자.

 

1. #include <stdio.h>
2. #include <stdlib.h>
3.  
4. void queens(int);
5. int promising(int);
6. int n;
7. int col[255]={0,};
8.  
9. FILE *inputFile, *outputFile;
10.  
11. int main() {
12.     char fileName[255];
13.  
14.     printf("input num? ");
15.     scanf("%d", &n);
16.     queens(0);
17. }
18.  
19. void printResult() {
20.     int i;
21.     printf("result : ");
22.     for(i = 1; i<=n; i++) printf("%d ", col[i]);
23.     exit(1);
24. }
25.  
26. void queens(int i) {
27.     int j;
28.    
29.     if(promising(i)) {
30.         if(i == n) printResult();
31.         else
32.             for(j = 1; j <= n; j++) {
33.                 col[i+1] = j;
34.                 queens(i+1);
35.             }
36.     }
37. }
38.  
39. int promising(int i) { // 직선, 대각선으로 만나는지 검사
40.     int k = 1, promising = 1;
41.     while(k < i && promising) {
42.         if(col[i] == col[k] || abs(col[i]-col[k]) == abs(i-k))
43.             promising = 0; 
44.         k++;
45.     }
46.     return promising;
47. }

코드는 간단하지만 재귀적으로 반복되는 양이 장난이 아니다. n이 30정도 되면 연산하는데 시간이 꽤 걸린다.

예를 들어 n=4인 경우 그림으로 표현하면 아래와 같다.

 

 

 

아까 말한 그대로다. Tree형태로 모든 경우를 다 따져 보는것이다.

확인을 위해서 queen함수를 아래와 같이 수정하여 그때그때 적용되는 값을 보자

 

1. void queens(int i) {
2.     int j,x;
3.     for(x=1; x<=n; x++) {
4.         printf("%d ",col[x]);
5.         if(n==x) printf("\n");
6.     }
7.    
8.     if(promising(i)) {
9.         if(i == n) printResult();
10.         else
11.             for(j = 1; j <= n; j++) {
12.                 col[i+1] = j;
13.                 queens(i+1);
14.             }
15.     }
16. }

마찬가지로 n=4를 넣었을때 결과는 아래와 같이 나온다.

 

 

딱 저 그림대로 되는 것이다. 소스를 분석 해 보자.

 

이 함수는 queen함수와, 그 안에 내부적으로 사용되는 printResult, promising 함수로 이루어져 있다.

printResult는 말그대로 연산이 끝난 후 결과값을 출력하는 함수다. 내부 구조도 간단하므로 설명은 생략하겠다. promising은 "조짐이 좋은"이라는 뜻인데.. 지금 놓은 말이 정답이 될 가능성이 있는지 체크해 본다.

 

이 알고리즘은 크기가 n인 col이라는 함수를 사용한다. col[i]의 값은 i행에서 말이 놓이는 열을 뜻한다.

queen함수는 i를 인자로 받아서 col[i]에 1부터 n까지의 수를 넣어본다. 그리고 promising함수를 통해 그 값을 체크 해 보고 괜찮은 값(조짐이 좋은? 가능성이 있는?)이면 재귀적으로 계속 실행하는 것이다.

 

queen(i)

  가능성이 있는가?

    col[i]에 1~n넣고 queen(i+1);

 

이렇게 하면 진짜 모든 경우를 다 체크하게 된다. 하지만 답이 나왔으면 그만 체크하고 결과를 출력 해 줘야 한다.

그래서 소스를 보면 아래와 같이 되어 있다.

 

queen(i)

  가능성이 있는가?

    i가 n까지 왔는가? 그럼 출력

    아니면, col[i]에 1~n넣고 queen(i+1);

 

어찌어찌 해서 n-1번째 행까지 왔다. 즉, 5x5 판에서 4번째 행까지의 결과가 나왔다. 그리고 5번째에 아무거나 넣어 봤는데 promising 결과가 문제가 없다면? 그건 1~5번째 행에 모든 결과값이 제대로 나왔다는 것이다.

 

자 그럼 promising함수는 어떻게 구성되어 있을까? col[i] == col[k] || abs(col[i]-col[k]) == abs(i-k) 라는 조건이 어려워 보일수도 있는데 생각보다 쉽다. 그냥 잠깐 뜯어 보면 직선이나 대각선상에 있지 않은지를 체크하는 것이다. 이전에 놓인 말중 어떤 말과도 직선이나 대각선상에 있으면 false를 반환하고 더이상 계산하지 않는다. 이 반환값이 true인 경우만 "가능성이 있다"라고 판단하고 계산을 하는 것이다.