Catalog
八皇后问题

深搜模板题目:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int a[100];//表示行
int b[100];//表示第几列被占领
int c[100];//表示左下到右上的对角线
int d[100];//表示左上到右下的对角线
int total, n;
void print() {
if (total <= 2) {
for (int i = 1; i <= n; i++) {
cout << a[i];
if (i != n)
cout << " ";
}
cout << endl;
}
total++;
}
void queen(int i) {
if (i > n) {
print();
return;
}
else
for (int j = 1; j <= n; j++) {
if ((!b[j]) && (!c[i + j]) && (!d[i - j + n]))//如果没有皇后占领,则宣布占领
{
a[i] = j;
b[j] = 1;
c[i + j] = 1;
d[i - j + n] = 1;
queen(i + 1);
b[j] = 0;
c[i + j] = 0;
d[i - j + n] = 0;//回溯清除标记
}
}

}
int main() {
cin >> n;
queen(1);
cout << total;
}
Author: superzhaoyang
Link: http://yoursite.com/2019/11/21/八皇后问题/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝
��