Backtracking(가지 치기) 문제로 유명한 N-Queen 문제이다.
Backtracking이란, 간단하게 말해 brute-force(전부 일일히 다 해보는 것)방법을 수행하지만 한정 함수(bounding function)을 이용해 경우의 수를 줄여나가는 방법을 말한다.
아래는 백트래킹에서 Bounding function(아래 코드에선 promising 함수)를 사용해 구현한 것이다. 시간복잡도는 O(N^N)이어야 하지만, 한정 함수에 의해 실제로는 더 빠른 속도로 수행되는 것을 알 수 있다.
#include <iostream>
using namespace std;
int N;
int col[15];
int result = 0;
bool promising(int i)
{
for(int j=0;j<i;j++)
{
// 새로운 퀸과 기존의 퀸이 같은 행에 있거나 대각선에 있을 경우
if(col[j] == col[i] || abs(col[i]-col[j]) == (i-j))
return false;
}
return true;
}
void N_Queen(int i)
{
if(i == N)
result += 1;
else
{
for(int j=0;j<N;j++)
{
col[i] = j;
if(promising(i))
N_Queen(i+1);
}
}
}
int main()
{
cin>>N;
N_Queen(0);
cout<<result<<endl;
return 0;
}