N-Queen
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
코드
#include <iostream>
#define MAX 15
using namespace std;
int N, result = 0;
int col[MAX];
bool check(int newC) {
for (int i = 0; i < newC; i++) {
if (col[i] == col[newC] || abs(col[newC] - col[i]) == newC - i) {
return false;
}
}
return true;
}
void dfs(int c) {
if (c == N) {
result++;
}
else {
for (int i = 0; i < N; i++) {
col[c] = i;
if (check(c)) {
dfs(c + 1);
}
}
}
}
int main(void) {
cin.tie(NULL); ios::sync_with_stdio(false);
cin >> N;
dfs(0);
cout << result;
}