题目描述
给出一个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;
}