2011/08/17 23:24
[Algorithm] N-Queen Programming/Algorithm2011/08/17 23:24
오늘의 포스팅 주제는 Algorithm입니다. 저번 백트래킹에 이어 N-Queen문제를 다뤄보려 합니다. Queen은 같은 열, 같은 행에 높인 말과 대각선상에 위치하는 말들을 공격할 수 있는 막강한 전사입니다. 이런 식으로 모두 N개의 퀸들이 서로를 공격할 수 없도록 만드는 것이 이 문제의 요점입니다. N이 8일때 체스판의 칸이 모두 64개이고 그 중에서 8개를 골라 퀸을 배치할 수 있으므로 후보해의 수는 총
아래는 N이 4개일 때의 퀸을 놓을 수 있는 경우의 수를 출력한 결과 입니다. 이렇게 어떠한 수가 주어졌을 때 퀸을 놓을 수 있는 문제를 N-Queen문제라고 하는데 옛날 가우스가 이 문제를 다뤘었고 많은 학생들 또한 이 문제를 다뤘습니다.
이 문제를 풀기위한 방법으로는 백트래킹(역추적) 기법이 알맞습니다. 너무나 많은 경우의 수를 일일히 고려하기에는 시간과 공간이 부족할 테니까요. 그래서 답이 될 수 없는 경우에 대해서는 일찌감치 그 경로를 끊어버리는 것이 더 효율적일 수 있습니다. 아래는 가로 세로 4개의 길이를 가지는 체스판에서 Queen을 놓을 수 있는 경우의 수를 그려본 상태 그래프 입니다.
1번째 인덱스부터 Backtrack에 쓰인 1번째 인덱스의 있는 값은 퀸을 놓을 수 있는 열을 의미하며 인덱스는 퀸의 행을 의미합니다. 이렇게 하면 체스판을 2차원 배열로 만들 필요 없이 단 N+1개의 배열의 길이로 N퀸 문제를 해결할 수 있습니다.
아래 상태 그래프를 해석하자면 (1, 2) (2, 4) (3, 1) (4, 3)에 퀸이 놓일 수 있는 경우라 볼 수 있습니다.
이를 소스코드로 구현하면 아래와 같습니다. 또 여기에 여러가지 가지치기가 존재할 수 있는데, 아래에 있는 코드에서는 k번째 열에 퀸을 전혀 놓을 수 없으면 뒤로 돌아가지만, 그보다 뒤에 있는 행(예를 들어 k+2번째 행)에 퀸을 놓을 만한 후보지가 없다면 굳이 k번째 열을 따져볼 필요도 없습니다. 이런 사실을 더 일찍알아낼수록 불필요한 작업횟수를 더 많이 줄일 수 있습니다.
속도를 더 향상시키고 싶다면 대칭을 생각해보면 됩니다. 풀이를 90도 회전시키면 또 다른 풀이가 나오고, 체스판의 중앙을 기준으로 거울 대충일 시켜도 또 다른 풀이가 만들어집니다. 각 군별로 하나씩의 풀이만 만든 다음 대칭을 생각해서 해의 개수를 구하면 검색해야 하는 경우의 수를 크게 줄일 수 있습니다.
예전에 읽었었던 임백준님의 누워서 읽는 알고리즘이라는 책에서 N-Queen 문제에 대한 제프 소머즈 알고리즘이라는 것을 읽었었는데 그 분이 쓰신 방법이 대칭과 비트연산입니다. 고수들은 비트를 자유자제로 다룬다는 사실에 감명받기도 하였죠.
예전에 읽었었던 임백준님의 누워서 읽는 알고리즘이라는 책에서 N-Queen 문제에 대한 제프 소머즈 알고리즘이라는 것을 읽었었는데 그 분이 쓰신 방법이 대칭과 비트연산입니다. 고수들은 비트를 자유자제로 다룬다는 사실에 감명받기도 하였죠.
COPY TO CLIPBOARD | DOWNLOAD | RAW | EMBED | REPORT ABUSE
- #include <stdio.h>
- #include <math.h>
- #define MAXCANDIDATES 100
- #define NMAX 100
- typedef int data;
- enum {FALSE, TRUE};
- bool finished;
- int solution_count = 0;
- int is_a_solution(int a[], int k, int n)
- {
- return (k==n);
- }
- void construct_candidates(int a[], int k, int n, int c[], int* ncandidates)
- {
- int i, j; // 카운터 //
- bool legal_move; // 이동 가능 여부 //
- *ncandidates = 0;
- // 열을 조사
- for(i=1; i<=n; i++)
- {
- legal_move = true;
- // 행을 조사
- for(j=1; j<k; j++)
- {
// 대각선 방향 or 같은 열 - if( abs( (k) -j ) == abs( i - a[j] ) || i == a[j] )
- {
- legal_move = false;
- break;
- }
- }
- if( legal_move == true )
- {
- c[*ncandidates] = i;
- *ncandidates = *ncandidates + 1;
- }
- }
- }
- void process_solution(int a[], int k, int n)
- {
- solution_count ++;
- printf("\n");
- for( int i=1 ; i<=n ; i++ )
- {
- for( int j=1 ; j<=n ; j++ )
- {
- if( a[j] == i)
- printf("Q");
- else
- printf(".");
- }
- printf("\n");
- }
- printf("\n");
- }
- void backtrack(int a[], int k, data input)
- {
- int c[MAXCANDIDATES] = {0,};
- int ncandidates=0;
- int i=0;
- if( is_a_solution(a, k, input) )
- {
- process_solution(a, k, input);
- }
- else
- {
- k++;
- construct_candidates(a, k, input, c, &ncandidates);
- for( i=0 ; i<ncandidates ; i++)
- {
- a[k] = c[i];
- backtrack(a, k, input);
- if( finished ) return; // 일찍 종료함
- }
- }
- }
- void generate_subsets(int n)
- {
- int a[NMAX];
- solution_count = 0;
- backtrack(a, 0, n);
- printf("n = %d solution_count = %d\n", n, solution_count);
- }
- int main(void)
- {
- generate_subsets(4);
- return 0;
- }
위 프로그램에서 가장 중요한 부분은 construct_candidates 입니다. 퀸을 놓을 자리를 지정하고 다음 해를 구할 함수를 호출할지를 결정하기 때문이죠. 여기서 처음 보면 이해가 잘 안가는 부분이 있는데 바로 대각선 상에 위협을 가하는 말이 있는지 검사하는 코드입니다.
|행1 - 행2| == |열1 - 열2|
예를 들자면 (2,2)와 (3,3) 상에 존재하는 퀸들은 서로를 대각선상에서 위협합니다. 그렇기에 퀸을 놓을 수가 없는 것이죠. 그럼 여기까지 N-Queen Problem 설명을 마치도록 하겠습니다.
참조 : Programming Challenge 알고리즘 트레이닝 북
