퇴각 검색(Backtracking) : N-Queens 문제

N-Queens 문제는 작년에 풀다가 포기했던 기억이 나고 책에도 마침 나오길래 다시 풀어보았다. 

그 때 당시의 풀이를 생각해보면 접근부터가 잘못되었던 것을 이제야 알게되었다. 

 

그 당시에는 문제를 분할정복을 적용하여서 풀려고 했었다. 그런데 지금 와서 다시 생각해보니 완전 헛발을 짚은 것이다...

 

서론이 길었는데 코드부터 보여드리겠습니다.

#include <iostream>
using namespace std;
int cnt = 0, map[15][15], col[15], across1[50], across2[50], n;
void queens(int y)
{
    if(y == n) // n-1행까지 다 돌았으면 횟수를 추가하고 리턴
    {
        cnt++;
        return;
    }
    for(int x = 0; x<n; x++){ // 열을 반복
        if(col[x] || across1[x+y] || across2[x-y+n-1]) continue; 
        //같은 행, 같은 기울기의 대각선이 존재한다면 continue
        
        col[x] = 1;
        across1[x+y] = 1;
        across2[x-y+n-1] = 1;
        queens(y+1); // 다음 행 값
        col[x] = 0;
        across1[x+y] = 0;
        across2[x-y+n-1] = 0;
    }
    
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    queens(0);
    cout << cnt;
    
    return 0;
}

이 문제를 정확하게 설명하면

행마다 단 하나의 퀸을 배치하되, 그 퀸이 이전 단계에 배치된 퀸을 공격할 수 없도록 배치하는 것이다. 만약 nXn 이라면 n개의 퀸을 배치하면 그 때 하나의 해를 구한 것이다.

 

이 때 이전 단계의 배치된 퀸을 공격할 수 없도록 하기 위해 같은 열, 두 대각선에 대한 번호를 부여하여 가능성을 제거해야 한다.

0	1	2	3
0	1	2	3
0	1	2	3
0	1	2	3

col[] 배열은 같은 열이면 같은 번호가 부여된다.

0	1	2	3
1	2	3	4
2	3	4	5
3	4	5	6

across1[] 배열

3	4	5	6
2	3	4	5
1	2	3	4
0	1	2	3

across2[] 배열

 

이런 식으로 같은 번호가 배정되는 규칙이 있다. 

 

따라서 같은 수가 부여된다면 그 위치에는 배치될 수 없기에 해를 구할 수 있다.

 

하지만 백트랙킹은 브루트포스의 방법을 적용한 것으로 모든 경우의 수를 하면서 가지치기를 진행하는 것으로 n이 증가할 때 마다 탐색이 급격하게 느려진다. 

 

실제로 n이 27에 달하면 경우의 수는 컴퓨터 클러스터를 사용하여야 한다.