算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：用回溯法解決八皇后問(wèn)題姓名：學(xué)號(hào)：江蘇科技大學(xué)一、實(shí)驗(yàn)名稱：回溯法求解8皇后問(wèn)題二、學(xué)習(xí)知識(shí)：回溯算法的根本思想是：從一條路往前走，能進(jìn)那么進(jìn)，不能進(jìn)那么退回來(lái)，換一條路再試?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解的空間樹(shù)。算法搜索至解的空間樹(shù)的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含，那么跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹(shù)的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否那么，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕?lái)求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問(wèn)題。三、問(wèn)題描述〔1〕使用回溯法解決八皇后問(wèn)題。8皇后問(wèn)題：在8*8格的棋盤上放置彼此不受攻擊的8個(gè)皇后。按照國(guó)際象棋的規(guī)那么，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。8后問(wèn)題等價(jià)于在8*8格的棋盤上放置8個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上?！?〕用高級(jí)程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)四、求解思路ProcedurePLACE(k) //如果一個(gè)皇后能放在第k行和X(k)列，那么返回true，否那么返回false。X是一個(gè)全程數(shù)組，進(jìn)入此過(guò)程時(shí)已置入了k個(gè)值。ABS(r)過(guò)程返回r的絕對(duì)值// globalX(1:k);integeri,k; i1 whilei<kdo ifX(i)=X(k)orABS(X(i)-X(k))=ABS(i-k)then return(false) endif ii+1 repeat return(true)EndPLACEProcedureNQUEENS(n) //此過(guò)程使用回溯法求出一個(gè)n*n棋盤上放置n個(gè)皇后，使其不能互相攻擊的所有可能位置// integerk,n,X(1:n) X(1)0;k1//k是當(dāng)前行；X(k)是當(dāng)前列// whilek>0do//對(duì)所有的行，執(zhí)行以下語(yǔ)句// X(k)X(k)+1//移到下一列// whileX(k)<=nandNotPLACE(k)do//此處能放這個(gè)皇后嗎// X(k)X(k)+1//不能放那么轉(zhuǎn)到下一列// repeat ifX(k)<=nthen//找到一個(gè)位置// ifk=nthenprint(X)//是一個(gè)完整的解那么打印這個(gè)數(shù)組// elsekk+1;X(k)0//否那么轉(zhuǎn)到下一行// endif elsekk-1//回溯// endif repeatEndNQUEENS五、算法實(shí)現(xiàn)本實(shí)驗(yàn)程序是使用C#編寫，算法實(shí)現(xiàn)如下：1.queen類—實(shí)現(xiàn)8皇后問(wèn)題的計(jì)算，將結(jié)果存入數(shù)組。usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Collections;namespace_8Queen{publicclassQueen{publicstaticArrayListarr=newArrayList();//存放查詢結(jié)果privatestaticbool[]columflag=newbool[8]{true,true,true,true,true,true,true,true};//列占用標(biāo)記true為可用privatestaticbool[]leftflag=newbool[15]{true,true,true,true,true,true,true,true,true,true,true,true,true,true,true};//左行對(duì)角線占用標(biāo)記privatestaticbool[]rightflag=newbool[15]{true,true,true,true,true,true,true,true,true,true,true,true,true,true,true};//右行對(duì)角線占用標(biāo)記privatestaticint[,]position=newint[,]{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};//皇后位置坐標(biāo)publicstaticintsum=0;publicstaticvoidTryStep(inti)//i取值1至8{for(intj=1;j<=8;j++){if(columflag[j-1]&&leftflag[i+j-2]&&rightflag[i-j+7])//如果當(dāng)前位置可以放置{columflag[j-1]=false;leftflag[i+j-2]=false;rightflag[i-j+7]=false;//占用position[i-1,j-1]=1;//參加皇后位置if(i<8)TryStep(i+1);//進(jìn)入下一行else{int[,]position1=newint[8,8];//皇后位置坐標(biāo)àfor(intm=0;m<8;m++)//打印解法{for(intn=0;n<8;n++)position1[m,n]=position[m,n];}arr.Add(position1);intt=arr.Count;sum++;//解法數(shù)統(tǒng)計(jì)}columflag[j-1]=true;//如果不能放置時(shí)，取消占座及移走皇后leftflag[i+j-2]=true;rightflag[i-j+7]=true;position[i-1,j-1]=0;}}}}}2.圖形界面Form1usingSystem;usingSystem.Collections.Generic;usingSystemponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;namespace_8Queen{publicpartialclassForm1:Form{publicForm1(){InitializeComponent();run();}privatePictureBox[,]card;privateintrows;//行數(shù)privateintcols;//列數(shù)privateintsize=8;publicintindex=0;publicintsum;privatevoidrun()//初始化動(dòng)態(tài)加載8*8的PictureBox控件，作為棋盤{rows=size;cols=size;this.card=newPictureBox[rows,cols];this.panel1.Controls.Clear();for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){this.card[i,j]=newPictureBox();this.card[i,j].Location=newSystem.Drawing.Point(70*j,70*i);this.card[i,j].Name=i.ToString()+j.ToString();this.card[i,j].Size=newSystem.Drawing.Size(70,70);this.panel1.Controls.Add(card[i,j]);}}Queen.TryStep(1);sum=Queen.arr.Count;for(intf=1;f<=sum;f++){thisboBox1.Items.Add(f);}comboBox1.SelectedIndex=0;label3.Text=sum.ToString();setPictureBox();}publicvoidsetPictureBox()//布局，放置皇后{int[,]p=(int[,])Queen.arr[index];for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){if(((i%2)!=(j%2))){if(p[i,j]==0)this.card[i,j].Image=Image.FromFile("..\\..\\picture\\背景\\3.jpg");elsethis.card[i,j].Image=Image.FromFile("..\\..\\picture\\背景\\1.jpg");}else{if(p[i,j]==0)this.card[i,j].Image=Image.FromFile("..\\..\\picture\\背景\\4.jpg");elsethis.card[i,j].Image=Image.FromFile("..\\..\\picture\\背景\\2.jpg");}}}}privatevoidnext_Click(objectsender,EventArgse)//點(diǎn)擊“下一個(gè)〞按鈕{index++;if(index+1>sum){index=0;MessageBox.Show("結(jié)束！共"+sum+"種方案?");}setPictureBox();comboBox1.Text=(index+1).ToString();comboBox1.SelectedIndex=index;}privatevoidcomboBox1_SelectedIndexChanged(objectsender,EventArgse)//選擇某一個(gè)方案{index=comboBox1.SelectedIn