回溯法之八皇后问题简单理解
时间： 20:08:20
&&&& 阅读：3010
&&&& 评论：
&&&& 收藏：0
标签：回溯法，简单理解就是有源可溯。基本思想要借鉴穷举法，但是它不是一味地穷举，当发现某一步不符合条件时，这一步后面的穷举操作就不进行了（俗称&剪枝&），我自己把它叫做动态穷举法。假设第一个步骤可行，那么执行第二个步骤，第三个......如果其中第三个步骤不行，那么我们再回过来（回溯），第二个步骤换一种方法尝试，然后再重新第三个步骤，第四个......直到完成任务要求为止。
这里，以八皇后问题为例。试图把回溯法讲清楚。
注意：递归应该是一种算法结构，回溯法是一种算法思想。
何为八皇后问题？
（百度百科）八皇后问题是一个以国际象棋为背景的问题：如何能够在 8&8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n&n，而皇后个数也变成n。当且仅当 n = 1 或 n & 4 时问题有解。
八皇后问题最早是由国际西洋棋棋手马克斯&贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹&诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。
艾兹格&迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。
八皇后问题出现在1990年代初期的著名电子游戏第七访客中。
我们采用回溯法来解决这个问题。还记得我说的动态穷举法（&剪枝&）？那么我们就开始穷举吧。过程请看下图。八个皇后，每个皇后放一行，那么我们要确定的就是每行皇后要放的列的位置。对于第一行，假设把皇后放在第一列（这里就开始了一个for循环了）。第一步当然满足，然后我们看第二行（又开始一个for循环啦），假设把第二个皇后放在（2，1）（行，列）处，不行（&剪枝&）！那继续for，放在(2,2)处，不行（&剪枝&）！继续for，放在(2,3)处。Bingo!那我们进行第三步，第四步....也许，在第三步当中，执行完第三步的八次for循环后，仍未有合理的答案。那么就得返回第二步了。这时候，把第二个皇后放在(2,4)处。继续......
（参考http://blog.csdn.net/justme0/article/details/7540425）
接下来，我们就要尝试把这个过程转化成伪代码。
//寻找当前行的皇后应该位于哪一列
void FindQueen(row)
　　for(int i=0;i&8;i++)
　　　　//1.判断当前是否满足要求
　　　　if(Is_Meet(row,i))
　　　　//2.判断当前是否是最后一行了
　　　　　　if(最后一行）{输出操作，并返回}
　　　　//3.执行下一行匹配
　　　　　　FindQueen(row+1);
　　　　//4.如果进行到这一步，说明步骤三已经操作完，没有合适结果，需要返回上一步，即执行当前for的下一个循环
判断是否满足条件
这里，有一步我们需要再考虑下的，即第1步，如何判断当前插入的皇后满足条件。
根据国际象棋的规则，不能有两个皇后位于：1）同一列；2）同一对角线。
比较好判断，列号相同，即属于同一列；
2）同一对角线
有两种位置：正斜对角线和反斜对角线。判断条件分别为：（r1+c1)==(r2+c2)，(r1-c1)==(r2-c2)
将新的皇后位置依次与已经插入过的皇后位置进行比较判断即可。
看到以上代码，应该有点思路了吧。上具体实现代码。
bool Is_Meet(int row,int column)
for(int r=0;r&r++)
c=queen[r];
if(column==c)
if((row+column)==(c+r))
if((column-row)==(c-r))
void findQueen(int row)
for(int c=0;c&8;c++)
if(Is_Meet(row,c))
queen[row]=c;
if(row==7)
findQueen(row+1);
queen[row]=-1;
为了好玩，简单地改了下，使其可以在控制台动态显示匹配过程。
#include "iostream"
#include "string"
#include &Windows.h&
using namespace
int queen[8];
void print()
system("cls");
cout && "八皇后问题动态演示\n";
cout&& "------------------------\n";
for (int outer = 0; outer & 8; outer++)
if(queen[outer]!=-1)
for (int inner = 0; inner & queen[outer]; inner++)
cout && " . ";
cout&&" # ";
for (int inner = queen[outer] + 1; inner & 8; inner++)
cout && " . ";
bool Is_Meet(int row,int column)
for(int r=0;r&r++)
c=queen[r];
if(column==c)
if((row+column)==(c+r))
if((column-row)==(c-r))
void findQueen(int row)
for(int c=0;c&8;c++)
Sleep(1000);
if(Is_Meet(row,c))
queen[row]=c;
if(row==7)
//print();
findQueen(row+1);
queen[row]=-1;
int main()
memset(queen,-1,8*sizeof(int));//这里是赋-1，故不会出错，要清楚memset是依次对单个字节进行赋值
findQueen(0);
&&国之画&&&& &&&&chrome插件
版权所有 京ICP备号-2
迷上了代码！&C++类库算法皇后问题回溯法 类库与算法八皇后问题源代码
秒后自动跳转到登录页
快捷登录：
举报类型：
不规范：上传重复资源
不规范：标题与实际内容不符
不规范：资源无法下载或使用
其他不规范行为
违规：资源涉及侵权
违规：含有危害国家安全等内容
违规：含有反动/色情等内容
违规：广告内容
详细原因：
任何违反下载中心规定的资源，欢迎Down友监督举报，第一举报人可获5-10下载豆奖励。
视频课程推荐
C++类库算法皇后问题回溯法 类库与算法八皇后问题源代码
上传时间：
技术分类：
资源评价：
（0位用户参与评价）
已被下载&4&次
一款用C++编程实现的类库与算法皇后问题回溯法实现，八皇后问题，期末考试编程实现题，压缩包有运行截图，已通过老师满分测试，相信很多同学需要用到。
本资料共包含以下附件：
C++类库算法皇后问题回溯法.rar
51CTO下载中心常见问题：
1.如何获得下载豆？
1)上传资料
2)评论资料
3)每天在首页签到领取
4)购买VIP会员服务，无需下载豆下载资源
5)更多途径：点击此处
2.如何删除自己的资料？
下载资料意味着您已同意遵守以下协议：
1.资料的所有权益归上传用户所有
2.未经权益所有人同意，不得将资料中的内容挪作商业或盈利用途
3.51CTO下载中心仅提供资料交流平台，并不对任何资料负责
4.本站资料中如有侵权或不适当内容，请邮件与我们联系（）
5.本站不保证资源的准确性、安全性和完整性, 同时也不承担用户因使用这些资料对自己和他人造成任何形式的伤害或损失
相关专题推荐
本专题收录Java经典编程的实例源码，
在国内的开发语言中，java凭借这简单
本套视频教程是韩顺平老师，循序渐进
北京圣思园张龙（风中叶）老师的Java
讲述Arm嵌入式Linux系统下的C语言编程
这段视频是从尚学堂科技的教学课堂上
本套视频共78集，是由郝斌老师根据多
本视频专题共180集涵盖了C语言概述中
本视频专题共107集涵盖了Java概述、数
由传智播客毕向东老师讲解的Java基础
本专题为spring视频教程，共31集。教
本专题为C语言黑客编程系列视频教程，
本专题为韩顺平讲解的Java从入门到精
本专题为Java Web项目开发案例精粹视
SSH为struts+spring+hibernate的一个
本专题为疯狂Java李刚老师讲解的Stru
意见或建议：
联系方式：
您已提交成功！感谢您的宝贵意见，我们会尽快处理我是一个C++初学者，控制台实现了一个八皇后问题。
代码如下：
//"八皇后问题"V1.0
//李国良于日编写完成
#include &iostream&
#include &Windows.h&
using namespace
const int ArSize = 8;//这个数等于几，就是几皇后。
int num = 0;
void solve(bool arr[ArSize][ArSize], int row);
bool check(bool arr[ArSize][ArSize], int row, int column);
void outPut(bool arr[ArSize][ArSize]);
int main()
SetConsoleTitle("八皇后问题");
bool chessboard[ArSize][ArSize];
for (auto &i : chessboard)
for (auto &j : i)
j = false;
solve(chessboard, 0);
cout && "八皇后问题共有" && num && "种解！" &&
system("pause");
void solve(bool arr[ArSize][ArSize], int row)
for (int column = 0; column & ArS ++column)
arr[row][column] = true;
if (check(arr, row, column))
if (row + 1 == ArSize)
outPut(arr);
solve(arr, row + 1);
arr[row][column] = false;
bool check(bool arr[ArSize][ArSize], int row, int column)
if (row == 0)
return true;
for (i = 0; i & ++i)
if (arr[i][column])
return false;
i = row - 1;
j = column - 1;
while (i &= 0 && j &= 0)
if (arr[i][j])
return false;
i = row - 1;
j = column + 1;
while (i &= 0 && j &= ArSize - 1)
if (arr[i][j])
return false;
return true;
void outPut(bool arr[ArSize][ArSize])
cout && "**********************" && num && "*********************" &&
for (int i = 0; i & ArS ++i)
for (int j = 0; j & ArS ++j)
cout && arr[i][j] && " ";
cout && "*********************************************" &&
阅读(...) 评论()1049人阅读
算法专区（13）
&&&&&&&& 题目说明：皇后可以横竖45度斜着吃子，现在在8*8的棋盘上放置8个皇后。问如何放置才能使她们平安相处？
&&&&&&&& 我用树结构解决的：对前7行的节点来说，下面有8中选择，如果下一行的某一个节点n可以放置，则改链增加，直到8个子都能放，否则链寻访下一个节点n+1，还不行就返回（节点数变小）。直到遍历了所有可能：
&&&&&&&&太可惜了，买了新电脑，把这个源代码没有拷贝（以前电脑上东西比较乱，坏习惯，要改）。我就说一下最深刻地感受，当初一开始开始是写了一个函数，一直递归调用直到最终结束，结果只能算到28，29（换了个机子）个结果（正确结果有92个），发现这是栈耗尽引起的。后来改成了bool&& funDeel函数处理，该函数只当最终结束才返回true, 用函数A一直调用funDeel直到他返回true. 这样每次调用funDeel后，栈会被释放。& 就计算出了92个结果。
&&&&&&& 没有源代码，有些不爽，啥时候补上。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：51744次
排名：千里之外
原创：34篇
评论：10条
(1)(1)(1)(3)(2)(1)(3)(2)(1)(1)(2)(8)(4)(7)