8queen.cpp

c语言实现的八皇后问题的解法

/*
八皇后问题
算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，
如果某列上已经有皇后，则为1，否则为0；
数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；
数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0；
用堆栈保存棋盘状态
*/
#include <stdio.h>
#include <stdlib.h>
typedef int SElemType;
#include "..\include\stack.cpp"

SqStack aStack;
int a[8],b[15],c[15],iQueenNum=0;  //记录总的棋盘状态数

void placeQueen(int i);  //参数i代表行

int main()
{
	int iLine;
	InitStack(aStack);
    //初始化堆栈，用于存放已摆放棋子的状态
    for(iLine=0;iLine<15;iLine++)
       b[iLine]=c[iLine]=0;  //主从对角线标记初始化，表示无冲突
    placeQueen(0);
    return 0;
}

void placeQueen(int i)
{
	int iColumn;
	for(iColumn=0;iColumn<8;iColumn++)
	{
		if(a[iColumn]==0 && b[i-iColumn+7]==0 && c[i+iColumn]==0) //如果无冲突
		{
			Push(aStack,i);//放皇后
			Push(aStack,iColumn);
		    a[iColumn]=1;   //标记，下一次该列上不能放皇后
		    b[i-iColumn+7]=1;  //标记，下一次该主对角线上不能放皇后
		    c[i+iColumn]=1;   //标记，下一次该从对角线上不能放皇后
		    if(i<7) placeQueen(i+1);  //如果行还没有遍历完，进入下一行
		    else     //否则输出
			{
				//输出棋盘状态
				int iLine,iColumn,iQueenX,iQueenY;
				int *mark;
				mark=GetMark(aStack);//保存栈顶
				printf("第%d种状态为：\n",++iQueenNum);
				for(iLine=0;iLine<8;iLine++)
				{
					Pop(aStack,iQueenY);
					Pop(aStack,iQueenX);
				    for(iColumn=0;iColumn<8;iColumn++)
					{
						if(iColumn==iQueenY) printf("@  ");
						else printf("*  ");
					}
				    printf("\n");
				}
				SetMark(aStack,mark);//恢复栈顶
			   }
			   //如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置
			   Pop(aStack,iColumn);
			   Pop(aStack,i);
			   a[iColumn]=0;
			   b[i-iColumn+7]=0;
			   c[i+iColumn]=0;
		}
	}
}