Eight queens problem

체스판에서 8개의 퀸을 서로 죽이지 않도록 배치하는 문제는 알고리즘에서 많이 다루어집니다. 여기서는 알고리즘의 문제도 있지만, 어떻게 프로그램을 작성해야지 더 효율적일지를 생각해볼까 합니다.

 

 

 

 

 

 

체스에서 퀸은 전후좌우 그리고 대각선까지 장애물이 있지 않는 한 원하는 칸 수만큼 이동할 수 있습니다. 체스판에서 8개의 퀸을 어떻게 배치하면 서로 잡을 수 없는 위치에 놓일까 하는 것입니다. 이 조건을 간단하게 정리하면 다음과 같습니다.

 

1. 각 열에는 오직 하나의 퀸만 존재해야 한다.
2. 각 행에는 오직 하나의 퀸만 존재해야 한다.
3. 각각의 퀸의 대각선에 다른 퀸이 존재해서는 안 된다.

여기서 첫번째 조건과 두번째 조건은 손쉽게 프로그램으로 작성할 수 있습니다. 만약 8개의 룩(Rook)을 가지고 이 문제를 냈다면, 수학적 방법으로도 문제를 풀 수 있습니다. 순열에 대한 경우의 수만 알고 있다면, 우리는 이 문제를 풀 수 있다. 8개의 퀸 문제는 여기에 대각선에 대한 조건이 더 추가됩니다.

 

이 문제를 풀기 위해서 가장 무식한 방법(Brute force method)을 선택한다면, 8x8의 체스판에 8개의 퀸을 놓는 경우를 다 따져보는 것입니다. 이 방법은 64개에서 8개를 선택하는 경우의 수와 같습니다. 이 숫자는 매우 큽니다. 

\[_{64}C_8 = 4,426,165,368\]

가지나 됩니다. 이 모든 경우를 처리하기 위해서는 엄청난 시간이 소요될 수밖에 없습니다.

 

알고리즘을 효율적으로 만들기 위해서는 미리 제한조건을 적용하는 것이 한 방법입니다. 첫번째 조건만을 적용한다면, $8^{8} = 16,777,216$ 경우의 수로 줄어듭니다. 앞에 있는 것보다 몇천배 빠르게 수행할 수 있습니다. 첫번째와 두번째 조건을 모두 적용한다면 보다 빠르게 동작할 수 있습니다. \(_{8}P_{8} = 8! = 40,320\) 경우의 수로 줄어듭니다.

 

경우의 수로만 따져본다면 이 순열을 이용하는 방법이 적합할 것으로 생각할 수 있습니다. 그러나 순열을 이용하는 방법은 실제 적합한 방법은 아닙니다. 왜냐하면 8개의 퀸 문제의 답은 92개만 존재하기 때문입니다. 대부분의 경우는 답이 될 수 없기 때문에 답이 아닌 경우를 제거하는 방법이 필요합니다. 예를 들어서 첫번째 열에 세번째 칸에 퀸이 있고, 두번째 열에 네번째 칸에 퀸이 있다면, 대각선으로 만나기 때문에 세번째 열부터 여덟번째 열까지는 검사할 필요가 없습니다. 실제 순열은 트리 모양으로 이어져 나가는 구조이기 때문에 우리는 깊이 우선탐색을 하면서 세번째 조건이 맞지 않는 경우가 발생하면, 그 이후의 트리를 검색하지 않는 방법입니다. 이 방법은 많은 경우에 효율적입니다. 이 방법을 이용하면 대각선 검사를 5,508번 합니다. 알고리즘에 따라서 조금 다르겠지만요.

 

순열을 이용해서 8개의 퀸 문제를 해결하는 프로그램은 다음과 같습니다.

 

int EightQueen5(int nSize)
{
    bool nextpermutation(int a[], int n);
    int *pnBoard = new int[nSize];
    for( int i = 0 ; i < nSize ; i++ ) pnBoard[i] = i;
    int count = 0;
    do
    {
        bool bFlag = true;
        for( int i = 0 ; i < nSize-1 && bFlag ; i++ )
        {
            for( int j = i+1 ; j < nSize && bFlag ; j++ )
                if( abs(pnBoard[j]-pnBoard[i]) == j-i )
                    bFlag = false;
        }
        if( bFlag ) count++;
    } while( nextpermutation(pnBoard, nSize) );
    return count;
}

