四皇后问题实验报告_n皇后问题实验报告
四皇后问题实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“n皇后问题实验报告”。
人工智能——四皇后问题
一、问题描述
四皇后问题
一个4×4国际象棋盘，依次放入四个皇后，条件：每行、每列及对角线上只允许出现一枚棋子。
设：DATA=L（表）x∈L x ∈﹛i j﹜ 1≤ i, j ≤4 其中：i j 表示棋子所在行列 如：24 表示第二行第四列有一枚棋子 ∵棋盘上可放入的棋子数为0 ～ 4 个
∴L表中的元素数为0 ～ 4 个，即 Length L = 0 ～ 4，如图A ﹛12，24，31，43 ﹜
定义规则： if 1≤ i ≤4 and Length DATA = i －1 then APPEND(DATA(ij))1≤ j ≤4 ① 对于任一行i，1≤ j ≤4 表明每行有四条规则。
比如第一行：R11，R12，R13，R14 ② 棋盘中共有四行，所以共有16条规则。
即： R11，R12，R13，R14 R21，R22，R23，R24 R31，R32，R33，R34 R41，R42，R43，R44 ③ 16条规则中，哪些是当前可用规则，取决于DATA的长度，即：DATA中的元素个数。换言之，每次只能将一个棋子放在当前行的下一行。
二、回溯法搜索策略图
讨论：
上述算法产生22次回溯，原因在于规则自然顺序排列，没考虑任何智能因素。改进算法
定义对角线函数：diag(i,j)：过ij点最长的对角线长度值。
规定：① 如果： diag(i,k)≤ diag(i,j)则规则排列次序为： Rik，Rij 同一行四条规则中，对角线函数值小的排在前面
② 如果：diag(i,k)＝ diag(i,j)则规则排列次序为： Rij，Rik j ＜ k 对角线长度相等的规则按照字母排列顺序排序
讨论：
① 利用局部知识排列规则是有效的。
② BACKTRACK算法对重复出现的状态没有判断，所以可能造成出现死循环。③ 没有对搜索深度加以限制，可能造成搜索代价太大。
三、算法描述
回溯法——在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件的分支。
使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几种可能的选择，而且往往在某个选择不成功时需要回头再试另外一种选择，如果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择则问题求解失败。
在回溯策略中，也可以通过引入一些与问题相关的信息来加快搜索解的速度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。
四、算法流程图
五、源程序
#include #define N 4 char board[N][N];int t;int col[N];
//存储第i行对应的列的值，这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。
int safetyPlace(int x,int y)//(x,y)位置是否安全 {
int i,j;
for(i=0;i
{
j=col[i];
if(x==i||y==j)
return 0;
if(x-y==i-j||x+y==i+j)
//判断左右对角线
return 0;
}
return 1;} void get_position(int i)
//处在第i行时状态 {
int w,j;
char a[1]={3};
if(i==N)
//输出棋盘
{
for(w=0;w
{
for(j=0;j
{
if(board[w][j]==001)
printf(“%c ”,board[w][j]);
else
{
printf(“%c”,a[0]);
printf(“%c ”,board[w][j]);
}
}
printf(“n”);
}
printf(“n”);
printf(“--------------n”);
t++;
}
else
{
int u;
for(u=0;u
{
if(safetyPlace(i,u)==1)
{
col[i]=u;
//记录下第i行可行的列的位置
board[i][u]=001;
//放置皇后
get_position(i+1);
//转换到下一个状态，即下一行
col[i]=0;
//回溯到当前状态，重置列和棋盘的值
board[i][u]=0;
} }
} } main(){
printf(“%c是皇后!nn”,001);get_position(0);printf(“一共有%d种方法！n”,t);}
六、结果截图
七、总结——心得体会
通过对四皇后问题的编程学习，让我对搜索策略更深层次的理解，尤其能比较熟练掌握回溯策略——首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。
同时，在整个编程学习过程中，使得我对人工智能感到越来越多的趣味性（例如四皇后问题上升到n皇后如何求解），更引起我对学习人工智能这门课程的积极性。
