人工智能论文-遗传算法实现八皇后问题

人工智能课程设计报告学号：20091000608姓名：王沙沙班级：191091指导老师：赵老师2011年10月14目录1．N皇后问题 (1)需求分析，设计 (1)设计表示 (1)运行结果 (2)用户手册即测试数据 (2)结论 (5)主要算法代码 (5)2罗马尼亚问题 (9)需求分析，设计 (9)设计表示，详细设计 (9)用户手册 (11)运行结果 (11)主要算法代码 (12)3.实习心得 (21)1 N 皇后问题1．问题描述、需求分析在N*N 的棋盘上分布N 个皇后，其中N 个皇后不能在同一行同一列，也不能出现在同一对角线上，此时N 个皇后不会相互攻击。

程序需能手动输入皇后个数，并分别采用回溯法、爬山法、遗传法得出皇后的分布情况，输出皇后的位置即棋盘。

2．设计思想2.1 形式化N 个皇后的位置可用一个N 维数组表示，如921543……，意思是第一个皇后在第一列的第9行。

2.2 程序模块CreatIndividual( )函数用于产生一组表示皇后不在同一行也不再同一列的的一位数组，即产生一组互不相等的0~N 之间的整数，便于快速求解。

IsLegal( )函数用于判断新放置的皇后是否合法，在回溯法中用到。

AttackQueenNum( )用于计算整个棋盘的攻击皇后个数，相当于一个评价函数，在爬山法和遗传法中用到；Find( )回溯法求解函数ClimbHill( )爬山法求解函数；GA( )遗传算法求解函数；（1）函数调用关系图如下：（2）函数接口规格说明：下图中的箭头指向表示为被指向函数所用2.3 详细设计a: CreatIndividual(int *A,int QueenNum)：以当时时间为种子循环产生随机数，为了使得产生的随机数都不想等，设计集合S[N]并初始化为0，表示还没有产生一个皇后，当产生的皇后不在S[N]中即S[N]！=1时将S[n]置为1，接着产生下一个皇后，如此循环便产生一组互不相等的值。

八皇后实验报告八皇后实验报告引言：八皇后问题是一个经典的数学问题，它要求在一个8x8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不会互相攻击。

这个问题看似简单，但实际上却充满了挑战。

在本次实验中，我们将探索八皇后问题的解法，并通过编写算法来解决这个问题。

一、问题背景：八皇后问题最早由数学家马克斯·贝瑟尔于1848年提出，它是一道经典的递归问题。

在国际象棋中，皇后可以在同一行、同一列或同一对角线上进行攻击，因此我们需要找到一种方法，使得8个皇后彼此之间不会相互攻击。

二、解决方法：为了解决八皇后问题，我们可以使用回溯法。

回溯法是一种穷举搜索的方法，它通过逐步尝试所有可能的解决方案，直到找到符合要求的解。

具体步骤如下：1. 初始化一个8x8的棋盘，并将所有格子标记为无皇后。

2. 从第一行开始，依次尝试在每一列放置一个皇后。

3. 在每一列中，检查当前位置是否符合要求，即与已放置的皇后不在同一行、同一列或同一对角线上。

4. 如果当前位置符合要求，将皇后放置在该位置，并进入下一行。

5. 如果当前位置不符合要求，尝试在下一列放置皇后。

6. 重复步骤3-5，直到找到一个解或者所有可能的位置都已尝试过。

7. 如果找到一个解，将其输出；否则，回溯到上一行，继续尝试下一列的位置。

三、编写算法：基于上述步骤，我们可以编写一个递归函数来解决八皇后问题。

伪代码如下所示：```function solveQueens(board, row):if row == 8:print(board) # 打印解returnfor col in range(8):if isSafe(board, row, col):board[row][col] = 1solveQueens(board, row + 1)board[row][col] = 0function isSafe(board, row, col):for i in range(row):if board[i][col] == 1:return Falseif col - (row - i) >= 0 and board[i][col - (row - i)] == 1:return Falseif col + (row - i) < 8 and board[i][col + (row - i)] == 1:return Falsereturn Trueboard = [[0]*8 for _ in range(8)]solveQueens(board, 0)```四、实验结果：通过运行上述算法，我们得到了八皇后问题的所有解。

算法设计与分析实验报告—八皇后问题-姓名：***学号：********班级：软件83【问题描述】在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。

