八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j，i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。
当前行、列用i和j表示；顺序栈用数组s[8]表示，栈空间的下标值表示皇后所在的行号，栈的内容是皇后所在的列号。
如，若皇后放在位置(i,j)上，则将j压入栈内，即s[i] = j;
int s[9];
为了便于检查皇后之间是否冲突，增加三个布尔数组（初始始值为真），将与检查有关的信息事先保存下来。定义如下：
int a[9],b[17],c[17]
a 数组表示各列上的信息；
b数组表示对角线"/"方向上信息，有15条，每条各元素的i j相等，列坐标之和分别为2至16；
c数组表示对角线"\"方向上信息，有15条，每条各元素的i-j相等，列坐标之差分别为-7至7；
a[j]、b[i j]、c[i-j 9]为真时，表示该列、"/"方向对角线、"\"方向对角线上无皇后。
在位置(i,j)上放置皇后，也就是将j压入栈内，即s[i] = j；a[j]、b[i j]、c[i-j 9]置为假；移去(i,j)上的皇后相当于将a[j]、b[i j]、c[i-j 9]置为真。
C代码如下：
#include<stdlib.h>
#include<stdio.h>
#define true 1
#define false 0
void print(int[]); //函数声明
void movequeen(int, int,int[],int[],int[]);
void eightqueen( );
void main( )
{
eightqueen( ); //调用求解八皇后问题
system("pause");
}
/* 打印输出一个解的函数 */
void print(int s[] )
{
int k;
printf("\n行号： 1 2 3 4 5 6 7 8\n");
printf("列号：");
for(k=1; k<=8; k )
printf("M",s[k]);
printf("\n");
}
/* 移去位置(i,j)上的皇后函数 */
void movequeen(int i, int j, int a[], int b[], int c[])
{
a[j]=1;
b[i j]=1;
c[i-j 9]=1;
}
//在此位置插入对应的函数
void eightqueen( )
{
int i,j;
int s[9];
int a[9], b[17], c[17];
for(i=2; i<=16; i ) {
if(i>=2 && i<=9) a[i-1]=true;
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;
c[i-j 9]=false;
s[i]=j; //皇后位置j入栈
if(i==8) {//找到一个解,输出解
print(s); //打印输出一个解
movequeen(i,j,a,b,c); //移去位置(i,j)上的皇后
i--; j=s[i]; //退栈，回溯到上一个皇后
movequeen(i,j,a,b,c); //移去位置(i,j)上的皇后
j ; //修改栈顶皇后的位置
}
else {
i ;j=1; //准备放置下一个皇后
}
}
else {
i--; //退栈
if(i>=1) { //栈不空,移去皇后
j=s[i];
movequeen(i,j,a,b,c); //移去皇后
j ;
}
}
}
}
运行结果：
递归法求解行号： 1 2 3 4 5 6 7 8
列号： 1 5 8 6 3 7 2 4
行号： 1 2 3 4 5 6 7 8
列号： 1 6 8 3 7 4 2 5
行号： 1 2 3 4 5 6 7 8
列号： 1 7 4 6 8 2 5 3
行号： 1 2 3 4 5 6 7 8
列号： 1 7 5 8 2 4 6 3
行号： 1 2 3 4 5 6 7 8
列号： 2 4 6 8 3 1 7 5
行号： 1 2 3 4 5 6 7 8
列号： 2 5 7 1 3 8 6 4
行号： 1 2 3 4 5 6 7 8
列号： 2 5 7 4 1 8 6 3
行号： 1 2 3 4 5 6 7 8
列号： 2 6 1 7 4 8 3 5
#include<stdio.h>
#define true 1
#define false 0
#define nmax 9
int num=0;
int q[9];
int C[9];
int L[17];
int R[17];
void eightqueen(int);
void main( )
{
int i=0;
// num=0;
for(i=0; i< 9 ; i )
C[i]=true;
for(i=0; i< 17 ; i )
{
L[i]=true;
R[i]=true;
}
eightqueen(1); //调用求解八皇后问题
system("pause");
}
//eightqqueen( )函数
void eightqueen(int i)
{
int j,k,c=0;
for(j=1; j<=8 ; j )
{
if((C[j] == true && (L[i-j nmax] == true)
&& (R[i j]) == true))
{
q[i]=j;
C[j] = false;
L[i-j nmax] = false;
R[i j] = false;
if(i<8)
{
eightqueen(i 1);
}
else
{
num ;
printf("方案-：", num);
for(k=1; k<=8; k )
printf("%d", q[k]);
printf("\n");
}
C[j] = true;
L[i-j nmax] = true;
R[i j] = true;
}
}
}
方案 1：15863724
方案 2：16837425
方案 3：17468253
方案 4：17582463
方案 5：24683175
方案 6：25713864
方案 7：25741863
方案 8：26174835
方案 9：26831475
......
-End-
