N-Queen - 9663

//9663 - N-Queen
 
#include <iostream>
using namespace std;
 
int N;
bool r[15], c[15], dc[29], ic[29];
 
int di(int x, int y)
{
    return x - y + N-1;
}
 
int ii(int x, int y)
{
    return x+y;
}
 
int ch(int x, int y, int n)
{
    if(n == N-1)
        return 1;
    if(x == N)
        return 0;
    
    r[x] = c[y] = dc[di(x, y)] = ic[ii(x, y)] = true;
    int ret = 0;
    for(int i = 0; i<N; ++i)
        if(!r[x+1] && !c[i] && !dc[di(x+1, i)] && !ic[ii(x+1, i)])
            ret += ch(x+1, i, n+1);
    r[x] = c[y] = dc[di(x, y)] = ic[ii(x, y)] = false;
    return ret;
}
 
int main()
{
    cin >> N;
    int ans = 0;
    for(int i = 0; i<N; ++i)
        if(!r[0] && !c[i] && !dc[di(0, i)] && !ic[ii(0, i)])
            ans += ch(0, i, 0);
    cout << ans;
}

 

 

 

 

 

 

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

9663번: N-Queen

 

 

 

 

 

 

N-Queen

가로, 세로, 감소하는 대각선, 증가하는 대각선에 겹치게 퀸이 존재할수 없기 때문에 각각의 배열을 만들어 해당 라인에 퀸이 있으면 true, 없으면 false를 넣어 가지치기를 해주었습니다.