【问题分析&算法设计】用8元组x[1: n]表示8后问题。

其中x[ i]表示皇后i放在棋盘的第i行的第x[ i]列。

由于不允许将2个皇后放在一列，所以解向量中的x[ i]互不相同。

2个皇后不能放在同一斜线上是问题的隐约束。

故若2个皇后放置的位置分别是（i，j）和（k，l），且i – j = k – l或i + j = k + l，则说明这2个皇后处于同一斜线上。

这两个方程分别等价于i – k = j – l和i – k = l – j。

由此可知，只要|i - k| = |j - l|成立，就表明2个皇后位于同一条斜线上。

问题的隐约束化成了显约束。

用回溯法解决8皇后问题时，用完全8叉树表示解空间。

【算法实现】#include "stdio.h"#include "math.h"#include "iostream.h"#define N 8 /* 定义棋盘大小*/static int sum; /* 当前已找到解的个数*/static int x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列*//* 每找到一个解,打印当前棋盘状态*/void Show(){sum++;cout << "第" << sum << "种情况：" << endl;cout << "坐标为:\t";for(int k = 0; k < N; k++)cout << '(' << k+1 << ',' << x[k] << ") ";cout << endl;cout << "---------------------------------\n";for (int i = 0; i < N; i ++){for (int j = 0; j < N; j ++)if (j == x[i]) //printf("@ ");cout << "* | ";else //printf("* ");cout << " | ";cout << "\n---------------------------------\n";}}/* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */int Judge(int k){// 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。

python八皇后问题递归算法Python八皇后问题递归算法是一种经典的算法，用于解决八皇后问题。

八皇后问题是一个典型的回溯算法问题，其目标是在一个8x8 的棋盘上放置 8 个皇后，使得每个皇后都不会攻击到其他的皇后。

在这个问题中，皇后可以攻击到同一行、同一列和同一对角线上的其他皇后。

因此，要解决这个问题，我们需要找到一种方法，使得每个皇后都能够在不攻击其他皇后的情况下放置在棋盘上。

递归算法是解决八皇后问题的一种常用方法。

在这种算法中，我们首先将皇后放置在第一行中的每个位置上，并递归地放置下一行的皇后，直到我们找到一种方案，其中每个皇后都不会攻击到其他皇后。

如果我们无法找到这样的方案，我们将回溯到前一行，并将前一行中的皇后移动到下一个位置上，继续递归寻找方案。

Python语言提供了丰富的库函数和语法特性，使得编写八皇后问题递归算法变得非常容易。

我们可以使用Python中的列表和循环语句来表示棋盘和皇后的位置，并使用递归函数来实现放置皇后和检查皇后位置的功能。

在编写递归函数时，我们需要注意以下几点：1. 递归函数的参数应该包括皇后的位置和当前行数。

2. 在放置皇后时，我们应该从左到右遍历每一列，并在每一列中检查皇后是否会攻击到其他皇后。

3. 如果当前行数达到8，说明我们已经找到了一种合法的方案，我们应该将其保存下来，并返回True，表示我们已经找到了一种方案。

4. 如果我们无法找到合法的方案，我们应该返回False，表示我们需要回溯到前一行。

最后，我们可以通过调用递归函数来解决八皇后问题，并输出所有合法的方案。

通过使用Python八皇后问题递归算法，我们可以更好地理解回溯算法和递归算法的工作原理，并提高我们的编程能力。

八皇后问题递归算法八皇后问题是一个经典的数学问题，其目标是在一个8×8的棋盘上放置8个皇后，使得没有两个皇后位于同一行、同一列或同一斜线上。

这个问题可以通过递归算法来求解，本文将详细介绍八皇后问题的递归算法及其实现过程。

我们需要定义一个函数来判断当前位置是否可以放置皇后。

该函数的输入参数为当前行和当前列，输出为一个布尔值，表示该位置是否可以放置皇后。

具体实现如下：```bool isSafe(int board[8][8], int row, int col){int i, j;// 检查当前列是否有其他皇后for (i = 0; i < row; i++)if (board[i][col])return false;// 检查左上方是否有其他皇后for (i = row, j = col; i >= 0 && j >= 0; i--, j--)if (board[i][j])return false;// 检查右上方是否有其他皇后for (i = row, j = col; i >= 0 && j < 8; i--, j++)if (board[i][j])return false;return true;}```接下来，我们可以使用递归算法来解决八皇后问题。

