nqueue.c

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

// n皇后问题
#include<stdio.h>
int n, result=0, line[100];  //line[i]中存放的是第i行中皇后的位置 
int main()
{
	int Judge(int t);
	void Display();
	void fan(int t);
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		fan(0);  //递归调用 
	}
	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++)  //只需要与0到t-1行已放的t个皇后相比较 
	{
		if(line[i]==line[t] || line[i]+i==line[t]+t || line[i]-i==line[t]-t)
		{//判断能不能在这一行放皇后 
			flag=1; //flag为1说明不能放  
			break;
		}
	}
	return flag;
}

void fan(int t)
{
	for(line[t]=0; line[t]<n; line[t]++) //line[t]的值只能是0到n-1 
	{ //这一条语句应该用得比较巧妙，哈哈，自夸一下 
		if(Judge(t))continue;
		
		if(t!=n-1)
		fan(t+1);
		else 
		Display();
	}
}