sakuragi's miscellaneous space : N-여왕말 문제... N-Queen Problem

2007년 06월 03일

N-여왕말 문제... 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-여왕말 문제 알고리즘

#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;
}