N皇后

题目描述

ps: 这是2023CEIT新生考核的最后一题...

$N-$皇后问题是指将 $N$ 个皇后放在 $N \times N$ 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 $n$，请你输出所有的满足条件的摆放方案的数量。

输入格式

共一行，包含整数 $n(1 \le n \le 10)$。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

4

样例输出 #1

2

提示

在 $4 \times 4$ 的棋盘上，有且仅有如下两种摆法： 其中 $Q$ 代表皇后，$.$ 代表空格。

#1:
.Q..
...Q
Q...
..Q.
#2:
..Q.
Q...
...Q
.Q..