[蓝桥杯][基础练习VIP]2n皇后问题

题目描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入

输入的第一行为一个整数n，表示棋盘的大小。

接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出

输出一个整数，表示总共有多少种放法。

样例输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

2

C语言AC代码

先放入白皇后，再放黑皇后

#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;
 } 

运行结果：

去掉在黑皇后的方法加一下面的注释可都得到如何放置的，如下图：