问题提出：八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850 提出在 8x8 格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后人有人用图论的方法解出 92种结果。虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后;可以从矩阵的特点上找到规律，如果在同一行，则行号相同:如果在同一列上，则列号相同;如果同在“/”斜线上的行列值之和相同:如果在对角线上，则行列号之和或行列号之差相等，逐个纪录符合题意的情况,最终得出解。
解决思路：利用数组来求解。
1)解决冲突问题:这个问题包括了行，列，两条对角线。
行:规定每一行放一个皇后，不会造成行上的冲突;
列:当第1列被某个皇后占领后，则同一列上的所有空格都不能再放皇后，被标记位置为被占领状态。
对角线：对角线有两个方向，在同一对角线上的所有点都不能有冲突。
2)使用算法分析与设计的知识，用递归法、枚举法、回溯法等解决问题。
3）思考要解决的问题：用什么算法分析与设计来描述棋盘，怎样描述棋盘，怎样描述皇后（包括皇后的位置，怎样移动皇后等）。怎样开始程序。
4）初步解决问题，列出大纲。
所用算法：
回溯法：
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。按选优条件向
前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标， 就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
行A的皇后放在第一列以后，行B的皇后放在第一列已经发生冲突。这时候不必继续放行C的皇后，而是调整行B的皇后到第二列，继续冲突放第三列，不冲突了才开始进入行C。如此可依次放下行A至E的皇后，将每个皇后往右边横向、斜向攻击的点位用叉标记，发现行F的皇后无处安身。这时回溯到行E的皇后，将其位置由第4列调整为第8列，进入行F，发现皇后依然无处安身，再次回溯行E。此时行E已经枚举完所有情况，回溯至行D，将其由第2列移至第7列，再进入行E继续。按此算法流程最终找到可行解，成功在棋盘里放下了8个“和平共处”的皇后。继续找完全部的解共92个。
回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。
流程图：
运行代码：
#include <stdio.h>
int queen[8] = {0};
int sum = 0;
int cnt ; //表示摆放了几个皇后，也表示摆放皇后的行数。
int col ; //表示在这一列上摆放了皇后
void greedy(){
while(1){
//在(cnt,col)这个坐标摆放皇后
if(cnt == 1 && queen[0] == 7 && col == 6){ //表示第一行的皇后已经到了第八列且第二行的皇后到了第六列位置，已经摆放不下皇后了就退出循环
break;
}
int isAttack = 0; //用来表示皇后们之间是否能够攻击的到，如果攻击的到就是1，否则就为0
int i=0;
for(i=0;i<cnt;i++){
if(queen[i] == col){ //表示在同一列上
isAttack = 1;
}
int div_row =cnt -i; //表示斜线上的纵坐标之差
int div_col = queen[i]-col; //表示斜线上横坐标之差
if(div_row == div_col ||div_row == -div_col){ //表示在同一斜线上
isAttack = 1;
}
}
if(isAttack == 0){ //表示可以放置
queen[cnt] = col; //记录皇后当前的列数
cnt++; //开始摆放下一个皇后
col = 0; //下一个皇后从第一列开始遍历
if(cnt == 8){ //如果摆满了八个皇后就打印出他们的摆法
for (i = 0 ; i <= 7; ++i) //打印该种摆放方法情况
{
for (int col=0;col<=7;col++)
{
if (col!=queen[i])
{
printf("0|");
}
else{printf("1|");}
}
printf("\n");
}
for(i=0;i<8;i++){
printf("%d ",queen[i]+1);
}
printf("\n");
sum++;
printf("这是第%d种摆法\n",sum);
printf("\n"); //并且摆放种数+1
do{ //越界问题 //回朔
cnt--; //撤回正在摆放的皇后
col = queen[cnt]+1; //往下一个列寻找摆放位置
}while(col>=8);
}
}else{ //表示不能摆放
col++;
while(col>=8){ //回朔
cnt--; //退一格
col = queen[cnt]+1; //上一个皇后往后移一格
}
}
}
printf("总共有%d种摆法\n",sum);
return ;
}
int main(){
greedy();
return 0;
}
总结感悟：
1.心得体会
这次课程设计我们解决了八皇后问题的位置输出问题，利用回溯法完成了八皇后九十二种解法。本问题的解题思路使用的是典型的回溯算法。回溯法有“通用解题法”之称。用它可以系统地搜索一个问题的所有解或任一解。回溯法在问题的解空间树中，拨深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。它适合于解组合数较大的问题。
2.总结文章来源：https://www.toymoban.com/news/detail-401995.html
此次的八皇后课程设计编程过程中，我们从最开始的查资料、确定算法、翻找课件、寻求递归过程一系列流程中，我们小组三人都熟悉掌握了算法设计与分析课程中的回溯、递归的应用，协同完善了八皇后安置问题。通过团队合作，使我们更好的解决问题，每个人都负责不同模块的操作，大大提高了效率。另外网络资料、向他人寻求帮助那些自己掌握不是很深刻的知识点都得到了巩固，大大提高了效率，更是明白了不同算法带来的效果是大大不同的，通过分析推敲我们选择了回溯算法，这种思维更有助于我们解决其他的问题！文章来源地址https://www.toymoban.com/news/detail-401995.html
到了这里，关于回溯法求解八皇后问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
