蓝桥杯基础练习VIP-2n皇后问题-题解（C语言代码）

#include <stdio.h>
int num,a[101][101],way=0;
int judge(int n,int m,int k)	//判断同行，列，斜角有没有相同的皇后，可放入时放入1 
{
	int i,j;
	for(i=0;i<num;i++)		//行或者列有白皇后 
		if(a[n][i]==k||a[i][m]==k)
			return 0;
	for(i=n,j=m;i>=0&&j>=0;i--,j--)	//左上角 
		if(a[i][j]==k)
			return 0;
	for(i=n,j=m;i>=0&&j<num;i--,j++)	//右上角 
		if(a[i][j]==k)
			return 0;
	for(i=n,j=m;i<num&&j>=0;i++,j--)	//左下角 
		if(a[i][j]==k)
			return 0;
	for(i=n,j=m;i<num&&j<num;i++,j++)	//右下角 
		if(a[i][j]==k)
			return 0;
	return 1;
}
void n_black(int n)	//放入黑色 
{	int i,j;
	if(n>=num)
	{
		way++;	//能够放完，该方法可行，加一 
	/*	for(i=0;i<num;i++)	//输出某种放置方法 
			{
				for(j=0;j<num;j++)
					printf("%d ",a[i][j]);
			printf("\n");
			}
		printf("\n\n");	*/
		return;
	}
	else {
		for(i=0;i<num;i++)//每行的每一个都要试探一遍 
			{
				if(a[n][i]==1&&judge(n,i,3)==1)//当该处可放皇后并且行列对角线等不同时，放入 ，放入黑皇后的标3 
					{
						a[n][i]=3;//放入 
						n_black(n+1);//回溯 ，放入下一个皇后 
						a[n][i]=1;//该种方式遍历完后回复原始 
					}
			}
	} 
}

void n_white(int n)	//放入白色 
{	int i;
	if(n>=num)	//白色放完后放黑色 
	{
		n_black(0);
		return;
	}
	else {
		for(i=0;i<num;i++)	//每行的每一个都要试探一遍 
			{
				if(a[n][i]==1&&judge(n,i,2)==1)	//当该处可放皇后并且行列对角线等不同时，放入 ，放入白皇后处标2 
				{
					a[n][i]=2;	//放入 
					n_white(n+1);//回溯 ，放入下一个点 
					a[n][i]=1;	//该种方式遍历完后回复原始 
				}
			}
	}
}
	
int main()
{
	scanf("%d",&num);
	int i,j;
	for(i=0;i<num;i++)
		for(j=0;j<num;j++)
			scanf("%d",&a[i][j]);
	n_white(0);	//先放白色再放黑色 
	printf("%d",way);
	return 0;
 }