八皇后问题.pdf

数据结构课程设计报告
八皇后问题
班级：
***
姓名：
***
学号：
***
八皇后问题
1、问题分析
线上无皇后。行、列坐标之差 i-j 相等的诸方格在同一 条“/方向的对角线
上，该类对角线有 15 条，其行、列坐标之差分别是-7 乙 因此 C 语言数组下标是
从 0 开始的，所以用 c[2…16B 记这种方向的诸对角线上 有无皇后，c[k]为真时表示
该方向的第 k 条对角线上无皇后。这样，b[i+j]和 c[i- j+9]的真假就分别表示了通过位
置(i, j)的两条对角线上有无皇后。
因此，位置(i,j)的安全”性可用逻辑表达式
a[j]&&b[i+j]&&c[i-j+9]
来表示。在位置(i,j)上放置皇后后，相当于将 a[j], b[i+j]和 c[i-j+9]置为 假；移去
(i,j)上的皇后相当于将 a[j], b[i+j]和 c[i-j+9]置为真。
2. 2 算法扩充
在上面的算法中，仅求出了八皇后问题的一个解，要求出所有满足约束条 件的
解，就要对上述算法进行扩充和修改。要解决这个问题，关键在于以下两 个问题：
(1) 如何从问题的一个解出发求出下一个解：
(2) 如何确定所有的问题解都已求出。
因此，我们可对上述算法进行修改，使其求得一个解后，算法并不终止， 而是
输出这个解，然后退栈回溯，继续寻找下一个解；一旦当前行是第 1 行又
仍需要退栈回溯时，算法终止。
3、算法实现
//求八皇后问题所有解的源程序清单
#include<>
#define true 1#define false 0
int a[9],b[17],c[17];// 声明全局变量
int s[9];
void main(){void print(),movequeen(),eightqueen();// 函数声明
eightqueen();// 调用求命新 l 皇后 I、可题}/**********************/
/*打印输出一个解的函数*/
/**********************/
void print(){int k;
printf("\n 行号 :1 2 3 4 5 6 7 8\n");
printf("列号：
");
for(k=1;k<=8;k++)
printf("%4d",s[k]);