[9663] N-Queen

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

9663번: N-Queen

<문제>

유명한 백트래킹 문제이다.

퀸의 이동방식은 가로, 세로, 대각선이다. 체스에서는 퀸(기물)의 '행마'나 '행마법'이라는 표현도 쓰는것 같다.

퀸의 행마법

우리는 아래와 같이 탐색을 진행할 것이다.

1) 한개의 행에는 하나의 퀸만 놓는다. 우리는 당장 놓아야하는 행의 위치를 'depth(level)'로 표현할것이다.
한개의 행에 하나의 퀸을 놓고, 총 N번 반복하면(depth == N) 모든 퀸을 놓은것으로 볼 수 있다.
이 방법의 장점은 같은 행에 퀸이 존재하는지는 무시해도 된다.

2) 한개의 열에는 하나의 퀸만 있어야 한다. i열에 퀸이 있다면, i열에 퀸이 있다고 표시해주면 된다. 대각선에 비해 매우 간단하니 이 부분이 문제가 되진 않을것이다.

3) 대각선에 대한 판별은, 행과 열의 차이가 일정하다는 것을 이용할 수 있다.

 i는 퀸의 열, queen[i]에는 퀸의 행이 저장되어 있다.

<소스코드>

#include<stdio.h>
#include<math.h>
int n,cnt,queen[15];
int check(int x) {
    int i,key;
    key = true;
    for (i = 0; i < x; i++) {
        if (queen[i] == queen[x] || x - i == abs(queen[i] - queen[x]))
            key = false;
    }
    return key;
}
void f(int level) {
    int i, j;
    if (level == n) {
        cnt++;
        return;
    }
    for (i = 0; i < n; i++) {
        queen[level] = i;
        if (check(level) == true)
            f(level + 1);
    }
}
int main(void) {
    scanf("%d", &n);
    f(0);
    printf("%d", cnt);
    return 0;
}