第1頁/共5頁實驗名稱：編程實現(xiàn)八皇后問題（驗證性實驗）實驗?zāi)繕?biāo)：使用深度優(yōu)先搜索算法以及回溯法的思想進行暴力解題實驗任務(wù)：用8*8的二維數(shù)組去模擬皇后所在的棋盤，然后用1標(biāo)記該位置可以放皇后，用0來標(biāo)記該位置不可以放皇后。然后每次有一個合理的八皇后方案，就會counter++，記錄擺放的方法，并且輸出皇后擺放的坐標(biāo)。實驗步驟：1.明確實驗?zāi)繕?biāo)和實驗任務(wù)2.理解實驗所涉及到深度優(yōu)先搜索的算法以及回溯法的思想3.編寫程序?qū)崿F(xiàn)求解八皇后問題。4.設(shè)計實驗數(shù)據(jù)數(shù)據(jù)并運行程序，記錄運行的結(jié)果程序代碼:/***********************************************************************這個題目我默認第一個皇后放第一行，第二個皇后放第二行，如此類推。***********************************************************************/#include<iostream>usingnamespacestd;structchessboard{ intb[8][8];//對棋盤的模擬};structlocation{ intx,y;//記錄皇后放的坐標(biāo)};chessboardvisited[9];locationloc[8];intnum;//記錄有多少種方法voidprint()//輸出皇后的方法以及種數(shù){ inti; cout<<++num<<ends; for(i=0;i<=7;i++) { cout<<loc[i].x<<ends<<loc[i].y<<ends; } cout<<endl;}intx1,y1,x2,y2;//用于標(biāo)記坐標(biāo)voidvisit(intx,inty,intstep){ inti; x1=x; y1=y; x2=x; y2=y; visited[step]=visited[step-1];//把上一次標(biāo)記過不能走的坐標(biāo)傳到下一次 for(i=0;i<8;i++) { visited[step].b[x][i]=0;//與皇后同行的都標(biāo)為不能放 visited[step].b[i][y]=0;//與皇后同列的都標(biāo)為不能放 } while(x1<8&&y1<8) { visited[step].b[x1][y1]=0;//與皇后對角線的標(biāo)記為不能放 x1++; y1++; }while(x2<8&&y2>=0) { visited[step].b[x2][y2]=0;//與皇后對角線的標(biāo)記為不能放 x2++; y2--; }}voiddfs(intstep){ intj; if(step==9) { print(); } else { for(j=0;j<8;j++) { if(visited[step-1].b[step-1][j]) { loc[step-1].x=step-1;//放置皇后的位置 loc[step-1].y=j; visit(step-1,j,step);//進行標(biāo)記 dfs(step+1);//遞歸進行下一個 } } }}intmain(){ num=0;//初始化計數(shù)變量num memset(visited,1,sizeof(visited));//初始化visited標(biāo)記數(shù)組 dfs(1);//從1開始，1作為步驟參數(shù) return0;}數(shù)據(jù)測試：實驗小結(jié)：首先是八皇后問題。關(guān)于八皇后問題，主要是先對回溯法進行理解。畢竟理解不了回溯法，就無法寫遞