1 设计要求与分析
在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。
2.全部程序
// 八皇后.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#define TRUE 1
#define FALSE 0
int iRow[9],iRightDiagonal[17],iLeftDiagonal[17];
int iSeqStack[9];
static int index=1;
void queenPrint()
{
int k;
printf("n行号: 1 2 3 4 5 6 7 8n");
printf("列号:");
for ( k=1 ; k<=8;k )
printf("m",iSeqStack[k]);
printf("n");
}
void queenMove(int i,int j)
{
iRow[j]=1;
iRightDiagonal[i j]=1;
iLeftDiagonal[i-j 9]=1;
}
void queenSolve()
{
int i,j;
for (i=2;i<=16;i ){
if (i>=2&&i<=9)
iRow[i-1]=TRUE;
iRightDiagonal[i]=TRUE;
iLeftDiagonal[i]=TRUE;
}
i=1;j=1;
while (i>=1){
while (j<=8){
if (iRightDiagonal[i j]&&iRow[j]&&iLeftDiagonal[i-j 9])
break;
j ;
}
if (j<=8){
iRow[j]=FALSE;
iRightDiagonal[i j]=FALSE;
iLeftDiagonal[i-j 9]=FALSE;
iSeqStack[i]=j;
if (i==8){
queenPrint();
queenMove(i,j);
i--;j=iSeqStack[i];
queenMove(i,j);
j ;
}
else {
i ;
j=1;
}
}
else {
i--;
if (i>=1) {
j=iSeqStack[i];
queenMove(i,j);
j ;
}
}
}
}
int main(int argc, char* argv[])
{
queenSolve();
//printf("Hello World!n");
return 0;
}
3.算法求精
全局变量
int iRow[9],iRightDiagonal[17],iLeftDiagonal[17];
iRow[j]为真时，表示j列上无皇后
iRightDiagonal[i j]为真时，表示“/”的对角线上无皇后
iLeftDiagonal[i-j 9]为真时，表示“”的对角线上无皇后
棋盘上的安全点为 iRightDiagonal[i j]&&iRow[j]&&iLeftDiagonal[i-j 9] 的点，在位置（i，j）上放置皇后后，把 iRightDiagonal[i j]&&iRow[j]&&iLeftDiagonal[i-j 9] 置为假。
程序的流程
for (i=2;i<=16;i ){
if (i>=2&&i<=9)
iRow[i-1]=TRUE;
iRightDiagonal[i]=TRUE;
iLeftDiagonal[i]=TRUE;
}
把所有的位置全设为安全的位置
while (i>=1){
.............................
}
当i一旦减为0，表示全部的解已找到
while (j<=8){
if (iRightDiagonal[i j]&&iRow[j]&&iLeftDiagonal[i-j 9])
break;
j ;
}
在第i行找安全点，找到了就跳出，没找到就接着找
if (j<=8){
iRow[j]=FALSE;
iRightDiagonal[i j]=FALSE;
iLeftDiagonal[i-j 9]=FALSE;
iSeqStack[i]=j;
接着上面的j，如果j<=8，就是说明在第八行找到了安全点
if (i==8){
queenPrint();
queenMove(i,j);
i--;j=iSeqStack[i];
queenMove(i,j);
j ;
}
else {
i ;
j=1;
}
当i=8 时，说明到了第八行，打印全部的解，并且移去最后一行的皇后，再退栈，回到上一个皇后，再移去这个皇后，再修改栈的位置，再进行回溯
