看了数据结构的课设题目,感觉这个最简单了.只要一个算法就可以,比起那些什么什么系统之类的简单多了.正要想办法解决的时候,一个兄弟把网上找的一个八皇后问题的源程序弄了过来.我正在犹豫要不要COPY的时候,那兄弟说,这个有点问题,你帮忙看看吧...哈哈...原来是有问题的啊,问题解决了那就不算是剽窃了....拿来一看只是个语法问题,郁闷下,改完了马上还给的那位兄弟...
我接着看那运行结果的时候,感觉好像有点问题,八皇后怎么会只有46种解,应该有92种解吧...哈哈,狂喜...原来还有逻辑错误...改完了不就是我的了(有点剽窃的嫌疑哈)....于是,把程序读了几遍,发现了问题所在,借用原来作者的算法,重新用C++写一遍...链接...运行...哈哈,92种结果全出来了...
八皇后问题
要求:试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法,并给出所有的解。
提示:在国际象棋上放置皇后时,任何一个皇后的水平、竖直和斜45º都不能有另一个皇后。解决该问题采用逐次试探的方法,即采用递归调用putchess函数的方法。首先将第一个皇后放于第一行第一列,然后开始向下一行递归。每一步递归中,首先检测待放置位置是否与已放置的皇后冲突,如不冲突,则进行下一行的放置,否则,选择该行的下一个位置进行检测。如整行的位置都冲突,则回到上一行,重新选择位置
源码:
/*
line[i]=j:表示第i行的棋子摆在第j列;
line[i]==line[t]:表示在同一列上有两颗棋子;
line[i]+i==line[t]+t:表示在右上或左下有两颗棋子;
line[i]-i==line[t]-t:表示在左上或右下有两颗棋子;
*/
#include<iostream> using namespace std;
int line[8],answer=0; void show()//显示摆放的结果. { int i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { if(line[i]==j) cout<<"Q"; else cout<<"*"; } cout<<endl; } answer++; cout<<endl; cout<<answer<<endl; getchar(); } int Judge(int t)//判断摆放的位置是否正确,不正确返回1,正确返回0. { int i,n=0; for(i=0;i<t;i++) { if(line[i]==line[t]) {n=1;break;} if(line[i]+i==line[t]+t) {n=1;break;} if(line[i]-i==line[t]-t) {n=1;break;} } return n; } void control(int n)//主要控制函数. { int t=8; for(line[n]=0;line[n]<t;line[n]++) { if(Judge(n)) continue; else if(n!=7) control(n+1); else show(); } } int main()//主函数. { control(0); cout<<answer<<endl; return 0; }
|
发现关注这个的人挺多的啊。。。把格式改的清楚点,顺便加点注释。
阅读(5295) | 评论(7) | 转发(0) |