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

时间:2022-03-11 11:41:03

问题描述

  给定一个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

样例输入

4

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1

样例输出

0


先看一下n皇后问题的解法

#include<iostream>using namespace std;
int ans, q[8], n;
void Q(int row)
{
if (row == n) { ans++; }
else
{
for (int i = 0;i < n;i++) //遍历第row行第i列,看哪一个可以放下皇后
{
bool flag = true;
q[row] = i; //假设第row行的皇后放到i列,存起来

for (int j = 0;j < row;j++) //检查j行q[j]列的其他皇后是否跟新放入的兼容
{
if (q[j] == q[row] || q[j] + j == q[row] + row || q[j] - j == q[row] - row)
{
flag = false;
break;
}
}
if (flag)
Q(row + 1);
}
}
}
int main()
{
while (cin >> n)
{
ans = 0;
Q(0);
cout << ans << endl;
}
return 0;
}

回溯法,思路,因为每行必须放一个,所以就省去了一维,每次只探索列数

所以用Q(row)的递归深度代表行数,每次递归都探索该row行的全部列,放入皇后之后再检查跟上面行的皇后是否兼容,用q[8]存皇后的位置。

那么回到本题,2n皇后问题,从n皇后问题拓展,我们可以认为是放两次n皇后,也就是先放黑,满足n黑皇后问题后在之前的情况之下再做n白皇后问题。

#include<iostream>using namespace std;int n, ans;bool board[8][8];int q[8][2];//拓展一个长度来存白皇后位置void Q(int row, bool isBlack){	if (row == n&&isBlack) { Q(0, false); }	if (row == n && !isBlack) { ans++; }	if (isBlack)	{		for (int i = 0;i < n;i++)    //测试第row行,第i列的位置		{			if (board[row][i])   //此处可以放棋子			{				q[row][0] = i;				bool flag = true;				for (int j = 0;j < row;j++)   //测试第j行,q[j][0]列的黑皇后是否兼容				{					if (q[row][0] == q[j][0] || row - q[row][0] == j - q[j][0] || row + q[row][0] == j + q[j][0])					{						flag = false;						break;					}				}				if (flag)					Q(row + 1, true);			}		}	}	else  //白皇后	{		for (int i = 0;i < n;i++)		{			if (board[row][i] && q[row][0] != i)			{				bool flag = true;				q[row][1] = i;				for (int j = 0;j < row;j++)				{					if (q[row][1] == q[j][1] || row - q[row][1] == j - q[j][1] || row + q[row][1] == j + q[j][1])					{						flag = false;						break;					}				}				if (flag) Q(row + 1, false);			}		}	}}int main(){	bool num;	while (cin >> n)	{		ans = 0;		for (int i = 0;i < n;i++)		{			for (int j = 0;j < n;j++)			{				cin >> num;				board[i][j] = num;			}		}		//地图存完了,开始遍历		Q(0, true);		cout << ans << endl;	}	return 0;}
因为题目要求,在探索棋盘时还要注意该位置是否可以放棋子(以及该位置有没有黑皇后)