백준 9663 : N-Queen

문제 설명

---

N-Queen 문제는 N × N 체스판 위에 N개의 퀸을 서로 공격하지 못하게 배치하는 방법의 수를 구하는 문제이다. (이때 1 ≤ N ≤ 15)

---

 

 N-Queen문제는 N범위가 작기 때문에 충분히 백트래킹을 통해 풀 수 있다. 하지만 퀸을 놓을 때 마다 상, 하, 좌, 우, 대각선 2방향을 모두 검사하려면 시간이 방대하게 걸린다. 따라서 이를 한번에 체크를 통해 확인해주어야 한다. 간단하게 현재 탐색중인 행 또는 열을 재귀함수의 인자로 하고, 체크배열 3개를 통해 대각성, 열을 체크해가며 탐색하면된다.

-기저 사례: 현재 탐색중인 행(row)이 N보다 크거나 같다면, 모든 퀸을 성공적으로 배치한 것이므로 cnt를 1 증가시킨다.

-백트래킹 과정-

 

• 행(row) x에서 가능한 모든 열(column) i에 대해 퀸을 놓는다.
• 퀸을 놓을 때, 그 열(ch_y[y]), 주대각선(ch_yx[x+y]), 부대각선(ch_xy[x-y+n])에 이미 다른 퀸이 있는지를 확인한다.
• 문제가 없다면, 퀸을 해당 위치에 놓고(ch_y[y] = 1 등) 다음 행(x+1)으로 넘어간다.
• 모든 경우를 확인한 후에는 원래 상태로 되돌린다.

 

---

소스코드

#include <stdio.h>

int n, ans;
int ch_yx[50], ch_y[20], ch_xy[50];

void NQueen(int x) {
    int y;
    if(x > n) {
        ans++;
        return;
    }
    for(y=1;y<=n;y++) {
        if(ch_yx[x + y] == 1 || ch_y[y] == 1 || ch_xy[x - y + n] == 1) continue;
        ch_y[y] = 1;
        ch_yx[x + y] = 1;
        ch_xy[x - y + n] = 1;
        NQueen(x + 1);
        ch_yx[y + x] = 0;
        ch_y[y] = 0;
        ch_xy[x - y + n] = 0;
    }
}

int main()
{
    int i, j;
    scanf("%d", &n);
    NQueen(1);
    printf("%d", ans);
    return 0;
}