四皇后问题试验报告

1、四皇后问题实验报告人工智能一一四皇后问题一、问题描述四皇后问题一个4X4国际象棋盘，依次放入四个皇后，条件：每行、每列及对角线上只 允许出现一枚棋子。QQQQ图AQQQQ至R设：DATA=L(表) x CL x i j1< i, j <4其中：i j 表示棋子所在行列如：24表示第二行第四列有一枚棋子.棋盘上可放入的棋子数为04个L表中的元素数为04 个，即Length L = 04 ,如图A 12, 24, 31,43 定义规则：if 1< i <4 and Length DATA = i 1then APPEND(DATA( ij )1< j <4 对于

2、任一行i , 1 & j <4表明每行有四条规则。比如第一行：R11, R12, R13, R14 棋盘中共有四行，所以共有16条规则。即：R11, R12, R13, R14R21, R22, R23, R24R31, R32, R33, R34R41, R42, R43, R4416条规则中，哪些是当前可用规则，取决于 DATA勺长度，即：DAT"的元素 个数。换言之，每次只能将一个棋子放在当前行的下一行。二、回溯法搜索策略图(41) (42) (43) (44)(41) (42) (43)皇后问题回溯算法搜索讨论：上述算法产生22次回溯，原因在于规则自然顺序排列，

3、没考虑任何智能因素。改进算法定义对角线函数：diag(i,j):过ij点最长的对角线长度值。规定： 如果：diag(i,k) < diag(i,j)则规则排列次序为：Rik , Rij同一行四条规则中，对角线函数值小的排在前面 如果：diag(i,k) = diag(i,j)则规则排列次序为：Rij , Rik j <k对角线长度相等的规则按照字母排列顺序排序按照对角线长度定义规则的排列次序为:0(口)(43)后的技至图讨论：利用局部知识排列规则是有效的。BACKTRACK法对重复出现的状态没有判断，所以可能造成出现死循环 没有对搜索深度加以限制，可能造成搜索代价太大。三、算法描述

4、回溯法一一在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件 的分支。使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几 种可能的选择，而且往往在某个选择不成功时需要回头再试另外一种选择，如 果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新 的选择则问题求解失败。在回溯策略中，也可以通过引入一些与问题相关的信息来加快搜索解的速 度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个 皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行 和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。 但在不同的位置，在对角

5、线方向所影响的棋盘位置数则是不同的。可以想象， 如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以 后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到 解的可能性也小。四、算法流程图五、源程序#include <stdio .h>#define N 4char boardNN;int t;int colN;/存储第i行对应的列的值，这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。int safetyPlace(int x,int y) (x,y)位置是否安全int i,j;for(i=0;i<x;i +)j =coli;if(x=i|y

6、=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 a1 =3;if(i=N)/输出棋盘for (w=0;w<N;w+)for (j=0;j <N;j +)if (boardwj =001)printf( "%c" ,boardwj);elseprintf( "%c" ,a0);printf( "%c " ,boardwj);printf( "n"

7、);printf( "n" );n")；printf(nt+；)else int u;for (u=O;u<N;u+)if (safety Place。,11)=1)(col|i=u;记录下第i行可行的列的位置board|i|u|=001;放置皇后get_position(i+l);/W换到下一个状态，即下一行col|i|=0;回溯到当前状态，重置列和棋盘的值board|i|u|=0; mainf)(printf(”c 是皇后八n 后”,001);getposition(O);一共有d种方法! nn,t);六、结果截图C:JMSOFTCYuYanbinvzwtemp.exe一共有2种方法!七、总结一一心得体会通过对四皇后问题的编程学习，让我对搜索策略更深层次的理解，尤其能 比较熟练掌握回溯策略一一首先将规则给出一个固定的排序，在搜索时，对当 前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状 态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态 重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有 规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生 成该状态的