八皇后实验报告-3

第1页/共5页实验名称：编程实现八皇后问题（验证性实验）实验目标：使用深度优先搜索算法以及回溯法的思想进行暴力解题实验任务：用8*8的二维数组去模拟皇后所在的棋盘，然后用1标记该位置可以放皇后，用0来标记该位置不可以放皇后。然后每次有一个合理的八皇后方案，就会counter++，记录摆放的方法，并且输出皇后摆放的坐标。实验步骤：1.明确实验目标和实验任务2.理解实验所涉及到深度优先搜索的算法以及回溯法的思想3.编写程序实现求解八皇后问题。4.设计实验数据数据并运行程序，记录运行的结果程序代码:/***********************************************************************这个题目我默认第一个皇后放第一行，第二个皇后放第二行，如此类推。***********************************************************************/#include<iostream>usingnamespacestd;structchessboard{ intb[8][8];//对棋盘的模拟};structlocation{ intx,y;//记录皇后放的坐标};chessboardvisited[9];locationloc[8];intnum;//记录有多少种方法voidprint()//输出皇后的方法以及种数{ 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;//用于标记坐标voidvisit(intx,inty,intstep){ inti; x1=x; y1=y; x2=x; y2=y; visited[step]=visited[step-1];//把上一次标记过不能走的坐标传到下一次 for(i=0;i<8;i++) { visited[step].b[x][i]=0;//与皇后同行的都标为不能放 visited[step].b[i][y]=0;//与皇后同列的都标为不能放 } while(x1<8&&y1<8) { visited[step].b[x1][y1]=0;//与皇后对角线的标记为不能放 x1++; y1++; }while(x2<8&&y2>=0) { visited[step].b[x2][y2]=0;//与皇后对角线的标记为不能放 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);//进行标记 dfs(step+1);//递归进行下一个 } } }}intmain(){ num=0;//初始化计数变量num memset(visited,1,sizeof(visited));//初始化visited标记数组 dfs(1);//从1开始，1作为步骤参数 return0;}数据测试：实验小结：首先是八皇后问题。关于八皇后问题，主要是先对回溯法进行理解。毕竟理解不了回溯法，就无法写递