4、八皇后问题

数学与计算机学院 课程设计说明书

课 程 名 称: 算法设计与分析-课程设计 课 程 代 码: 7106620 题 目: 八皇后问题 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2010 年 12 月 27 日 完 成 时 间: 2011 年 01 月 07 日 课程设计成绩：

学习态度及平技术水平与实际能时成绩（30） 力（20） 创新（5） 说明书撰写质量（45） 总 分（100） 指导教师签名： 年 月 日

八皇后问题 目 录

1 引 言 .......................................................... 1

1.1 问题的提出......................................................................................................................... 1 1.2任务与分析 ......................................................................................................................... 1

2 程序的主要功能 ................................................... 1

2.1回溯功能............................................................................................................................. 1 2.2检查功能............................................................................................................................. 1

3 程序运行平台 .................................................... 2 4 总体设计 ........................................................ 2 4.1算法设计 ....................................................... 2 4.2流程设计 ....................................................... 3 5 模块分析 ........................................................ 4

5.1 回溯模块 ............................................................................................................................ 4 5.2 检查模块 ............................................................................................................................ 5

6 系统测试 ........................................................ 6 7 结论 ............................................................ 8 8 致谢 ............................................................ 9 9 参考文献 ....................................................... 10 附录 ............................................................ 11

八皇后问题 摘 要

本论文主要采用回溯法和递归法，求解著名的8皇后问题。即在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，也就是任意两个皇后都不能处于同一行、同一列或同一斜线上，求可行方案的总数。

问题的提出者高斯当时认为有76种方案，后来有人用图论的方法解出92种结果。本论文采用回溯法和递归法，在放置皇后之前，预先判断当前棋盘格子的所在行，列和主从对角线是否已存在皇后，如果存在，则右移一列进行相同判断，若右移至最后一列仍不可放，则行数加一列数回到第一列继续判断；如果不存在，则在当前格放置一个皇后，同时同行剩下的格子不再进行判断，行数加一列数回到第一列，如此递归进行，直至八个皇后全部符合要求地摆放完毕。当判断完最后一个格子后，皇后数仍小于8，则回溯到摆放上一个皇后的格子，将上一个皇后摆放在其下一列格子上，再继续上述相同的操作，直至8个皇后摆放完毕。

此程序不仅能求解八皇后问题，还能解决相同类型的N皇后问题。此外，代码简洁易懂，界面友好，便于操作。

关键词：n皇后，回溯，递归

八皇后问题 1 引 言

1.1 问题的提出

问题由十九世纪著名的数学家高斯提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯当时认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。试编写一个算法，求解并输出此问题的所有合法布局。

1.2任务与分析

求出在一个8×8的棋盘上，放置8个不能互相捕捉的国际象棋“皇后”的所有布局。皇后可以沿着纵横和两条斜线4个方向相互捕捉。输出所有符合要求的解。

分析：采用回溯法。例如：当前棋盘格子所在行数、列数分别为i，j，在放置皇后之前需判断i行，所有小于j的列是否存在皇后；i-1行j-1列和i-1行j+1列是否已存在皇后。若都不存在，则当前布局合法，可放置皇后；否则不可放置，以相同的方法继续判断i行j+1列是否为合法布局，当列数大于8时，行数加1，列数从1自增到8重新开始递归判断，若所有棋盘格子遍历完一次摆放的皇后数小于8，则回溯到上一个皇后的位置，将其移至下一列，再对剩余格子进行同上判断；若皇后数等于8，则说明找到一种可行方案，再继续使用回溯法寻找其他可行方案。

2 程序的主要功能

2.1回溯功能

若当前棋盘格子满足条件，则放置一个皇后，同时同行剩余的格子不再进行判断，即行数加一，列数从一到八递增，重新开始判断，进行下一个皇后的放置。如果所有的棋盘格子都遍历了完毕，但已放置的皇后数仍小于8，则回溯到上一个已放置的皇后，将其移至同行的下一列，再递归对剩余的皇后进行放置，直至八个皇后放完为止。

