백준 9663 C언어

백트래킹의 유명한 문제로 체스 판에 퀸을 서로 공격할 수 없게 놓는 문제다.

#include <stdio.h>

int cnt = 0;
int Arr[15][15] = { {0,}, };

void BackTracking(int N, int d) {
	for (int i = 0, k; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (i == k) Arr[d][k] = 1;
			else Arr[d][k] = 0;
		}

		for (k = 0; k < d; k++) {//위 확인
			if (Arr[k][i] == 1) break;
		}
		if (k != d) continue;

		for (k = 0; k < d; k++) {//좌측 상단 확인
			if(i-1-k >= 0)
				if (Arr[d - 1 - k][i - 1 - k] == 1) break;
		}
		if (k != d) continue;

		for (k = 0; k < d; k++) {//우측 상단 확인
			if(i+1+k < N)
				if (Arr[d - 1 - k][i + 1 + k] == 1) break;
		}
		if (k != d) continue;


		if (N - 1 == d) cnt++;
		else BackTracking(N, d + 1);
	}
}

int main() {
	int N;
	scanf("%d", &N);

	BackTracking(N, 0);
	printf("%d", cnt);
	return 0;
}