【ACM】3个皇后不能相遇

在n×n的方格棋盘放置3个皇后，任意两个皇后不能相邻，否则她们会相互攻击（也就是说，以一个皇后所在位置为中心的九宫格中不能有其他的皇后。皇后的上下左右四个格子，以及左上、左下，右上、右下四个格子都不能有其他皇后，下图是3×3的棋盘放置3个皇后的方法）。 对于给定的n，求出有多少种合法的放置方法。

![3个皇后不能相遇.JPG](https://blog.fivk.cn/usr/uploads/2021/05/3938420174.jpg)

### 输入格式:

输入正整数n（n≤10），表示棋盘大小为n×n个方格。

### 输出格式:

输出，在n×n的方格棋盘放置3个皇后，合法的放置方法数。

### 输入样例1:

在这里给出一组输入。例如：

```in
3
```

### 输出样例1:

在这里给出相应的输出。例如：

```out
8
```

### 输入样例2:

在这里给出一组输入。例如：

```in
2
```

### 输出样例2:

在这里给出相应的输出。例如：

```out
0
```

### 我的代码（半成品）

感觉有点像八皇后问题但是我可能少了些判断。

```cpp
#include<bits/stdc++.h>

using namespace std;

int a[12][12];
int n,t=0;

void dfs(int x)
{
	int i;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==0&&a[i+1][j]==0&&a[i-1][j]==0&&a[i][j+1]==0&&a[i][j-1]==0&&a[i+1][j+1]==0&&a[i-1][j-1]==0)
			{
				a[i][j]=1;
				if(x<3)
				{
					dfs(x+1);
				}else{
					t++;
					for(int a1=1;a1<=n;a1++)
					{
						for(int b1=1;b1<=n;b1++)
						{
							cout<<a[a1][b1]<<" ";
						}
						cout<<endl;
					}
					cout<<endl<<endl;
				//	exit(1);
				}
				a[i][j]=0;
			}
		}
	}
}

int main()
{
	cin>>n;
	dfs(1);
	cout<<t;
	return 0;
}

```

最后修改：2021 年 05 月 24 日