递归算法的思想是将问题分解为子问题，然后逐步解决子问题，最终得到原问题的解。

具体的递归算法如下：```bool solveNQueens(int board[8][8], int row){// 所有行都已经放置好了皇后，得到了一个解if (row == 8)return true;// 尝试在当前行的每个列中放置皇后for (int col = 0; col < 8; col++)// 检查当前位置是否可以放置皇后if (isSafe(board, row, col)){// 放置皇后board[row][col] = 1;// 递归求解下一行if (solveNQueens(board, row + 1))return true;// 回溯，撤销当前位置的皇后board[row][col] = 0;}}// 无法找到解return false;}```我们可以编写一个主函数来调用递归算法并打印结果。

八数码问题（一）问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。

这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。

现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。

该问题称八数码难题或者重排九宫问题。

（二）问题分析八数码问题是个典型的状态图搜索问题。

搜索方式有两种基本的方式，即树式搜索和线式搜索。

搜索策略大体有盲目搜索和启发式搜索两大类。

盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

1、启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。

所以引入启发式搜索策略。

启发式搜索就是利用启发性信息进行制导的搜索。

它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。

所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。

即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

启发函数设定。

对于八数码问题，可以利用棋局差距作为一个度量。

搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。

（三）数据结构与算法设计该搜索为一个搜索树。

为了简化问题，搜索树节点设计如下：struct Chess//棋盘{int cell[N][N];//数码数组int Value;//评估值Direction BelockDirec;//所屏蔽方向struct Chess * Parent;//父节点};int cell[N][N]; 数码数组：记录棋局数码摆放状态。

int Value; 评估值：记录与目标棋局差距的度量值。

Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。

回溯算法的实现（1）为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从1到8。

当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。

用语句实现，可定义如下三个整型数组：a[8],b[15],c[24]。

其中：a[j-1]=1 第j列上无皇后a[j-1]=0 第j列上有皇后b[i+j-2]=1 (i,j)的对角线（左上至右下）无皇后b[i+j-2]=0 (i,j)的对角线（左上至右下）有皇后c[i-j+7]=1 (i,j)的对角线（右上至左下）无皇后c[i-j+7]=0 (i,j)的对角线（右上至左下）有皇后（2）为第i个皇后选择位置的算法如下：for(j=1;j<=8;j++) /*第i个皇后在第j行*/if ((i,j)位置为空)）/*即相应的三个数组的对应元素值为1*/{占用位置（i,j）/*置相应的三个数组对应的元素值为0*/if i<8为i+1个皇后选择合适的位置；else 输出一个解}#include <graphics.h>#include <stdlib.h>#include <stdio.h>#include <dos.h>char n[3]={'0','0'};/*用于记录第几组解*/int a[8],b[15],c[24],i;int h[8]={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/int l[8]={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/void *arrow;void try(int i){int j;for (j=1;j<=8;j++)if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行为空*/{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*显示皇后图形*/delay(500);/*延时*/if(i<8) try(i+1);else /*输出一组解*/{n[1]++;if (n[1]>'9') {n[0]++;n[1]='0';}bar(260,300,390,340);/*显示第n组解*/outtextxy(275,300,n);delay(3000);}a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后，继续寻找下一组解*/ delay(500);}}int main(void){int gdrive=DETECT,gmode,errorcode;unsigned int size;inITgraph(&gdrive,&gmode,"");errorcode=graphresult();if (errorcode!=grOk){printf("Graphics error\n");exIT(1);}rectangle(50,5,100,40);rectangle(60,25,90,33);/*画皇冠*/line(60,28,90,28);line(60,25,55,15);line(55,15,68,25);line(68,25,68,10);line(68,10,75,25);line(75,25,82,10);line(82,10,82,25);line(82,25,95,15);line(95,15,90,25);size=imagesize(52,7,98,38); arrow=malloc(size);getimage(52,7,98,38,arrow);/*把皇冠保存到缓冲区*/clearviewport();settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);setusercharsize(3, 1, 1, 1);setfillstyle(1,4);for (i=0;i<=7;i++) a[i]=1;for (i=0;i<=14;i++) b[i]=1;for (i=0;i<=23;i++) c[i]=1;for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);/*画棋盘*/for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285);try(1);/*调用递归函数*/delay(3000);closegraph();free(arrow);}。

