一、 实验内容
在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，求解可以放置的方法种数。
二、 问题分析
n后问题等于于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后，不会造成列上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。
三、 算法设计
1. 解决冲突问题：
这个问题包括了行，列，两条对角线；
列：规定每一列放一个皇后，不会造成列上的冲突；
行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；
对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2. 算法设计
因为n皇后问题，从n大于11开始求解过程耗时就很长，所以定义x数组的最大值MAXNUM=30；即最大可解决30皇后问题。
1) 判断当前位置是否可放置皇后
皇后k在第k行第x[k]列时，x[i]==x[k] 时，两皇后在同一列上;abs(x[i]-x[k])==abs(i-k)时，两皇后在同一斜线上;两种情况两皇后都可相互攻击，返回false表示不符合条件。
bool Place(int k)
{
int i;
i=1;
while(i<k)
{
if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))
return false;
i=i+1;
}
return true;
2) 输出当前解
void Print(int x[],int n)
{
num++;
printf("第%d\t种解法:(",num);
for(int i=1;i<=n;i++)
{
printf("%d,",x[i]);
if(i%n==0)printf(");\n");
}
3) 回溯法搜索解空间
void NQueens(int n)
{
int k=1;
x[1]=0;
while(k>0)
{
x[k]+=1;
while(x[k]<=n&&!Place(k))
x[k]+=1;
if(x[k]<=n)
{
if(k==n)
Print(x,n);
else
{
k=k+1;
x[k]=0;
}
}
//回溯至上一行；
else
k--;
}
}
3. 实验结果及分析
n皇后问题解的情况
4. 实验程序
随着N 的增大，解的个数增多，以N=4为例
#include <stdio.h>
#include<math.h>
#define N 4 /* 定义棋盘大小 */
static int sum; /* 当前已找到解的个数 */
static int x[N];
int place(int k)
{
int j;
for (j = 0; j < k; j ++)
if (x[j] == x[k] || abs(j - k) == abs(x[j] - x[k]))
return 0;
return 1;
}
/* 打印棋局 */
void chessboard()
{
int i,j;
int site[N];
printf("第%d种解法:\n", ++ sum);
for (i = 0; i < N; i ++) {
for (j = 0; j < N; j ++)
if (j == x[i]) {printf("Q ");site[i]=j+1;}
else printf("* ");
printf("\n");
}
printf("A%d(",sum);
for(i = 0; i < N; i ++)
{
printf("%d,",site[i]);
}
printf(");");
printf("\n");
}
/* 回溯搜索解空间 */
void backtrack()
{
int k = 0;
x[0] = -1;
while (k >= 0) {
x[k] += 1; /* 向右移一列 */
/* 向右移至出最右列或可以放置皇后的列 */
while ((x[k] < N) && !(place(k))) x[k] += 1;
if (x[k] < N) /* 向右移未移出棋盘 */
if (k == N - 1) chessboard(); /* 已移至最后一行 */
else x[++ k] = -1; /* 向下移一行 */
else k --; /* 回溯到上一行 */
}
}
int main(void)
{
backtrack();
printf("%d皇后有%d个解:\n",N,sum);
return 0;
}
实验结果截图：
5. 流程图
第二篇：河师大算法设计与分析N皇后问题实验报告
计算机与信息技术学院实验报告
专业：计算机科学与技术 年级/班级：20##级 20##—20##学年第一学期
一、实验项目
N皇后问题
二、需求分析
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题要求在一个8*8的棋盘上放上8个皇后，使得每一个皇后既不攻击到另外七个皇后，也不被另外七个皇后所攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法：并找出所有的摆法。因此，八皇后问题等于要求八个皇后中的任意两个不能被放置在同一行或同一列或同一斜线。
本次实验算法设计中，用到的主要知识有：递归法的运用，for 语句的灵活运用，数据结构中树知识的灵活运用、数组及动态数组技术的掌握。 系统要求：win98 以上操作系统； 语言平台：vc++6.0 或以上版本。
根据程序的设计要求，需要设计一个八皇后问题的演示程序，程序需要具备以下功能：能够快速查找并显示八皇后的布局方式有多少种正确方法。能够逐个查看每种布局的结果。能够很方便的改变皇后个数即棋盘规格。
三、概要设计：
本实验是用递归和回溯法来实现的，分别测试了每一种摆法，并将一个解图形化显示输出。在这程序中，思路主要是这样的：
1、解决冲突问题和数据结构的实现
对于数据结构的实现，则是着重于：
（1） 数组x[i]：表示第i个皇后放置的列；i的范围：0—n-1；
（2） 数据初始化
（3） 从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先用xx函数测试当前位置是未被占领；如果是，摆放第n-1个皇后后并宣布占领，接着进行递归；如果不是，测试下一个位置（n,m+1），但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。
（4） 当n=8时，便一一打印出结果。）
首先定义一个递归找全部的解的递归函数FindQueen(int i)，设有一个参数i,表示1至i-1行都已有皇后合理放置的情况下，寻找第i行的合理放置。在i行上，有8种可能的放置，列j顺序选择第1列，第2列……直至第n列。当第i行j列的放置是合理的时候，就设置与i行j列相对应的列、斜线有皇后的标志并输出皇后，并在i=7(i从0开始计算)的情况下，看皇后位置是否合适，合适则弹出对话框，并把标记flag置为1；否则递归调用FindQueen（i+1）,在第i+1行上寻找合理的放置，一列试探结束，再试探下一列前，清除已设置的与i行j列相对应的列，斜线有皇后的标志，让j增加1，在下一列寻找解。
再看如何表示一个解。由于每一列要放置一个皇后，所以，可以放置一个一维数组
，称其为解数组，令其每个元素对应一行，其值等于该行上皇后所在的列号，即
X[i]==k
表示第i行上的第k列放置皇后。
要保存多个解时，可以设立多个这样的一维数组或一个二维数组。
下面考虑棋盘的表示。棋盘在这里是原始输入数据。但该问题与一般不同，只要知道棋盘的规模（即n×n）,棋盘就完全确定了。此外，皇后的放置状态以用解数组x表示，因此，如果没有其他用途，棋盘的n×n的阵列表示是不需要显示给出的。
下边考虑冲突判别。如果已设置n×n阵列棋盘的表示，则可以对已放置了皇后的格子做标记，然后根据标记判别是否有冲突。若不设置n×n阵列，则可通过解数组x判别冲突。因为解数组已包含了全部的放置状态信息。
设目前要在i行j列放置皇后，考虑如何判断其是否u其他皇后冲突。冲突判别有下列几种：
（1）“是否为同行”，由于以行为单位放置皇后，所以不需要判断“是否为同行”
（2）“是否为同列”，这可以通过扫描解数组x得到，即查找x[1]~x[j-1]中，是否有值为i的元素。
（3）“是否为同斜线”，注意，n×n的阵列中有两种斜线——正斜线（/）和反斜线（\），各有2n-1条。同一条正斜线上，个元素的行号和列号之和相等；同一条反斜线上，个元素的行号和列号之差相等。因此，若有两个皇后的放置位置分别为（i,j）（g,h），则如果 i-j==g-h或i+j==g+h
则表示它们在同一斜线上，有冲突。这两个式子等价于
I- g==j-h或i-g==h-j 其又等价于|i-g|==|j-h|
因此，判断（i,j）是否与当前放置的皇后冲突，可以通过扫描解数组x来完成，即检查x的每个元素x[k]（其表示位置(x[k]，k)上有皇后，k<j），若下式成立
|i- x[k]|==|j-k|
则表明有冲突。
2、逻辑结构设计
类图
表汇总
3、模块设计
4、算法流程图
四、编程源代码：
# #include "stdio.h"
#include "stdlib.h"
#include "math.h"
Int N ; //定义棋盘的大小
int sum = 0; //当前已找到解的个数
int x[N]; //记录皇后的位置，x[i]表示皇后i放在棋盘的第i行的第x[i]列
/*每找到一个解，打印当前棋盘状态*/
void Show()
{
sum++;
printf("第%d种情况：",sum);
printf("坐标为：\n");
for(int k=0;k<N;k++)
printf("(%d,%d)",k+1,x[k]);
printf("\n");
printf("----------------------\n");
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
if(j==x[i])printf("*|"); //prinft("@")
else printf(" |"); //printf("*")
printf("\n---------------------------\n");
}
}
/*确定某一位置皇后放置与否，放置则返回1，反之返回0*/
int Judge(int k)
{
//测试皇后k在第k行，第x[k]列时是否与前面已放置好的皇后相攻击。X[j]==x[k]时
//两皇后在同一列上；abs(k-j)==abs(x[j]-x[k])时，两皇后在 同一斜线上。两种情况两皇//后都可相互攻击，故返回0表示不符合条件。
for(int j = 0; j < k; j++)
if(abs(k-j) == abs(x[j] - x[k]) || x[j]==x[k])
return 0;
return 1;
}
/*主递归函数，搜索解空间中第i层子树*/
int Backtrack(int t)
{
/*t==N时，算法搜索至叶节点，得到一个新的N皇后互不攻击的放置方案*/
if(t==N)
Show();
else
{
for(int i = 0; i < N; i++)
{
x[t] = i;
if(Judge(t))
Backtrack(t+1);
}
}
return 0;
}
int main()
{ printf(“请输入棋盘大小（N）：\n”);
Scanf(“%d”,&N);
Backtrack(0);
printf("\n");
system("pause");
getchar();
return 0;
}
运行结果：
当N=8时，输出的第92种情况：
五、心得体会
本程序通过关键函数Backtrack(int t)的调用，将N皇后的关键问题通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在行与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断，即可完成。如果在程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断地判断，去推答案，而且这种非递归的思想，大大增加了程序的时间复杂度。我们使用了数据结构中的算法后，程序的时间复杂度，以及相关的代码简化都能取得不错的改进。
在本次实验中，我们利用递归和回溯法求解n皇后问题。通过本次实验设计，明确了n皇后的概念。并通过本实验，熟悉回溯算法在程序设计中的应用方法。回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法士计算机科学里的常用方法，使用回溯、递归，可以将很复杂的问题再形式上予以简化，由于自己编程能力有限，本程序算法不够精炼，程序语句也不够简明。在编写程序时，对书上的算法语句还不能融汇贯通。今后一定多研读书中的代码，做到活学活用。
在初始状态下 棋盘上没有任何棋子。然后顺序在第1行，第2行，…，第n行上布置棋子。在每一行中有n个可选择的位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件：即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。
用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜方向、反斜方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，回复安放此棋子前的状态，试探本行的j+1列。