nqueuefei.c

来自「《数据结构-使用C语言》第三版」· C语言 代码 · 共 94 行

//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;
	//int stack[100];  //栈顶记录当前行 
	SeqStack row;
	int Judge(int t);
	void Display();
	while(scanf("%d",&n)!=EOF)
	{
		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);
				j=line[t]+1;
				if(j>=n)continue;
			}
			if(Judge(j)==0)
			{
				StackPush(&row, t);
				line[t]=j;
				t++;
				j=0;
				if(t>=n)
				{
					Display();
					StackPop(&row, &t);
					j=line[t]+1;
				}
			}
			else 
			{
				//StackPop(&row, &t);
				j++;
				/*if(j>=n)
				{
					StackPop(&row, &t);
					j=line[t]+1;
				}*/
			}
			/*if(line[t]>=n)
			{
				StackPop(&row, &t);
				line[t]++;
			}*/
		}
	}
	return 0;
}
			
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;
}