nqueuefei1.c

《数据结构-使用C语言》第三版

//n皇后问题的非递归算法
#include<stdio.h>
#define MaxStackSize 100
typedef int DataType;

#include"SeqStack.h"  //包含堆栈的相关操作，一般的数据结构书上都有详细的讲解。 

int n, result=0, line[100];
int main()
{
	int i, j, t;
	SeqStack row;  //栈顶记录当前行 
	int Judge(int t);
	void Display();
	
	scanf("%d",&n);  //此程只能输出n>=4的情况 

	getchar();
	t=0;  //指示当前行 
	j=0;  //指示当前列 
	for(i=0;i<n;i++)
	line[i]=-1;
	StackInitiate(&row);
	
	while(line[0]<n)
	{
		
		if(j>=n)//
		{
			StackPop(&row, &t);//回溯 
			if( line[0]==n-1 && StackNotEmpty(row)<=0 )
				break; //此句说明所有的可能结果都已经搜索完毕 
			j=line[t]+1;
			if(j>=n)continue;
		}
		line[t]=j;
		
		if(Judge(t)==0) //判断成立，向前推进一步 
		{
			StackPush(&row, t);
			line[t]=j;
			t++;
			j=0;
			if(t>=n)  //走到第n-1行后，输出结果 
			{
				Display();
				StackPop(&row, &t);
				j=line[t]+1;
			}
		}
		else j++;
		
	}
	getchar();
}
			
void Display()
{//输出结果 
	int i, j;
	printf("Display %d\n",result++);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		if(line[i]==j)
		printf("Q");
		else printf("*");
		
		printf("\n");
	}
	getchar();
}

int Judge(int t)
{//判断 
	int i, flag=0;
	for(i=0;i<t;i++)
	{
		if(line[i]==line[t] || line[i]+i==line[t]+t || line[i]-i==line[t]-t)
		{
			flag=1;
			break;
		}
	}
	return flag;
}