四皇后问题实验报告VIP免费

人工智能——四皇后问题一、问题描述四皇后问题一个4×4国际象棋盘，依次放入四个皇后，条件：每行、每列及对角线上只允许出现一枚棋子。设：DATA=L（表）x∈Lx∈﹛ij﹜1≤i,j≤4其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子∵棋盘上可放入的棋子数为0～4个∴L表中的元素数为0～4个，即LengthL=0～4，如图A﹛12，24，31，43﹜定义规则：if1≤i≤4andLengthDATA=i－1thenAPPEND(DATA(ij))1≤j≤4①对于任一行i，1≤j≤4表明每行有四条规则。比如第一行：R11，R12，R13，R14②棋盘中共有四行，所以共有16条规则。即：R11，R12，R13，R14R21，R22，R23，R24R31，R32，R33，R34R41，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，Rikj＜k对角线长度相等的规则按照字母排列顺序排序讨论：①利用局部知识排列规则是有效的。②BACKTRACK算法对重复出现的状态没有判断，所以可能造成出现死循环。③没有对搜索深度加以限制，可能造成搜索代价太大。三、算法描述回溯法——在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件的分支。使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几种可能的选择，而且往往在某个选择不成功时需要回头再试另外一种选择，如果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择则问题求解失败。在回溯策略中，也可以通过引入一些与问题相关的信息来加快搜索解的速度对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。四、算法流程图五、源程序#include#defineN4charboard[N][N];intt;intcol[N];//存储第i行对应的列的值，这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。intsafetyPlace(intx,inty)//(x,y)位置是否安全{inti,j;for(i=0;i