算法设计与分析
实验报告
—八皇后问题
-
姓名：***
学号：********
班级：软件83
【问题描述】
在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。

【问题分析&算法设计】
用8元组x[1: n]表示8后问题。

其中x[ i]表示皇后i放在棋盘的第i行的第x[ i]列。

由于不允许将2个皇后放在一列，所以解向量中的x[ i]互不相同。

2个皇后不能放在同一斜线上是问题的隐约束。

故若2个皇后放置的位置分别是（i，j）和（k，l），且i – j = k – l或i + j = k + l，则说明这2个皇后处于同一斜线上。

这两个方程分别等价于i – k = j – l和i – k = l – j。

由此可知，只要|i - k| = |j - l|成立，就表明2个皇后位于同一条斜线上。

问题的隐约束化成了显约束。

用回溯法解决8皇后问题时，用完全8叉树表示解空间。

【算法实现】
#include "stdio.h"
#include "math.h"
#include "iostream.h"
#define N 8 /* 定义棋盘大小*/
static int sum; /* 当前已找到解的个数*/
static int x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列*/
/* 每找到一个解,打印当前棋盘状态*/
void Show()
{
sum++;
cout << "第" << sum << "种情况：" << endl;
cout << "坐标为:\t";
for(int k = 0; k < N; k++)
cout << '(' << k+1 << ',' << x[k] << ") ";
cout << endl;
cout << "---------------------------------\n";
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
if (j == x[i]) //printf("@ ");
cout << "* | ";
else //printf("* ");
cout << " | ";
cout << "\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层子树*/
void 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);
}
}
int main()
{
Backtrack(0);
cout << endl;
return 0;
}
【运行结果】
可知在考虑对称的情况下，8皇后问题共有92种解。