백준 9663번 - N Queen

백준 9663번 - N Queen

문제

• N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

• N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

• 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력

8

예제 출력

92

접근

• 1행(Row), 1열(Column) 위치에 퀸을 하나 놓는다.

• 다음 행에서 가능한 가장 왼쪽에 퀸을 놓는다.

• N번째 열에 퀸을 놓지 못한다면 백트래킹

• 마지막 행에서 퀸을 하나 놓으면 하나의 정답을 구한 것이다.

• 모든 경우의 수를 조사하고 가능한 정답의 경우의 수를 구한다.

유망성 (Promising)

• 백트래킹 문제에서 현재의 경우의 수가 가능한 경우의 수인지 체크하는 것

• 백트래킹 문제는 트리 구조의 형태를 가지는데 전혀 정답이 나올 가능성이 없는 마디는 유망하지 않다고 한다. (Non-Promising)

• N-Queen 문제에서는 유망성을 검사할 때 열과 대각선만 검사하면 된다.

• 열(Column)을 검사하는 방법은 크기가 N인 배열을 만들어 퀸을 놓을 때마다 그 위치에 체크를 한다.

• 대각선의 경우는 기울기가 증가하는 대각선, 감소하는 대각선 두 가지로 나누어 생각해볼 수 있다.

• 대각선이 증가하는 경우는 (행+열)값이 일정하다.

• 대각선이 감소하는 경우는 (행-열)값이 일정하다.

C++ Code

#include <cstdio>
​
int n, ans = 0;
bool col[16];
bool inc[31];
bool dec[31];
​
void solve(int r) {
    if (r > n) {
        ans++;
        return;
    }
​
    for (int i = 1; i <= n; i++) {
        if (!col[i] && !inc[r + i] && !dec[n + (r - i) + 1]){
            col[i] = inc[r + i] = dec[n + (r - i) + 1] = true;
            solve(r + 1);
            col[i] = inc[r + i] = dec[n + (r - i) + 1] = false;
        }
    }
}
​
int main()
{
    scanf("%d", &n);
    solve(1);
    printf("%d\n", ans);
}