main.cpp

著名的n皇后问题 在一个棋盘上

#include <stdio.h>
#define N 100
#define n 8			//n皇后问题
int main()
{
	int y[N];			//每一个皇后的列坐标
	int count[N];
	for(int i=0;i<N;i++)
	{
		y[i]=1;
		count[i]=1;
	}
	int lie[N]={0};			//列
	int leftline[N]={0};	//左对角线
	int rightline[N]={0};	//右对角线
	
	int flag[N][N]={0};		//每一个位置的标志位
	int t=1;
	int total=0;
	while(t>0)
	{
		while(lie[y[t]]==1	||	leftline[t-y[t]+n]==1	||	rightline[t+y[t]]==1)
		{
			if(count[t]==n)	
			{	
				count[t]=1;
				y[t]=1;
				goto L1;
			}
			y[t]++;
			count[t]++;
			
		}

		lie[y[t]]=1;
		leftline[t-y[t]+n]=1;
		rightline[t+y[t]]=1;
		flag[t][y[t]]=1;
		
	
		if(t==n)
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=n;j++)
					printf("%3d",flag[i][j]);
				printf("\n");
			}
			printf("\n");
			//getchar();
			total++;

			lie[y[t]]=0;
			leftline[t-y[t]+n]=0;
			rightline[t+y[t]]=0;
			flag[t][y[t]]=0;

			y[t]++;
			count[t]++;
			if(count[t]>n)	
			{
				count[t]=1;
				y[t]=1;
				goto L1;
			}
			goto L2;
		}
		
		t++;

		goto L2;

L1:
		t--;
		if(t==0)	break;
		lie[y[t]]=0;
		leftline[t-y[t]+n]=0;
		rightline[t+y[t]]=0;
		flag[t][y[t]]=0;
		
		y[t]++;
		count[t]++;
		if(count[t]>n)
		{
			count[t]=1;
			y[t]=1;
			goto L1;
		}

L2:
		;
	}
	printf("\n");
	printf("Total is %d\n",total);
	return 0;
}