9663번: N-Queen

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


$O(n^2*n!)$

완전 탐색을 하되 행, 열, 두 방향의 대각선의 퀸 존재여부를 확인하여 탐색 시간을 줄인다.

#include<cstdio>
int ck[3][27], n, r;
void f(int h) {
    if (h == n) {
        r++;
        return;
    }
    for (int i = 0; i < n; i++) if (!ck[0][i] & !ck[1][h + i] & !ck[2][h - i + n - 1]) {
        ck[0][i] = ck[1][h + i] = ck[2][h - i + n - 1] = 1;
        f(h + 1);
        ck[0][i] = ck[1][h + i] = ck[2][h - i + n - 1] = 0;
    }
}
int main() {
    scanf("%d", &n);
    f(0);
    printf("%d", r);
    return 0;
}