题目描述

相信大家都听过经典的 八皇后 问题吧？这个游戏要求在一个 8×8 的棋盘上放置 8 个皇后，使 8 个皇后互相不攻击（攻击的含义是有两个皇后在同一行或同一列或同一对角线上）。

桐桐对这个游戏很感兴趣，也很快解决了这个问题。可是，她想为自己增加一点难度，于是她想求出 n 皇后的解的情况。你能帮助她吗？

输入格式

一个数 n ( 1 ≤ n ≤ 13 )，表示为 n 皇后问题。

输出格式

一个数，表示 n 皇后问题的解法总数。

样例

8

92

解题思路

因为 n*n 的棋盘上要放 n 个皇后，所以每行都要放一个皇后才能放得完 n 个，也不可能某一行放 2 个皇后，否则同一行的 2 个皇后就互相攻击了。因此，我们可以用一个数组 x[i] 来记录第 i 行的皇后是放在哪一列。

我们只需要把 x[i] 数组填完，就能得到一种放置方案。来到这里，是不是觉得这条题和桐桐的全排列有几分相似？不同的地方，是要把皇后的放置规则在 DFS 函数里体现出来。枚举 x[l] 能填什么(第 l 行的皇后的位置) 有几个影响因素：

1. 这一列没有别的皇后

2. [l,x[l]] 这个格子的 “左上到右下” 斜线上没有别的皇后。之前学习二维数组的时候我们有一个知识：标识 [i,j] 的这条斜线可以通过 i-j+n 来标识，i-j+n 的取值范围是 1 到 2*n-1

3. [l,x[l]] 这个格子的 “左下到右上” 斜线上没有别的皇后。标识 [i,j] 的这条斜线可以通过 i+j-1 来标识，i+j-1 的取值范围是 1 到 2*n-1

4. 因为题目只问方案数有多少个，而不是输出每一个方案的内容，所以，实际上并不需要真的去填 x[i]，x 数组可以不存在。只需要标记好哪些列已经有皇后，哪些斜线有皇后就可以了。

DFS 算法尤其像枚举，DFS 是递归调用，第 i 层 DFS 调用往往是枚举方案里第 i 个变量的值。

完善程序

#include<bits/stdc++.h>
using namespace std;
bool col[14],xie1[50],xie2[50];
// col 数组用于纪录哪些列已经放了皇后
// xie1 用于记录“从左上角到右下角”斜线是否放了皇后
// xie2 用于记录“从左下角到右上角”斜线是否放了皇后
int n,ans; 
void dfs(int l) // 决定第 l 行的皇后的列号
{
	if(l==填空(1)) // 意味着找到了一种可行方案
		填空(2);
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(!col[i] && !xie1[l+i-1] && !xie2[l-i+n])
			{
				// 第 l 行的皇后放在第 i 列。
				填空(3) = true; //给第 i 列打上标记
				填空(4) = true; //给“从左上角到右下角”打上标记
				填空(5) = true; //给“从左下角到右上角”打上标记
				
				dfs( 填空(6) );
				
				填空(3) = false;
				填空(4) = false;
				填空(5) = false;
			}
		}
	}
}
int main()
{
	scanf("%d",&n);

	dfs(填空(7));

	printf("%d",ans);

	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}