目录
[TOC]
问题分析：
相信八皇后规则的问题，大家都很熟悉，接下来是如何分析回溯法的应用。回溯法与图里面的深度优先遍历非常的类似，就是，在满足题目条件时候，它总是优先选择第一个，当不满足的时候，它会选择接下来的一个点，通常会用遍历数组的方式。
总体的代码构建如下
void fun(n){
if(总体条件){
for(){
fun(n+1);
}
}
本问题分析：
每次填满第一行第一列，当不满足时候，试下第一行第二列，依次进行，递归的出口为找到第八个点，跳出递归。，在循环里面还要判断是否满足不同行，不同列，不同对角线。
具体代码实现：
#include<stdio.h>
#include<math.h>
int max=8,sum=0,a[8];
void show(){ //显示每次成功后整个界面的坐标
for(int i=0;i<max;i++){
printf("(%d,%d)\t",i,a[i]);
}
printf("\n");
}
int check(int n){
for(int i=0;i<n;i++){ //这里只需要比较到已知就行
if(a[i]==a[n]||abs(a[n]-a[i])==(n-i))//这里比较关键，就是判断现在放下的皇后是否与之前
return 0 ; //放下的皇后有冲突（即不同列，不同对角线，因为之前有
}
return 1; //之前有调用 eightQueen(n+1); //保证了不同行
}
int eightQueen(int n){
int i;
if(n<max){
for(i=0;i<max;i++){
a[n]=i;
if(check(n))
eightQueen(n+1);
}
}
else{
sum++;
show();
}
}
int main(){
eightQueen(0); //从第零行开始
printf("%d",sum);
}
Alt text
总共有92种。
结论：
主要是找到递归的出口，当满足添加时候，执行递归，不满足时候，执行循环的下一步。 马走日问题也是类似的。
