八皇后问题

int a[9],b[17],c[17];
int s[9];
其中，a[j]为真时
（1），表示第j列上无皇后。位于同一条 “/方”向的对角线上的诸方格，其 行、列坐标之和i+j是相等的，这种方向的对角线有15条，其行、列坐标之和 分别为2〜16,因此用b[2…16标记该方向的诸对角线上有无皇后，b[k]为真时 表示该方向的第k条对角线上无皇后。行、列坐标之差i-j相等的诸方格在同一 条“/方”向的对角线上,该类对角线有15条,其行、列坐标之差分别是-7〜7, 因此C语言数组下标是从0开始的，所以用c[2…16标记这种方向的诸对角线上 有无皇后，c[k]为真时表示该方向的第k条对角线上无皇后。这样，b[i+j]和c[i- j+9]的真假就分别表示了通过位置（i,j）的两条对角线上有无皇后。
c[i-j+9]=false；
s[i]=j；//皇后位置j入栈
if(i==8){//找到一个解，输出解
print()；//打印输出一个解
movequeen(i,j);〃移去位置(i,j)上的皇后
i--；j=s[i]；//退栈，回溯到上一个皇后movequeen(i,j); //移去位置(i,j)上的皇后
#define true1
#define false0
int a[9],b[17],c[17];//声明全局变量
int s[9];
void main(){void print(),movequeen(),eightqueen();//函数声明eightqueen();//调用求解八皇后问题}/**********************/ /*打印输出一个解的函数*/
因此，位置（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算法扩充
在上面的算法中,仅求出了八皇后问题的一个解,要求出所有满足约束条 件的解,就要对上述算法进行扩充和修改。要解决这个问题,关键在于以下两 个问题：
******************************
void movequeen(int i,int j){a[j]=1;b[i+j]=1;c[i-j+9]=1;}//在此位置插入eightquee n()函数
void eightqueen(){int i,j;
for(i=2;i<=16;i++){if(i>=2&&i<=9) a[i-1]=true;
2、算法描述
从第一行起逐行放置皇后，每放置一个皇后均需要依次对第1,2…8列进行
试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已经放置 的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安 全位置；若当前试探的列位置不安全，则用下一列去试探，当8列位置试探完 毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然 后继续试探。
/**********************/void print(){int k;
printf("\n行号:1 2 3 4 5 6 78\n");
printf("列号:
");
for(k=1;k<=8;k++)
printf("%4d",s[k]);printf("\n");}/
/*移去位置（i，j）上的皇后函数*/
数据结构课程设计报告
八皇后问题
班级：
***
姓名：
***
学号：
***
八皇后问题
1、问题分析
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高 斯1850提出；在8X8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意 两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认 为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的 解，后人有人用图论的方法解出92宗结果。
(8)}
2．1算法求精
要对上述抽象算法进行逐步求精，就需要确定相应的存储结构和有关的数 据类型。当前行和列分别用i和j表示；用数组s[1…8表示顺序栈，栈空间的下 标值表示皇后所在的行号，栈的内容是皇后所在的列号。例如，若皇后放在位 置(i,j)上，则将j压入栈中，即s[i]=j。为了便于检查皇后之间是否冲突，我们 增加三个布尔数组(初始值为真)，将与检查有关的信息事先保存起来。定义 如下：
该算法抽象的描述如下：
(1)置当前行当前列均为1；
(2)While(当前行号v=8);
(3){检查当前行，从当前列起逐列试探，寻找安全列号；
(4)if(找到安全列号)
(5)放置皇后，将列号放入栈中，并将下一行置为当前行，第1列置为当
前列；
(6)else
(7)退栈回溯到上一行，移去该行已经放置的皇后，已该皇后所在列的下 一列作为当前列；
（1）如何从问题的一个解出发求出下一个解：
（2）如何确定所有的问题解都已求源自文库。
因此,我们可对上述算法进行修改,使其求得一个解后,算法并不终止, 而是输出这个解,然后退栈回溯,继续寻找下一个解；一旦当前行是第1行又 仍需要退栈回溯时,算法终止。
3、算法实现
//求八皇后问题所有解的源程序清单
#include<stdio.h>
b[i]=true;c[i]=true;}i=1;j=1; while(i>=1){//当i=0时终止循环
while(j<=8){//在当前行i上寻找安全位置if(a[j]&&b[i+j]&&c[i-j+9]) break;
j++；}if(j<=8){〃找到安全位置(i,j)
a[j]=false;b[i+j]=false;
八皇后问题是在8*8的国际象棋棋盘上，安放8个皇后，要求没有一个皇 后能够 “吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的 同一行、同一列或同一条对角线。
八皇后在棋盘上分布的各种可能的格局，其数非常大，但是可以将一些明 显不满足问题要求的格局排除掉。由于任何两个皇后不能同行，即每一行只能 放置一个皇后，因此将第i个皇后放置在第i行。这样在放置第i个皇后时，只 要考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。