#define    SWAP(X,Y) { int t = X; X=Y; Y=t; }
bool nextpermutation(int a[], int n)
{
    int maxk = -1;
    for( int i = 0 ; i < n-1 ; i++ )
        if( a[i] < a[i+1] ) maxk = i;
    if( maxk == -1 ) return false;
    int maxs = maxk+1;
    for( int i = maxk+2 ; i < n ; i++ )
        if( a[maxk] < a[i] ) maxs = i;
    SWAP(a[maxk], a[maxs]);
    int s = n-maxk-1;
    for( int i = 0 ; i < s/2 ; i++ )
        SWAP(a[maxk+1+i], a[maxk+s-i]);
    return true;
}

 

순열을 이용하는 방법인 경우 다음 순열을 알아내는 방법에 시간이 많이 소요되고, 대각선 검사가 복잡합니다. 대각선 검사에서 이미 \(O(n^{2} )\)의 복잡도를 가지고 있으니까요.

 

알고리즘 책이나 학교에서는 8x8만큼의 공간을 만들어놓고, 각각의 공간에 퀸을 배치하는 방법을 많이 가르칩니다. 이 방법이 동작하지 않는 것은 아니지만, 분명히 낭비가 있습니다. 비트필드를 이용해서 8개의 공간만 사용할 수도 있습니다만, 결국 같은 이야기입니다. 이렇게 구현을 하고, 첫번째 조건만을 적용하여 수행시간을 줄인 프로그램은 다음과 같습니다.

 

 

 

int EightQueen1(int nSize)
{
    int EightQueen1Int(int *pnBoard, int nDepth, int nSize);
    int *pnBoard = new int[nSize*nSize];
    for( int i = 0 ; i < nSize*nSize ; i++ ) pnBoard[i] = 0;
    int count = EightQueen1Int(pnBoard, 0, nSize);
    delete[] pnBoard;
    return count;
}

int EightQueen1Int(int *pnBoard, int nDepth, int nSize)
{
    int count = 0;
    for( int i = 0 ; i < nSize ; i++ )
    {
        int c = nDepth*nSize+i;
        bool bFlag = true;
        for( int k = 1 ; k < nSize && bFlag ; k++ )
        {
            if( nDepth-k < 0 ) break;
            if( pnBoard[c-nSize*k] ) bFlag = false;
        }
        for( int k = 1 ; k < nSize && bFlag ; k++ )
        {
            if( nDepth-k < 0 || i-k < 0 ) break;
            if( pnBoard[c-nSize*k-k] ) bFlag = false;
        }
        for( int k = 1 ; k < nSize && bFlag ; k++ )
        {
            if( nDepth-k < 0 || i+k >= nSize ) break;
            if( pnBoard[c-nSize*k+k] ) bFlag = false;
        }
        if( bFlag == false ) continue;
        if( nDepth == nSize-1 ) return 1;
        pnBoard[c] = 1;
        count += EightQueen1Int(pnBoard, nDepth+1, nSize);
        pnBoard[c] = 0;
    }
    return count;
}

 

 

아무래도 공간을 검사하기 때문에 알고리즘 상에 공간상 위치 검사하는 부분이 들어갑니다.

 

이 공간을 만들기 보다, 해당 열에 몇번째 칸에 퀸이 있는지 숫자로 표현을 한다면, 공간상에 퀸을 위치하는 것보다 더 효율적이 될 수밖에 없습니다. 이 알고리즘으로 우리는 적당한 수행시간으로 원하는 답을 찾을 수 있습니다.

 

int EightQueen2(int nSize)
{
    int EightQueen2Int(int *pnBoard, int nDepth, int nSize);
    int *pnBoard = new int[nSize];
    int count = EightQueen2Int(pnBoard, 0, nSize);
    delete[] pnBoard;
    return count;
}
 