使⽤遗传算法和模拟退⽕算法解决⼋皇后问题本⽂测试内容主要包括：1）构建⼋皇后的类，类中包含有⼋皇后的属性矩阵、排列数组、评估函数数组等，以及实现各种基本功能的函数。

2）⽤模拟退⽕算法来解决⼋皇后问题，并测试什么样的参数和温度下降函数的求解效率⽐较⾼，分析模拟退⽕算法的优点和缺点。

3）设计遗传算法来解决⼋皇后问题，并测试什么样的参数的求解效率最⾼，分析遗传算法的优点与缺点。

先说结论，模拟退⽕算法和遗传算法都可以得到近似最优解，都收到参数设置的影响⽐较⼤，⽽模拟退⽕算法更可能找到最好的解，遗传算法可以得到最优解的近似解空间，该空间中有很多近似最优解。

本次使⽤的遗传算法是在传统算法的基础上做了⼀点点改进，改进内容如下：种群中每个个体产⽣的时候由内部竞争产⽣：1.⾸先有交叉互换产⽣两个⼦代个体C1,C22.如果没有发⽣交叉互换，则⽤亲本个体作为⼦代个体C1,C23.分别对两个⼦代个体进⾏变异操作。

4.选择C1、C2中适应值⾼的个体作为此次产⽣的个体。

该改进将⼤幅减⼩找到全局解所需要的世代数，如果不这样做会产⽣很多⼦代才能有解。

更多的细节和详细的代码请访问我的获取。

1.数据结构和基本操作⾸先进⾏⼋皇后类的设计，接着完成针对⼋皇后问题的模拟退⽕算法的设计和遗传算法的设计。

在类的设计中，要将⼋皇后封装起来，⼋皇后要设计属性：位置矩阵，并⽤⼀个⼀维数组来表⽰⼋个皇后的位置，最后再设计⼀个评估值矩阵，评估每个位置上可以被多少个皇后攻击的到。

我在这⾥设计了以下⼏个操作函数：1.初始化⽅法：把棋盘清零，⼋个皇后都暂时不摆放。

2.根据排列⽅法来确定queen属性的值。

内部先调⽤了⼀次 initial()，然后根据 state 数据成员往棋盘 board 放⼊ 8 个皇后。

3.随机赋值排列函数。

随机产⽣⼀个初始状态，赋值给 state 数据成员。

4.输出棋盘的函数。

5.输出棋盘评估函数值的函数。

打印当前棋盘的评估值函数数据成员。

八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。

该问题是十九世纪著名的数学家高斯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<time.h>#include <iostream>//采用启发式修补解N皇后问题#include<time.h>#include <iostream>using space std;void shuffle(int Queen[],const int n)...{//随机取得各行的初始皇后位置，以Queen[i]表示第i行的皇后位置for(int i=0;i<n;i )Queen[i]=abs(rand())%n;}int collision(int Queen[],const int row,const int column,const int n)...{ //计算每个位置的冲突值int bug=0;for(int i=0;i<n;i )...{if ((i!=row)&&(Queen[i]==column||(Queen[i]-column)==(i-row)||(Queen[i]-column)==(row-i)))//同列，同对角线的情况bug ;}return bug;}void show(int Queen[],const int n)...{//打印皇后图cout<<"╭";for(int k=0;k<n-1;k )cout<<"─┬";cout<<"─╮"<<endl;for(int i=0;i<n-1;i )...{cout<<"│";for(int j=0;j<n;j )cout<<((j==Queen[i])? "凤" :" ")<<"│";//有皇后的位置用"凤"cout<<endl;cout<<"├";for(j=0;j<n-1;j )cout<<"─┼";cout<<"─┤"<<endl;}cout<<"│";for(int j=0;j<n;j )cout<<((j==Queen[n-1])? "凤" :" ")<<"│";//有皇后的位置用，没有的用_ cout<<endl;cout<<"╰";for(k=0;k<n-1;k )cout<<"─┴";cout<<"─╯"<<endl;cout<<endl;}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;i<n;i )...{minbug=collision(Queen,i,Queen[i],n);//取得当前的冲突数，不断优化int temp=Queen[i];for(int j=0;j<n;j )...{int bug=collision(Queen,i,j,n);if(bug<=minbug&&j!=temp)...{ //保持皇后在等冲突的情况下不断变更位置，有利于后面行的优化minbug=bug;Queen[i]=j;}}if (minbug>max)max=minbug;}show(Queen,n);count ;}return count;}void main()...{int n=-1;int step=0;cout<<"Welcome to N Queen Settlement"<<endl;cout<<"Input N (you would better input a interge minor to 15):"<<endl;cin>>n;if(n<=0)...{cout<<"Illegal Input!"<<endl;return;}int* Queen=new int[n];srand(time(NULL));//取得随机种子shuffle(Queen,n);cout<<"The oringinal state:"<<endl;show(Queen,n);step=repair(Queen,n);if(step>100)...{cout<<"Could find solution within 100 steps,Try again!"<<endl;return;}cout<<"After "<<step 1<<" steps"<<endl;cout<<"The goal state arrives!"<<endl;}。

