N皇后问题实验报告.doc

一、 实验内容
在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皇后问题解的情况
皇后的个数
问题的解
N=1
X=(1)
N=2
无解
N=3
无解
N=4
X1=(2,4,1,3); X2=(3,1,4,2)
N=5
X1=(1,3,5,2,4); X2=(1,4,2,5,3); X3=(2,4,1,3,5); X4=(2,5,3,1,4)；
X5=(3,1,4,2,5); X6=(3,5,2,4,1); X7=(4,1,3,5,2); X8=(4,2,5,3,1)；
X9=(5,2,4,1,3); X10=(5,3,1,4,2)
N=6
X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,5,2,6,3);X4=(5,3,1,6,4,2)
N=7
40个解
N=8
92个解
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. 流程图

4 / 5