https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제의 이름 'N-Queen'은 사실 컴퓨터공학 전공으로 알고리즘 수업을 들었다면 수업시간에 접해봤을 문제중 하나다. 이 문제를 풀기위해선 백트레킹을 이용한 탐색 방법을 적용해야 하는데, 검색어 'N-Queen'으로 구글링만 해도 내가 첨부해놓은 하단의 답안보다, 더 가독성이 좋은 소스코드가 한무더기로 나온다. 위키백과에 있는 해설도 꽤 좋은 편이다. (gif로 해답을 얻어과는 과정도 보여준다.)
다만 백트래킹을 통한 '완전탐색' 알고리즘을 사용하기 때문에 N이 일정 수준 이상을 넘어가게 되면 시간복잡도가 제곱으로 늘어난다. 따라서 위 문제에서도 입력받을수 있는 N의 최대값은 14이다.
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#include <math.h>
int column[15] = { 0, };
int result = 0;
int N;
int capable(int i) {
int k = 1, capable = 1;
while (k < i && capable) {
if ((column[k] == column[i]) || (abs(column[i] - column[k]) == abs(i - k)))
capable = 0;
k++;
}
return capable;
}
void nqueens(int i) {
int j;
if (capable(i)) {
if (i == N) {
result += 1;
}
else {
for (j = 1; j <= N; ++j) {
column[i + 1] = j;
nqueens(i + 1);
}
}
}
}
int main(void) {
scanf("%d", &N);
nqueens(0);
printf("%d\n", result);
}