八皇后问题及解答.docx
- 文档编号:5917464
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:9
- 大小:16.84KB
八皇后问题及解答.docx
《八皇后问题及解答.docx》由会员分享,可在线阅读,更多相关《八皇后问题及解答.docx(9页珍藏版)》请在冰点文库上搜索。
八皇后问题及解答
八皇后问题
问题描述:
在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相冲突
(在每一横列,竖列,斜列只有一个皇后)。
求解:
标 题:
八皇后问题的解(回溯法程序代码)
发信站:
网易虚拟社区 (Fri Jul 14 10:
06:
52 2000), 站内信件
以前上学的时候,写8皇后程序的时候偷懒用最笨的算法,在8086上计算十皇后
的时候,我放了张纸条,说明计算机正在运行,然后去吃饭,吃完以后,才看到
结果。
前几天,刚好有空,所以重写了一次,以补当年的遗憾。
#include "stdio.h"
int attacked(int *array,int position){
int flag=-1;
float step;
if(position==1) return flag;
for(step=1.00;step if(*(array+(int)step)==*(array+position)||step==position)return 1; if(((*(array+(int)step)-*(array+position))/(step-position))==1||((* (array+(int)step)-*(array+position))/(step-position))==-1){ flag=1; break; } } returnflag; } voidmain(void){ intcountSum,queenSum,printCount,*queenArray,queenPosition=0; inttempArray[20]={6666,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; countSum=1; queenArray=tempArray; printf("inputyouqueenSumhere: "); scanf("%d",&queenSum); fflush(stdin); if(queenSum<4){ printf("the%dqueen'ssumis0\n",queenSum); return; } for(;;){ if(countSum if(countSum==1&&*(queenArray+countSum)==1)countSum++; if(attacked(queenArray,countSum)==1){ if(*(queenArray+countSum)>=queenSum){ if(*(queenArray+countSum-1) ++*(queenArray+(--countSum)); *(queenArray+countSum+1)=0; } else{ *(queenArray+countSum--)=0; if(*(queenArray+countSum) else{ if(countSum==1&&*(queenArray+countSum)==queenSum)break; *(queenArray+countSum--)=0; ++*(queenArray+countSum); } } } else ++*(queenArray+countSum); } else ++*(queenArray+(++countSum)); } else{ if(attacked(queenArray,countSum)==1){ if(*(queenArray+countSum)>=queenSum){ if(*(queenArray+countSum-1) ++*(queenArray+(--countSum)); *(queenArray+countSum+1)=0; continue; } else{ *(queenArray+countSum--)=0; if(*(queenArray+countSum) else{ *(queenArray+countSum--)=0; ++*(queenArray+countSum); } continue; } } else{ ++*(queenArray+countSum); continue; } } queenPosition++; for(printCount=1;printCount<=queenSum;printCount++) printf("%3d%",*(queenArray+printCount)); if(printCount>=queenSum) printf("\n"); if(*(queenArray+countSum)>=queenSum){ ++*(queenArray+(--countSum)); //the "++" priority is different from turbo C *(queenArray+countSum+1)=0; } ++*(queenArray+countSum); } } printf("the %d queen's sum is %d\n",queenSum,queenPosition); } -- 谁能告诉我! ! 现在完成一件耗日持久的事后,不再象以前有轻松的感觉? ? #include #include #include int NUM = 0; void FindQuePos(int *posArray, int queen_num,int deep) { int i; if(deep == queen_num) { for(i = 0;i < queen_num;i++) printf("(%d,%d) ",i+1,posArray[i]+1); printf("\n"); NUM++; } else { int j,check; for(j = 0;j < queen_num; j++) { check = 1; for(i = 0;i < deep;i++) { if(posArray[i] == j || posArray[i] - j == i - deep || posArray[i] - j == deep - i) check = 0; } if(check) { int *posArray2; posArray2 = (int*)malloc(sizeof(int)*queen_num); for(i = 0;i < deep;i++) posArray2[i] = posArray[i]; posArray2[deep] = j; deep++; FindQuePos(posArray2,queen_num,deep); deep--; free(posArray2); } } } } int main(int argc,char **argv) { int *posArray; if(argc < 2) FindQuePos(posArray,8,0); else FindQuePos(posArray,atoi(argv[1]),0); printf("Have %d cases ! \n",NUM); } //8Queen递归算法 //如果有一个Q为chess[i]=j; //则不安全的地方是k行 j位置,j+k-i位置,j-k+i位置 classQueen8{ staticfinalintQueenMax=8; staticintoktimes=0; staticintchess[]=newint[QueenMax];//每一个Queen的放置位置 publicstaticvoidmain(Stringargs[]){ for(inti=0;i placequeen(0); System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 madebyyifi2003"); } publicstaticvoidplacequeen(intnum){//num为现在要放置的行数 inti=0; booleanqsave[]=newboolean[QueenMax]; for(;i //下面先把安全位数组完成 i=0;//i是现在要检查的数组值 while(i qsave[chess[i]]=false; intk=num-i; if((chess[i]+k>=0)&&(chess[i]+k if((chess[i]-k>=0)&&(chess[i]-k i++; } //下面历遍安全位 for(i=0;i if(qsave[i]==false)continue; if(num chess[num]=i; placequeen(num+1); } else{//numislastone chess[num]=i; oktimes++; System.out.println("这是第"+oktimes+"个解法如下: "); System.out.println("第n行: 12345678"); for(i=0;i Stringrow="第"+(i+1)+"行: "; if(chess[i]==0); else for(intj=0;j row+="++"; intj=chess[i]; while(j System.out.println(row); } } } //历遍完成就停止 } } C#解法 usingSystem; classQueen{ constintSIZE=8;//皇后数 publicstaticvoidMain() { int[]Queen=newint[SIZE];//每行皇后的位置 inty,x,i,j,d,t=0; y=0; Queen[0]=-1; while(true) { for(x=Queen[y]+1;x { for(i=0;i { j=Queen[i]; d=y-i; //检查新皇后是否与以前的皇后能相互攻击 if((j==x)||(j==x-d)||(j==x+d)) break; } if(i>=y) break;//不攻击 } if(x==SIZE)//没有合适的位置 { if(0==y) { //回朔到了第一行 Console.WriteLine("Done"); break;//结束 } //回朔 Queen[y]=-1; y--; } else { Queen[y]=x;//确定皇后的位置 y++;//下一个皇后 if(y Queen[y]=-1; else { //所有的皇后都排完了,输出 Console.WriteLine("\n"+++t+': '); for(i=0;i { for(j=0;j if(Queen[i]==j) Console.Write('Q'); else Console.Write('.'); Console.WriteLine(); } y=SIZE-1;//回朔 } } } } } 八皇后有解92个。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 解答