人工智能实验报告-八皇后问题

八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。基本思想：在open表中保留已生成而未考察的结点，并用启发函数h(x)对它们全部进行估价，从中选出最优结点进行扩展，而不管这个结点出现在搜索树的什么地方。（1）把初始结点S0放入open表中，计算h(S0);（2）若open表为空，则搜索失败，EXIT；（3）移出open表中第一个结点N放入closed表中,并冠以序号n（4）若目标结点Sg=N则搜索成功，EXIT（5）若N不可扩展，则转步骤（2）；（6）扩展N，计算每个子结点x的函数值h(x)，并将所有子结点配以指向N的返回指针后放入open表中，再对open表中的所有子结点按其函数值大小以升序排序，转步骤2；//采用启发式修补解N皇后问题#includetime.h#includeiostream//采用启发式修补解N皇后问题#includetime.h#includeiostreamusing...namespacestd;voidshuffle(intQueen[],constintn)...{//随机取得各行的初始皇后位置，以Queen[i]表示第i行的皇后位置for(inti=0;in;i)Queen[i]=abs(rand())%n;}intcollision(intQueen[],constintrow,constintcolumn,constintn)...{//计算每个位置的冲突值intbug=0;for(inti=0;in;i)...{if((i!=row)&&(Queen[i]==column||(Queen[i]-column)==(i-row)||(Queen[i]-column)==(row-i)))//同列，同对角线的情况bug;}returnbug;}voidshow(intQueen[],constintn)...{//打印皇后图cout╭;for(intk=0;kn-1;k)cout─┬;cout─╮endl;for(inti=0;in-1;i)...{cout│;for(intj=0;jn;j)cout((j==Queen[i])?凤:)│;//有皇后的位置用凤coutendl;cout├;for(j=0;jn-1;j)cout─┼;cout─┤endl;}cout│;for(intj=0;jn;j)cout((j==Queen[n-1])?凤:)│;//有皇后的位置用，没有的用_coutendl;cout╰;for(k=0;kn-1;k)cout─┴;cout─╯endl;coutendl;}intrepair(intQueen[],constintn)...{//启发式修补intmax=-1;//标志行行之间冲突数intminbug=n;intcount=0;while(max!=0&&count=100)...{max=0;for(inti=0;in;i)...{minbug=collision(Queen,i,Queen[i],n);//取得当前的冲突数，不断优化inttemp=Queen[i];for(intj=0;jn;j)...{intbug=collision(Queen,i,j,n);if(bug=minbug&&j!=temp)...{//保持皇后在等冲突的情况下不断变更位置，有利于后面行的优化minbug=bug;Queen[i]=j;}}if(minbugmax)max=minbug;}show(Queen,n);count;}returncount;}voidmain()...{intn=-1;intstep=0;coutWelcometoNQueenSettlementendl;coutInputN(youwouldbetterinputaintergeminorto15):endl;cinn;if(n=0)...{coutIllegalInput!endl;return;}int*Queen=newint[n];srand(time(NULL));//取得随机种子shuffle(Queen,n);coutTheoringinalstate:endl;show(Queen,n);step=repair(Queen,n);if(step100)...{coutCouldfindsolutionwithin100steps,Tryagain!endl;return;}coutAfterstep1stepsendl;coutThegoalstatearrives!endl;}