人工智能实验报告_八皇后问题.doc

八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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皇后问题 #include #include /采用启发式修补解N皇后问题 #include #include using .namespace std; void shuffle(int Queen,const int n) ./随机取得各行的初始皇后位置，以Queeni表示第i行的皇后位置 for(int i=0;in;i ) Queeni=abs(rand()%n; int collision(int Queen,const int row,const int column,const int n) . /计算每个位置的冲突值 int bug=0; for(int i=0;in;i ) . if (i!=row)&(Queeni=column|(Queeni-column)=(i-row) |(Queeni-column)=(row-i)/同列，同对角线的情况 bug ; return bug; void show(int Queen,const int n) ./打印皇后图 cout; for(int k=0;kn-1;k ) cout; coutendl; for(int i=0;in-1;i ) . cout; for(int j=0;jn;j ) cout(j=Queeni)? 凤 : );/有皇后的位置用凤 coutendl; cout; for(j=0;jn-1;j ) cout; coutendl; cout; for(int j=0;jn;j ) cout(j=Queenn-1)? 凤 : );/有皇后的位置用，没有的用_ coutendl; cout; for(k=0;kn-1;k ) cout; coutendl; coutendl; int repair(int Queen,const int n) . /启发式修补 int max=-1;/标志行行之间冲突数 int minbug=n; int count=0; while(max!=0&count=100) . max=0; for(int i=0;in;i ) . minbug=collision(Queen,i,Queeni,n);/取得当前的冲突数，不断优化 int temp=Queeni; for(int j=0;jn;j ) . int bug=collision(Queen,i,j,n); if(bugmax) max=minbug; show(Queen,n); count ; return count; void main() . int n=-1; int step=0; coutWelcome to N Queen Settlementendl; coutInput N (you would better input a interge minor to 15):n; if(n=0) . coutIllegal Input!endl; return; int* Queen=new intn; srand(time(NULL);/取得随机种子 shuffle(Queen,n); coutThe oringinal state:100) . coutCould find solution within 1