八皇后
- 格式：doc
- 大小：254.00 KB
- 文档页数：7
内容摘要
八皇后问题是十九世纪著名数学家高斯于1850年提出的。
问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。
可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。
回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。
关键词：八皇后问题；回溯法；探索；选优；试探法；
目录
1.引言 (1)
1.1研究的缘起 (1)
1.2本文的研究思路、方法及意义 (1)
1.3相关理论基础 (1)
2.实验过程分析 (1)
2.1算法描述 (1)
2.2实验工具 (1)
3.结果与讨论 (1)
3.1算法分析 (1)
3.2研究与结论 (3)
4.设计体会 (5)
5.参考文献 (5)
1.引言
1.1研究的缘起
在8X8格的国际象棋棋盘上放置8个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45°或135°的斜线）上不得有两个或两个以上的皇后。
这样的一个格局称为问题的一个解。
请用回溯算法写出求皇后问题的算法。
1.2本文的研究思路、方法及意义
每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1≤i≤n且1≤xi≤n，即第n个皇后放在第i行第xi列上。
由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:xi≠xj;若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件：i-j=xi-xj；在棋盘上斜率为1的斜线上，满足条件：i+j=xi+xj；
综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X
必须满足的约束条件为:|i-xi|≠|j-xj|；
显然，八皇后问题就可以根据解n皇后的这个思路去解决。
1.3相关理论基础
1.if语句的各种形式的运用。
2.for循环语句的层层嵌套。
3.do ｛｝while；语句的运用。
4.简单的输出。
5.定义常量。
2.实验过程分析
2.1算法描述
运用for循环的层层嵌套和if语句相结合，以及do while语句实现回溯法的算法，来解决八皇后问题。
当然，n皇后问题也是可以完成的。
2.2实验工具：Microsoft Visual C++ 6.0和截图工具。
3.结果与讨论
3.1分析与讨论
#include<stdio.h> //定义头文件
#define Q 8 //定义Queens为常量8，以便求解8皇后问题
int s[Q+1]; //算皇后所在每一行位置，从1开始
int main() //主函数
{
int i,k,j,unfinished=1,n=0; //定义相关所需变量
i=1; //赋初值
s[1]=1;
printf("There are some solutions of eight queens puzzle:\n");
do //unfinshed=1:处理未结束
{
do //处理未结束
{
for(k=1,j=1;j&&k<i;k++) //判断是否有两个或两个以上的皇后在同一行if(s[k]==s[i])
j=0;
for(k=1;j&&k<i;k++) //判断是否有多个皇后在对角线
if((s[i]==s[k]-(k-i))||(s[i]==s[k]+(k-i)))
j=0;
if(!j) //若存在矛盾,重设第i个元素
{
if(s[i]==s[i-1])
{
i--; //退回一步，重新试探处理前一个元素if(i>1&&s[i]==Q)
s[i]=1; // 当s[i]为Q时,将s[i]的值重置
else if(i==1&&s[i]==Q) //当第一未位的值达到Q时结束
unfinished=0;
else
s[i]++;
}
else if(s[i]==Q)
s[i]=1;
else
s[i]++;
}
else if(i++<=Q) //若前一个元素的值为Q
if(s[i-1]==Q)
s[i]=1;
else
s[i]=s[i-1]+1; //否则元素为前一个元素的下一个值
}while(unfinished&&i<Q+1);
if (unfinished)
{
n++;
printf((n-1)%10?"第%2d种解:":"\n第%2d种解:",n);
for(k=1;k<=Q;k++) //输出结果
printf("(%d,%d) ",k,s[k]);
printf("\n");
if(s[Q-1]<Q)
s[Q-1]++;
else
s[Q-1]=1;
i=Q-1;
}
}while(unfinished);
return 0;
}
3.2研究与结论运行结果：
分析：运用回溯法，可以的算出这92种解，但是有一些解是对称的，也就是说总的来说只有12种解。
4.设计体会
八皇后问题运用回溯法来解决是一个不错的方法，需要的是对回溯法具有一定的了解后，通过缜密的思考来想出对应的解决方案（算法），在运用C语言编程来实现算法。
经过一年来对C语言的学习，我认为实现算法的操作并不难，难的是脑子里所思考出来的算法。
算法分很多种，每个人都有不同的想法，不一定想到的就是最好的，但是毕竟是想到了，这是很难得的。
其实，只要想出了相对应的算法，即使再复杂。
我相信，可以通过继续思索来将算法进一步优化，最终达到一个可以接受的、相对合理的方案。
我通过运用for循环的层层嵌套和if语句相结合，以及do while语句实现回溯法的算法，来解决八皇后问题。
我想到的算法一开始是蛮复杂的，但是经过我的一些优化，让算法简单了一些。
还有的就是，程序的艺术性。
很多for循环语句和if语句的层层嵌套，让程序看起来会难看些，需要的是合理的编排和整序。
甚至是输出的结果，我也通过对程序进行一些小改变让输出的结果看起来清晰，这样不仅益于我检查错误，也能让看程序的人清晰的理解。
通过这次的编程，我感受到了人的思维是有限的，算法却是无穷的，没有最后，只有更好。
而今，我所需要的是多思考算法，了解、深究算法，让程序更加完美、可观。
5.参考文献
1.算法与数据结构【第4 章】，张乃孝，高等教育出版社
2.计算机算法与设计分析（第 3 版），王晓东，电子工业出版社。