(2023)八皇后问题实验报告(一)实验背景八皇后问题，是一道经典的数学问题，简要地说：在一个 8x8 的国际象棋棋盘上摆放 8 个皇后，使其不能互相攻击。

即任意两个皇后都不能处于同一行、同一列或同一斜线上。

实验目的1.理解并掌握八皇后问题的基础算法；2.利用Python编写程序，解决八皇后问题；3.掌握递归算法与回溯算法的基本思想；4.分析算法时间复杂度，理解优化算法的重要性。

实验步骤1.利用递归算法，枚举每一行中皇后的位置；2.每一行都有8个候选位置，依次尝试每个位置是否可行；3.如果某个位置可行，继续对下一行进行递归；4.如果都不可行，则回溯到上一行，重新选择位置；5.直到第8行所有位置都选择完成，输出结果。

程序实现及结果def conflict(pos, i):for j in range(i):if abs(pos[i] - pos[j]) in (0, i - j):return Truereturn Falsedef queen(num =8, pos = ()):for i in range(num):if not conflict(pos, i):if len(pos) == num -1:yield (i, )else:for result in queen(num, pos + (i, )):yield (i, ) + resultfor solution in list(queen(8)):print(solution)程序输出结果为所有可能的八皇后问题解决方案，共计92种：(0, 4, 7, 5, 2, 6, 1, 3)(0, 5, 7, 2, 6, 3, 1, 4)…(7, 3, 0, 2, 5, 1, 6, 4)(7, 4, 2, 0, 6, 1, 3, 5)结论与分析1.通过本实验，我们深入地理解了递归算法与回溯算法的基本思想，并将其应用到八皇后问题的解决中；2.程序的输出结果表明：八皇后问题有92种可能的解决方案；3.根据算法的时间复杂度分析，当八皇后问题的规模更大时，应该采用更高效的算法进行优化；4.进一步研究表明，通过基因算法等优化算法可以提高八皇后问题的解决效率。