2.2检查功能

放置皇后之前对该格做预判断处理，即判断当前格子的所在行，所在列是否已存在皇后，如果不存在，再判断上一行同列的左右两列，即从对角线和主对角线上是否已存

-1-

八皇后问题 在皇后，如果都不存在则可以放置，反之则不可放置。

3 程序运行平台

WINDOWS XP/WIN 7 VC++6.0。

具体操作如下：进入Visual C++6.0开发环境,在开发环境的主窗口中选择File|New菜单项，在弹出的对话框中单击Project选项卡，选择C++ Source File，命名为“八皇后问题”，再制定保存路径，单击OK键完成新建。再在编辑窗口中编辑代码，编译，链接，执行，最后对其进行调试。

4 总体设计

4.1算法设计

check(int row,int line)//检验当前格是否可放 {

//row代表行，line代表列

if(Queen[i][line]==queen)//同列已存在queen

return false;

if(Queen[row][i]==queen)//同行已存在queen

return false;

if(Queen[i][j]==queen)//左上方已存在queen

return false;

if(Queen[i][j]==queen)//右上方已存在queen

return false;

return true;//同行同列，主从对角线都不存在queen}

backtrack(int n1,int n2)//回溯法，n1代表棋盘格数，n2代表王后数 {

if(n1>=n*n||n2==n)//棋盘是否放满或王后是否放完 {

if(n2==n)//王后放完 {

printf(\

}

}

else {

int row=n1 /n,line=n1 %n;//得到当前格子的所在行和列

-2-

八皇后问题 if(check(row,line))//如果可放，则放 {

Queen[row][line]=queen;//当前格置为queen backtrack(n1+1,n2+1);//放下一个queen Queen[row][line]=blank;//还原状态 }

} }

backtrack(n1+1,n2);//不可放，则检查下一格

4.2流程设计

总体设计的流程图如图4.1所示：

开 始 初始化 row=line=queen=0 row<8 N line<8 queen<8 Y row不满足 row++ line=0 N 判断行列主从对line或对角线不满足 角线是否有line++ queen Y 此格放queen row++ queen++ line=0 输出结果 结 束 图4.1 总体流程图

-3-

八皇后问题

5 模块分析

5.1 回溯模块

代码分析：

backtrack(int n1,int n2)//回溯法，n1代表棋盘格数，n2代表王后数 { }

-4-

char ch;

if(n1>=n*n||n2==n)//棋盘是否放满或王后是否放完 { } else { }

int row=n1 /n,line=n1 %n;//得到当前格子的所在行和列 if(check(row,line))//如果可放，则放 { }

backtrack(n1+1,n2);//不可放，则检查下一格

Queen[row][line]=queen;//当前格置为queen backtrack(n1+1,n2+1);//放下一个queen Queen[row][line]=blank;//还原状态 if(n2==n)//王后放完 { }

