Untitled

Cho bàn cờ có kích thước NxN, và N quân hâu.

Có bao nhiêu cách để sắp xếp N quân hâu vào bàn cờ sao cho chúng không đe dọa lẫn nhau

input:

Dòng đầu tiên là số lương testcase,

Các dòng tiếp theo là kích thước bàn cờ N cho mỗi testcase.



Output:

In ra mỗi testcase với kết quả là số cách sắp xếp dưới dạng: 

Case #1: 1

Case #2: 0

Case #3: 0


13
1
2
3
4
5
8
6
7
13
12
11
9
10


#include <iostream>

using namespace std;

int T;
int N;

int checkCot[40];
int checkCheo1[40];
int checkCheo2[40];

int ans = 0;

int abss(int x) {
	if (x >= 0) return x;
	return -x;
}

void backTrack(int hang) {
	for (int cot = 0; cot < N; cot++) {
		if (checkCot[cot] == 0 && checkCheo1[hang - cot + N] == 0 && checkCheo2[hang + cot] == 0) {
			checkCot[cot] = 1;
			checkCheo1[hang - cot + N] = 1;
			checkCheo2[hang + cot] = 1;
			if (hang == N - 1) ans++;
			else backTrack(hang + 1);
			checkCot[cot] = 0;
			checkCheo1[hang - cot + N] = 0;
			checkCheo2[hang + cot] = 0;
		}
	}
}

int main() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		for (int i = 0; i < 40; i++) {
			checkCot[i] = 0;
			checkCheo1[i] = 0;
			checkCheo2[i] = 0;
		}
		ans = 0;
		backTrack(0);
		cout << "Case #" << t << ": " << ans << endl;
	}
	return 0;
}