八皇后问题的实现(从简单到难得各种解法)

《八皇后问题的实现(从简单到难得各种解法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八皇后问题的实现（C语言）  八皇后问题主要靠回溯的方法实现,与迷宫的实现相似,但又困难了一些.如迷宫的路径不因为上一步而改变,八皇后的每一步都受约束于以前的步数,并且,迷宫只要找出一条路径就行,但八皇后则有很多的解法.等等.#include#defineN8          //定义棋盘的格数,通过改变,也可以是4皇后,16皇后,9皇后什么的.intchess[N][N]={0};//棋盘intcount=0;//有多少种放法intcanput(introw,intcol)//确定某一格能不能放{inti,j;for(i=0;i

2、if(chess[i][col]==1)//有同列的  {   return0;  }  for(j=0;j

3、

4、(i-row)==(col-j))&&chess[i][j]==1)//对角线上有的   {    return0;   }  }}return1;}voidprint_chess()//打印放置的方案{inti,j;for(i=0;i

5、printf("%d",chess[i][j]);  }  printf("");}printf("");}intput(introw)    //放置棋子,row是从哪一行开始,通常是0{intj,s;for(j=0;j

6、   count=count+1;   print_chess();    chess[row][j]=0;//成功后,寻找下一种方法    continue;   }   s=put(row+1);//放置下一行的   if(s==0)   //假如下一行不能放   {    chess[row][j]=0;//那么这格是放错了的,清除    continue;          //找本行的下一个方格   }   else   {    break;   }     }}if(j==N)   //如果这一行的每个空格都不能放置{  return0;//那么本行放置失

7、败}else{  return1;//本行放置成功}}intmain(){ints;s=put(0);//放置printf("thenumberofputwayis%d",count);//打印信息return0;}    这个程序有个奇怪的地方,就是在有星号的那一行,当把chess[row][j]=0,continue;两句去掉时,发现程序依然能正常运行.原因就是:当行比列多时,假如皇后是的数目是列那么多,是肯定放不成功的,所以,当程序要在最后一行的下一行放皇后时,怎么放也不成功,所以,程序会不断调整以前的方法,但打印信息却在这里执行,所以能打出正确信息.但不建议

8、去掉,因为操作未知内存终究不是件好事.盲目的枚举法#include#includeintcheck(inta[],intn){inti,j;for(i=2;i<=n;i++)for(j=1;j<=i-1;j++)if((a[i]==a[j])

9、

10、(abs(a[i]-a[j])==abs(i-j)))return(0);return(1);}voidqueen1(){inti;inta[9];for(a[1]=1;a[1]<=8;a[1]++)for(a[2]=1;a[2]<=8;a[2]++)for(a[3]=1;a[3]<=8;a

11、[3]++)for(a[4]=1;a[4]<=8;a[4]++)for(a[5]=1;a[5]<=8;a[5]++)for(a[6]=1;a[6]<=8;a[6]++)for(a[7]=1;a[7]<=8;a[7]++)for(a[8]=1;a[8]<=8;a[8]++){if(check(a,8)==0)continue;elsefor(i=1;i<=8;i++)printf("%d",a[i]);printf("");}}intmain(intargc,char**argv){queen1();return0;}#include<