백준 9663번 : N-Queen

Algorithm/problem

백준 9663번 : N-Queen

DingCoDing 2022. 12. 13. 23:36

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

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

#include <bits/stdc++.h>

using namespace std;

int N;
//i+j, i-j
bool arr[16], diagonal1[32], diagonal2[55];
int ans = 0;

void backTrack(int L) {
    if (L == N) {
        ans++;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!arr[i] && !diagonal1[L + i] && !diagonal2[L - i + N]) {
            arr[i] = diagonal1[L + i] = diagonal2[L - i + N] = 1;
            backTrack(L + 1);
            arr[i] = diagonal1[L + i] = diagonal2[L - i + N] = 0;
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    backTrack(0);
    cout << ans << '\n';

}