백준 9663번 - N-Queen

https://www.acmicpc.net/problem/9663

백트래킹에서 유명한 N-Queen문제이다.

dfs를 통해 말이 일직선상에 있거나 대각선에 있는지를 확인해준다.

만약에 있다면 더이상 진행하지 않고 없다면 N번째까지 진행해주면 된다.

#include <iostream>
#include <math.h>
using namespace std;
 
int N;
int ans=0;
int queen[16]={0};
 
bool promising(int n){
    for(int i=1;i<n;i++){
        if(queen[n]==queen[i] || n-i==abs(queen[n]-queen[i]))
            return false;
    }
    return true;
}
void dfs(int n){
    if(n==N+1){
        ans++;
        return;
    }
    
    for(int i=1;i<=N;i++){
        queen[n]=i;
        if(promising(n)){
            dfs(n+1);
        }
    }
}
int main(){
    
    cin>>N;
    dfs(1);
    cout<<ans<<endl;
    return 0;
}