⽤遗传算法解⼋皇后问题此算法收敛速度还可以，基本在1万代之内就能找到解主程序clear;clc;%%%⼋皇后问题，8X8的棋盘上，放置8个皇后，使之两两都不能攻击%初始的状态，随机在棋盘上放置8个皇后，每列放⼀个n = 8; %8皇后%%%⽤遗传算法计算%先随机获得⼏个个体，形成⼀个种群%这个种群有10个个体No_of_people = 10;people = randi(n,[No_of_people,n]);%计算每个初始种群的h值people_h = ones(No_of_people,1);for i = 1:No_of_peoplepeople_h(i) = fun_c(people(i,:));end%进化了多少代，由G来统计G = 1;G_max = 1e5;plt = zeros(1,G_max);while prod(people_h)~=0 && G<=G_max%精英保留策略，保留初始种群中1/100的精英个体%保留多少个精英No_elite = fix(No_of_people/100);if No_elite == 0No_elite =1;end%按照h值选出这些精英[~,ind] = sort(people_h);index = ind(1:No_elite);people_elite = people(index,:);%计算这个种群中每个个体的优势，以百分⽐表⽰，所有个体优势之和为1adv = people_h ./ sum(people_h);%从种群中随机选出10对个体，根据个体的优势来选择，优势越⼤的，被选中的概率越⼤people_dad = people;people_mom = people;for i=1:No_of_peoplepick = ones(2,1);while pick(1)==pick(2)pick = randsrc(2,1,[1:No_of_people; adv']);endpeople_dad(i,:) = people(pick(1),:);people_mom(i,:) = people(pick(2),:);end%然后交叉繁殖，染⾊体交叉。

人工智能课程设计报告学号：20091000608姓名：王沙沙班级：191091指导老师：赵老师2011年10月14目录1．N皇后问题 (1)需求分析，设计 (1)设计表示 (1)运行结果 (2)用户手册即测试数据 (2)结论 (5)主要算法代码 (5)2罗马尼亚问题 (9)需求分析，设计 (9)设计表示，详细设计 (9)用户手册 (11)运行结果 (11)主要算法代码 (12)3.实习心得 (21)1 N皇后问题1．问题描述、需求分析在N*N 的棋盘上分布N个皇后，其中N个皇后不能在同一行同一列，也不能出现在同一对角线上，此时N个皇后不会相互攻击。

程序需能手动输入皇后个数，并分别采用回溯法、爬山法、遗传法得出皇后的分布情况，输出皇后的位置即棋盘。

2．设计思想2.1 形式化N个皇后的位置可用一个N维数组表示，如921543……，意思是第一个皇后在第一列的第9行。

2.2 程序模块CreatIndividual( )函数用于产生一组表示皇后不在同一行也不再同一列的的一位数组，即产生一组互不相等的0~N之间的整数，便于快速求解。

IsLegal( )函数用于判断新放置的皇后是否合法，在回溯法中用到。

AttackQueenNum( )用于计算整个棋盘的攻击皇后个数，相当于一个评价函数，在爬山法和遗传法中用到；Find( )回溯法求解函数ClimbHill( )爬山法求解函数；GA( )遗传算法求解函数；（1）函数调用关系图如下：（2）函数接口规格说明：下图中的箭头指向表示为被指向函数所用2.3 详细设计a: CreatIndividual(int *A,int QueenNum)：以当时时间为种子循环产生随机数，为了使得产生的随机数都不想等，设计集合S[N]并初始化为0，表示还没有产生一个皇后，当产生的皇后不在S[N]中即S[N]！=1时将S[n]置为1，接着产生下一个皇后，如此循环便产生一组互不相等的值。

【实验名称】人工智能实验二：八皇后问题实验代码：#include<iostream>#include<stdlib.h>using namespace std;int LineNum[9]; //第i列的皇后要放的行位置（只用其中的列号1到8）bool a[9]; //a[i]为1表示第i行上尚未放皇后bool b[15]; //b[i]为1表示第i条斜对角线上尚未放皇后（斜对角线指的是"/"状对角线，该对角线上各点的行列号之和i+j为一个常数）bool c[15]; //c[i]为1表示第i条反斜对角线上尚未放皇后（反斜对角线指的是"\"状对角线，该对角线上各点的行列号之差i-j为一个常数）。

int count=0; //计数器，用于计算方法总数class Queen{int i; //成员变量，列号public:Queen(int x) //构造函数{i=x;}void solve(int);//成员函数};void Queen::solve(int i)//成员函数的实现{int j;for(j=1;j<9;j++)//遍历行{if(a[j]&&b[i+j-2]&&c[i-j+7]) //用于判断并实现：如果在第j行的第i列上放置皇后安全的话，则将一枚皇后放置到那儿。

{LineNum[i]=j; //记录皇后位置a[j]=false;b[i+j-2]=false;c[i-j+7]=false;solve(i+1); //递归调用solvea[j]=true;b[i+j-2]=true;c[i-j+7]=true;}}if(i>8) //摆放皇后之后，若i=8即已放满时则递归出口；否则通过solve(i+1);进行递归调用。

{count++;cout<<"第"<<count<<"种方案："<<endl; for(int m=1; m<9; m++){for(int n=1; n<9; n++){if(LineNum[m] == n)cout<<" Q";elsecout<<" *";}cout<<endl;}for(int p=1; p<9; p++){for(int q=1; q<9; q++){if(LineNum[p] == q){cout<<"("<<p<<","<<q<<")";}}}cout<<endl;getchar();//暂停以查看结果}}void main(){Queen queen(1); //定义一个八皇后对象，并初始化int i;for(i=0;i<9;i++) //初始化一个"空棋盘"{a[i]=true;}for(i=0;i<15;i++){b[i]=true;c[i]=true;}queen.solve(1); //第1列开始的连续8列上均放上皇后cout<<"一共有"<<count<<"种方案！";}实验截图如下：省略第9种到第88种方案。

⼋皇后（JAVA算法实现）在学习现代软件⼯程构建之法这门课时，⽼师要求发表⼀篇博客，使⽤JAVA算法实现⼋皇后问题的求解。

写这篇博客时，我学习了⼀些其他的博客，⾃⼰⽆法解决时，向他⼈学习也是⼀种⽅法。

国际西洋棋棋⼿马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放⼋个皇后，使其不能互相攻击，即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上，问有多少种摆法。

我们可以逐⾏或者逐列来进⾏可⾏摆放⽅案的遍历，每⼀⾏（或列）遍历出⼀个符合条件的位置，接着就到下⼀⾏或列遍历下⼀个棋⼦的合适位置，这种遍历思路可以保证我们遍历过程中有⼀个条件是绝对符合的——就是下⼀个棋⼦的摆放位置与前⾯的棋⼦不在同⼀⾏（或列）。

接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下⼀⾏（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某⼀个⾏（或列）的所有位置都不合适，就返回上⼀⾏（或列）继续该⾏（或列）的其他位置遍历，当我们顺利遍历到最后⼀⾏（或列），且有符合条件的位置时，就是⼀个可⾏的8皇后摆放⽅案，累加⼀次⼋皇后可⾏⽅案的个数，然后继续遍历该⾏其他位置是否有合适的，如果没有，则返回上⼀⾏，遍历该⾏其他位置，依此下去。

这样⼀个过程下来，我们就可以得出所有符合条件的8皇后摆放⽅案了。

这是递归思路。

接下来，我们以逐列遍历，具体到代码，进⼀步说明。

⾸先，从第⼀列开始找第⼀颗棋⼦的合适位置，我们知道，此时第⼀列的任何⼀个位置都是合适的，当棋⼦找到第⼀个合适的位置后，就开始到下⼀列考虑下⼀个合适的位置，此时，第⼆列的第⼀⾏及第⼆⾏显然就不能放第⼆颗棋⼦了，因为其与第⼀个棋⼦⼀个同在⼀⾏，⼀个同在⼀条斜线上。

第⼆列第三⾏成为第⼆列第⼀个合适的位置，以此类推，第三列的第5⾏⼜会是⼀个合适位置，这个过程中，我们注意到，每⼀列的合适位置都是受到前⾯⼏列的位置所影响，假设前⾯1列的棋⼦放在第3⾏，那当前列不能放的位置就⼀定是3⾏，2⾏，4⾏。

八皇后问题1、打开Microsoft Visual C++6.0编程软件→创建文件名为Queen.c2、编写程序→保存→调试→运行3、源代码#include <stdio.h> //120940120-陆绍启-八皇后问题static char Queen[8][8]; static int a[8];static int b[15];static int c[15];static int iQueenNum=0; //记录总的棋盘状态数void qu(int i); //参数i代表行int main(){int iLine,iColumn; //棋盘初始化，空格为#，放置皇后的地方为Qfor(iLine=0;iLine<8;iLine++){a[iLine]=0; //列标记初始化，表示无列冲突for(iColumn=0;iColumn<8;iColumn++)Queen[iLine][iColumn]='#';} //主、从对角线标记初始化，表示没有冲突for(iLine=0;iLine<15;iLine++)b[iLine]=c[iLine]=0;qu(0);system("pause");return 0;}void qu(int i){int iColumn;for(iColumn=0;iColumn<8;iColumn++){if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) //如果无冲突{Queen[i][iColumn]='Q'; //放皇后a[iColumn]=1; //标记，下一次该列上不能放皇后b[i-iColumn+7]=1; //标记，下一次该主对角线上不能放皇后c[i+iColumn]=1; //标记，下一次该从对角线上不能放皇后if(i<7)qu(i+1); //如果行还没有遍历完，进入下一行else //否则输出{ //输出棋盘状态int iLine,iColumn;printf("第%d种状态为：\n",++iQueenNum);for(iLine=0;iLine<8;iLine++){for(iColumn=0;iColumn<8;iColumn++)printf("%c ",Queen[iLine][iColumn]);printf("\n");}printf("\n\n");if(iQueenNum % 10 == 0){getch();}} // 如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置Queen[i][iColumn]='#';a[iColumn]=0;b[i-iColumn+7]=0;c[i+iColumn]=0;}}}4、执行结果（92种）。