printf(\for(int i=0;i

ch=getchar(); printf(\

for(int j=0;j

printf(\

printf(\

八皇后问题 5.2 检查模块

检查模块流程图如图5.1所示：

N row<=8 line<=8 n<=8 退出 row++ j=0 Y Y Y 检查对角线是否有queen N j++ Y Y Y j++ 检查行是否有queen N 检查列是否有queen N j++ n++ 此格放置queen 图5.1检查模块流程图

代码分析：

check(int row,int line)//检验当前格是否可放 {

int i,j;

for(i=row-1;i>=0;i--)

if(Queen[i][line]==queen)//同列已存在queen

return false;

for(i=line-1;i>=0;i--)

if(Queen[row][i]==queen)//同行已存在queen

return false;

for(i=row-1,j=line-1;(i>=0)&&(j>=0);i--,j--)

if(Queen[i][j]==queen)//左上方已存在queen

return false;

for(i=row-1,j=line+1;(i>=0)&&(j

-5-

八皇后问题

if(Queen[i][j]==queen)//右上方已存在queen

return false;

return true;//同行同列，主从对角线都不存在queen

}

6 系统测试

运行结果：

图1摆放方案

图 2摆放方案

-6-

八皇后问题

图 3摆放方案

图 4摆放方案

从上述结果可知，此程序能够很好地解决八皇后问题，以至于解决n皇后问题，并能够将运行结果以友好的界面呈现在用户面前，能够方便用户的使用，所以说此次设计还是比较成功的。

-7-

八皇后问题 7 结论

回溯法号称算法中“通用的解题方法”。此次课程设计通过回溯法不仅能成功地解决八皇后问题，还能解决n皇后问题。经过此次对八皇后问题的解决，再次加深了我对这种思想的理解。

刚开始拿到题的时候，虽然对题早有耳闻，但不曾亲自解决过，同时也无从下手。

通过查阅资料，总结了几种较为常见的算法，在递归与非递归中，最后选择了较为通用的递归算法。在程序设计时，在该用一维数组还是二维数组问题上困惑了很久，但最终选择了较容易让人理解的二维数组进行解题。此程序有以下几大优点：1、代码简练易懂；2、界面友好，方便用户使用；3、不仅能成功地解决八皇后问题，还能解决同类型的N皇后问题。

-8-

八皇后问题

8 致谢

首先需要感谢的是指导老师谢春芝老师，在她的督促下才能按时完成这个课程设计，并且对于各种提出的问题很热情的解答。再者需要感谢的是交过我C语言的王秀华老师，没有她的教导自然就不可能有基础来完成课程设计了。整个完成的过程中周围的同学给了不少帮助，而且帮忙解决了很多想不通的问题，在此真的非常感激每个人！有进步是因为有帮助！

-9-

八皇后问题

9 参考文献

[1] 严蔚敏 吴伟民 著. 《数据结构》（C语言版）(第三版). 北京：清华大学出版社2007.4

[2] 谭浩强 著. 《C程序设计》(第三版).北京：清华大学出版社；2006.9 [3] Anany Levitin 著. 潘彦 译 《算法设计与分析基础》(第二版).北京：清华大学出版社；2010.1

[4] [美] S巴斯 著.计算机算法：设计和分析引论. 朱洪等译 上海：复旦大学出版社；1985.1

-10-

八皇后问题

附录

#include #define MAX 20

char Queen[MAX][MAX]; enum {blank ='.',queen = 'Q'}; int n;

int total=0;

int check(int row,int line)//检验当前格是否可放 {

int i,j;

for(i=row-1;i>=0;i--) if(Queen[i][line]==queen)//同列已存在queen

return false;

for(i=line-1;i>=0;i--) if(Queen[row][i]==queen)//同行已存在queen

return false;

for(i=row-1,j=line-1;(i>=0)&&(j>=0);i--,j--) if(Queen[i][j]==queen)//左上方已存在queen

return false;

for(i=row-1,j=line+1;(i>=0)&&(j

return false;

return true;//同行同列，主从对角线都不存在queen

}

void backtrack(int n1,int n2)//回溯法，n1代表棋盘格数，n2代表王后数 {

char ch;

if(n1>=n*n||n2==n)//棋盘是否放满或王后是否放完 {

if(n2==n)//王后放完 {

printf(\for(int i=0;i

for(int j=0;j

printf(\

printf(\}

ch=getchar(); printf(\

-11-

八皇后问题

} else {

}

int row=n1 /n,line=n1 %n;//得到当前格子的所在行和列 if(check(row,line))//如果可放，则放 {

Queen[row][line]=queen;//当前格置为queen backtrack(n1+1,n2+1);//放下一个queen Queen[row][line]=blank;//还原状态

}

backtrack(n1+1,n2);//不可放，则检查下一格

} }

void main() { }

printf(\ \scanf(\for(int i=0;i

backtrack(0,0);

printf(\关于 %d 王后的求解方法有 %d 种!\\n\

-12-

本文来源：https://www.bwwdw.com/article/zenv.html