信息学一本通 1213：八皇后问题

1213：八皇后问题

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 31439     通过数: 11591

【题目描述】

【输入】

【输出】

【输入样例】

（无）

【输出样例】

No. 1
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
No. 2
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
...以下省略

#include
#include
using namespace std;
 
const int N = 10;
int ans, a[N];
void print() {
	printf("No. %d\n", ++ans);
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++)
			if (a[j] == i)printf("1 ");
			else printf("0 ");
		printf("\n");
	}
}
bool check(int x, int d) {
	for (int i = 1; i < d; i++) {
		if (a[i] == x || x - a[i] == d - i || x - a[i] == i - d)
			return 0;
	}
	return 1;
}
void solve(int d) {
	if (d == 9) {
		print();
		return;
	}
	for (int i = 1; i <= 8; i++) {
		if (check(i, d)) {
			a[d] = i;
			solve(d + 1);
		}
	}
}
//更多信息学资料：https://pan.baidu.com/s/10ES7h0hEedyjFXuoBAFKVQ?pwd=nrbl 
 
int main() {
	solve(1);
	return 0;
}