什么是八皇后问题？就是在一个8*8的棋盘中向着64个格子中放入8个皇后 任意2个皇后之间不能同行，同列，也不能是对角线的关系，问一共有多少种方案 ？这是一个经典的回溯问题，听别人说会了这个好多问题都可以很轻松的解决 ，当时想了好长时间，看了网上的思路，感觉最经典的是用x[i]=j;这个代表 第i行第j列是可以放入皇后的，比自己建立一个二维的数组感觉简单多了 ， 什么时候可以用dfs呢？我现在也一直再练习，想一想，对于每一个问题都 可以调用dfs来进行解决，也就说明了有时候我们没有必要从一个很大的方向 去思考，我们只需要把一个很大的问题进行缩小，因为他们的解题的思路都是 一样的，所以变成小问题反而更加容易解决。 我们先说这个八皇后问题的思路把； 主要是dfs函数，这个函数只有一个参数num，代表当前已经填写到了第几行 根据这个题意我们可以知道每一行只能有一个皇后， 当num==8时，那就说明已经全部搞定了，直接sum++就行了(sum代表有多少种 方案)，当num!=8，那就进行x[num+1]行的判断1-8，全部进行判断 如果符合条件，那就直接放入并进行下一行的判断，如果全部都不符合，那就 进行回溯， 具体思路就是这样，主要是条件的判断，我们没有必要进行 行条件的判断 因为我们是按照从第一行开始的，我们只需要进行列和对角线的判断 对角线有一个性质那就是斜率等于1或-1，具体列怎么判断那就直接一列 一列的进行判断，因为只有8列，直接一个for循环就行了 具体就是这样写的，自己动手写写吧！ 一共有92种 当然你如果想把所有的情况打印出来也是可以的 用chess[i][x[j]]进行标记就行了，这里就不再写了
#include <cstdio> #include <cmath> int x[10],sum=0; bool check(int i)//i代表当前的行 { for(int g=i-1;g>0;--g)//这个地方需要注意是对前面的i-1行进行判断 { if(x[g]==x[i]||(abs(x[i]-x[g])==abs(i-g))) return false; } return true; } void dfs(int num) { if(num==8) { ++sum; return ; } else { for(int j=1;j<=8;++j)//一共只有8列，我们一个一个的进行赋值 //判断就行了 { x[num+1]=j; if(check(num+1))//判断是否符合条件 dfs(num+1); } } } int main() { dfs(0);//一开始没有填入一行，那肯定从0开始 printf("%d\n",sum); return 0; }