int EightQueen2Int(int *pnBoard, int nDepth, int nSize)
{
    int count = 0;
    for( int i = 0 ; i < nSize ; i++ )
    {
        int j;
        for( j = 0 ; j < nDepth ; j++ )
        {
            if( pnBoard[j] == i || abs(i-pnBoard[j]) == nDepth-j ) break;
        }
        if( j < nDepth ) continue;
        if( nDepth == nSize-1 ) return 1;
        pnBoard[nDepth] = i;
        count += EightQueen2Int(pnBoard, nDepth+1, nSize);
    }
    return count;
}

 

대각선 검사하는 비용이 앞의 방법보다 줄어든 것으로 알 수 있습니다. 간단하게 위치의 차이와 열 인덱스의 차이를 검사하는 것만으로 대각선 검사를 대신합니다.

 

 다음은 같은 행에 퀸이 중복되지 않는 것을 보다 편하게 적용한 방법입니다. 여기서는 비트필드를 사용하였습니다. 이것으로 수행시간을 더 줄일 수 있습니다.

 

int EightQueen3(int nSize)
{
    int EightQueen3Int(int *pnBoard, int nLast, int nDepth, int nSize);
    int *pnBoard = new int[nSize];
    int count = EightQueen3Int(pnBoard, 0, 0, nSize);
    delete[] pnBoard;
    return count;
}
 
int EightQueen3Int(int *pnBoard, int nLast, int nDepth, int nSize)
{
    int count = 0;
    for( int i = 0 ; i < nSize ; i++ )
    {
        if( nLast & (1<<i) ) continue;
        int j;
        for( j = 0 ; j < nDepth ; j++ )
        {
            if( abs(i-pnBoard[j]) == nDepth-j ) break;
        }
        if( j < nDepth ) continue;
        if( nDepth == nSize-1 ) return 1;
        pnBoard[nDepth] = i;
        nLast |= 1<<i;
        count += EightQueen3Int(pnBoard, nLast, nDepth+1, nSize);
        nLast &= ~(1<<i);
    }
    return count;
}

 

이제까지 알고리즘이 자기호출함수(Recursion)를 이용한 방법이었는데, 자기호출함수를 사용하지 않고 해보았습니다. 많은 경우에 자기호출함수는 호출비용과 메모리 사용비용에 대해 페널티를 가지고 있습니다. 자기호출함수를 사용하지 않으면, 좀 더 수행시간을 줄일 수 있지만, 이 문제에서는 큰 영향을 미치지 않았습니다.

int EightQueen4(int nSize)
{
    int *pnBoard = new int[nSize];
    int s = 0, k = 0;
    int count = 0;
    while( 1 )
    {
        if( k == nSize )
        {
            if( s == 0 ) break;
            k = pnBoard[--s]+1;
            continue;
        }
        int j;
        for( j = 0 ; j < s ; j++ )
        {
            if( pnBoard[j] == k || abs(k-pnBoard[j]) == s-j ) break;
        }
        if( j < s ) k++;
        else if( s == nSize-1 ) { count++; k = pnBoard[--s]+1; }
        else { pnBoard[s++] = k; k = 0; }
    }
    delete[] pnBoard;
    return count;
}

 

자기호출함수를 사용하는 것을 비재귀프로그램으로 작성하는 것을 연습해보는 것은 개인적으로 프로그램 작성 공부에 많은 도움이 된다고 생각합니다.

 

마지막으로 실제 수행을 하였을 경우 수행결과와 수행시간을 정리해보도록 할께요.

 

 

 

DepthFirst1은 8x8의 공간을 만들고 푼 알고리즘입니다. DepthFirst2는 8개의 공간에 퀸의 위치를 지정한 알고리즘이고, DepthFirst3는 비트플래그로 같은 행에 퀸이 중복되지 않도록 한 알고리즘입니다. NonRecursion은 자기호출함수를 사용하지 않는 방법이고, Permutation은 순열을 사용한 방법입니다. 순열을 사용한 방법은 워낙 시간이 많이 소요되어서 퀸의 개수가 13개 이상인 경우 계산하지 않았습니다.