篇一：四皇后问题实验报告
人工智能--四皇后问题
一、问题描述
四皇后问题
一个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 ﹜
定义规则： if1≤ i ≤4andlength data =  i －1
thenappend(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 同一行四条规则中，对角线函数值小的排在前面怎么用printf输出bool函数值
② 如果：diag(i,k) ＝ diag(i,j)  则规则排列次序为： rij ，rikj ＜ k 对角线长度相等的规则按照字母排列顺序排序
讨论：
① 利用局部知识排列规则是有效的。
② backtrack算法对重复出现的状态没有判断，所以可能造成出现死循环。 ③ 没有对搜索深度加以限制，可能造成搜索代价太大。
三、算法描述  回溯法--在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件的分支。
使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几种可能的选择，而
且往往在某个选择不成功时需要回头再试另外一种选择，如果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择则问题求解失败。
在回溯策略中，也可以通过引入一些与问题相关的信息来加快搜索解的速度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，到解的可能性也大；反之留有余地就小，到解的可能性也小。
四、算法流程图
五、源程序
#include <stdio.h>
#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<x;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<n;w++)
{
for (j=0;j<n;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<n;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是皇后!\n\n,001);
get_position(0);
printf(一共有%d种方法！\n,t);
}
六、结果截图
篇二：八皇后问题实验报告
实验报告
--八皇后问题求解（递归和非递归）
学号：  专业年级：  姓名：
一、需求分析（要实现的功能描述）
1．问题描述
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。八皇后问题最早是由国际囯际象棋棋手马克斯·贝瑟尔于1848年提出。诺克也是首先将问题推广到更一般的n
皇后摆放问题的人之一。
2．实现功能
八皇后问题实现了在棋盘上摆放八个皇后的功能，这八个皇后任意两个皇后都不能处于同一条横行、纵行或斜线上。
3．测试数据
测试数据可以通过手工寻三组满足需要的值，测试数组（m，n），其中m代表皇后所在的行，n代表皇后所在的列。例如，第一组测试数据：
（1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6）；第二组测试数据（1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）；第三组测试数据： （1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1）。最后与编程求得的结果进行比较。如果这三组数据在最后编程求得的结果中，说明程序的编写基本没有什么问题。
二、概要设计
在进行概要设计的过程中，要清楚整个程序包含的功能模块及模块间的调用关系。 对于八皇后问题，整个程序中应该包括主函数模块，摆放皇后的函数模块，以及判断皇后的位置是否摆放正确的判断模块。对于模块间的关系，在运行主函数的过程中会调用摆放皇后的函数模块，在摆放皇后的函数模块中，又会调用判断皇后位置是否摆放正确的判断模块。
三、详细设计
抽象数据类型中定义的各种操作算法实现（用n-s图描述） 对于求解八皇后问题的非递归算法，n-s图如下：对于八皇后问题求解的递归算法，n-s图如下：
四、调试分析
1．程序在调式过程中出现的问题及解决方法
由于对于c语言编程问题掌握的并非十分熟练，因而在程序的调试过程中出现了一些问题。例如，在编写位置冲突算法的过程中，在解决对角线问题上，没有考虑对角线有两条，只考虑了其中的一条，因而在编写程序的过程中，没有使用绝对值，导致得到的满足要求的测试结果比实际的要多得多。
再如，为了能够输出比较整齐的测试结果，开始的时候只是输出了皇后所在的列数，没有输出皇后的行数。后来，在添加了行数坐标后，两个程序输出了相同的比较整齐美观的测试结果。
2．算法的时间复杂度分析
在考虑算法的时间复杂度问题上，只需考虑每个函数的最大的时间复杂度即可，求得的最大的时间复杂度即为整个程序的时间复杂度。
对于递归程序的时间复杂度：
o()
对于非递归程序的时间复杂度：
o()
因而，对于递归和非递归程序两个程序的时间复杂度，递归程序的时间复杂度要高。
五、用户手册
由于在程序编写的过程中，使用的环境为visual c++ 6.0，因而在使用的过程中，最好使用visual c++ 6.0，以免在程序运行错误。
本程序的操作过程十分简单，不需要操作者有c语言基础。
六、测试结果
通过对于问题的编程求解，共得到了92种结果。从中任意选择三组数据进行测试。数组的第一个数值为皇后所在的行，第二个值为皇后所在的列。
第一组测试数据：
（1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6） 用图像形象表示为：
再如，第二组测试数据：
（1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）
第三组测试数据：（1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1）
由于空间有限，所以92种测试结果用数组的形式表示如下：篇三：八皇后实验报告
实验项目：
1. 实验目的：通过求解皇后问题，熟悉深度优先搜索法dfs（回溯法（backtracking algorithms）技术。
2. 实验内容：由n2个方块排成n行n列的正方形称为n元棋盘。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现要出使棋盘上n个皇后互不攻击的布局。编制程序解决上述问题，以n=6运行程序，输出结果。
3. 程序简介：将n个皇后放到一个n*n的方阵中，要求每个皇后不在同一行同一列及同一对角线，我的程序是先把每个皇后放在了第零列，然后再按行检查，不符合要求继续下一列，若已经到这一行的最后一列，还没到符合要求的位置，则回到上一行。
4. 算法设计介绍：
定义一个一维数组，数组的下标是皇后所在位置的行数，数组存的值是皇后所在位置的列数，现将a[0]-a[n-1]都赋成零，然后随着检查的进行，皇后的位置也在不断地变化，最后到一个符合要求的方阵时，本质上就是一个存放整数的一维数组，数组的下标是行数，存放的值是列数。