1213：八皇后问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
【输入】
(无)
【输出】
按给定顺序和格式输出所有八皇后问题的解（见样例）。
题目要求：不能是同一列、同一行、同一斜线（两个方向的对角线
思路：
- 一个8*8的矩阵，用一个二维数组可以储存结果，也可以用一维数组（下标为n表示n行皇后的列数）
- 从第一个开始搜索，搜索时判断在这一行之前的数是否有同一列、同一斜线（由于是for循环搜索，每次搜索就是一个同一行确定一个皇后，所以不存在同一行的冲突）
- 用二维数组的话：
同一列，统一斜线最简单的就是用三个for循环，去找同一列和对角线是否冲突，但是不太聪明的样子 - 如果用一维数组的话：不难发现，只要一个for循环去判断是否该值和前面几行的值是否冲突就行。至于对角线不难发现：两行的差和两列的差的绝对值不相同，则不可能冲突即：
abs(a[i]-a[l])==abs(i-l)
- 用二维数组的话：
- 一共有92种放置方式，但是可以分为按列放置（先看第一列皇后放在哪一行，再看第二列皇后放在哪一行，，，）和按行放置（先看第一行皇后放在哪一列，再看第二行皇后放在哪一列，，，）
- 按行放置和按列放置最终结果排列有差异，但是内容一致，仔细观察会发现其实两种结果就是矩阵的转置即可得到，而当一维数组储存列数时，矩阵转置只需要下标和数组值对换就行
代码示例：
#include<bits/stdc++.h>
using namespace std;
int n=8,num=1;
int a[9]={0};
void dfs(int l);
int check(int l);//判断同一列/同一行/一条斜线上是否已经有皇后，传入参数为第几行
void print();
int main(){
dfs(1);
return 0;
}
void print(){
// 按行输出
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// if(j==a[i]) cout<<1<<" ";
// else cout<<0<<" ";
// }
// cout<<endl;
// }
//按列输出 ,按列实质就是矩阵倒置，由于是一维数组储存 所以只需要将第n行m行转化为第m列的n行即可
int b[9];
for(int i=1;i<=n;i++){
b[a[i]]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j==b[i]) cout<<1<<" ";
else cout<<0<<" ";
}
cout<<endl;
}
}
void dfs(int l){
//先判断是否需要结束该次遍历
if(l==n+1){
cout<<"NO. "<<num<<endl;
print();
num++;
return ;
}else{
//先循环遍历,i表示第几列
for(int i=1;i<=n;i++){
a[l]=i;//直接先赋值，否则会出错 （他会往下继续判断，然后再搜索下一行，如果该位置判断有问题，会回退到上一行，）
if(check(l)){ //判断
dfs(l+1);
}
}
return;
}
}
int check(int l){
for(int i=1;i<l;i++){ //即在l-1行才确定皇后的位置，后面的就不需要遍历判断了
if((a[i]==a[l])||(abs(a[i]-a[l])==abs(i-l))) { //a[l]表示的当前行所在列数
return 0;
}
}
return 1;
}
问题实质为：搜索、回溯
搜索与回溯
-
该搜索问题的实质是深度优先的算法（且为左根右）：为了求得问题的解，先选择某一种可能情况开始搜索，在搜索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向下搜索，如此反复进行，直至得到解或证明无解。
-
最终搜索的结果得到一个二叉树。而向下搜索的和回溯都可以利用递归去实现。
-
回溯是回到上一步然后再向下搜索，所以是基于第一次选择的条件下搜索，直到所有情况搜索完才会换到另外的选择继续搜索
以下是二叉树搜索的过程，根节点表示满足条件的 结果（4次搜索完成）
