题目描述

给出一个n*n的国际象棋棋盘，你需要在棋盘中摆放n个皇后，使得任意两个皇后之间不能互相攻击。具体来说，不能存在两个皇后位于同一行、同一列，或者同一对角线。请问共有多少种摆放方式满足条件。

输入描述

一行，一个整数n(1≤n≤12)，表示棋盘的大小。

输出描述

输出一行一个整数，表示总共有多少种摆放皇后的方案，使得它们两两不能互相攻击。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int pos[20];//用于记录第i行皇后的位置pos[i]
int sum;
int n;
int num;//记录几个皇后
bool f = true;
void dfs(int r)
{
	if (num == n) {
		sum++;
		return;
	}
	if (r == n + 1) return;
	for (int i = 1; i <= n; i++)//从第一列遍历到最后一列
	{
		for (int j = 1; j <= r; j++)//遍历所有之前存在皇后的位置
		{
			if (i == pos[j] ||( r - j == abs(pos[j] - i)))//如果在同一列或者对角线上则下一列
			{
				f = false;
				break;
			}
		}
		if (f) {//如果可以放则进行继续dfs
			pos[r] = i;
			num++;
			dfs(r + 1);
			num--;//回溯
			pos[r] = 0;
		}
		f = true;
	}
		
}
int main()
{
	cin >> n;
	dfs(1);
	cout << sum << endl;
}