八皇后问题(Eight Queens)

题目描述

在 8×8 的国际象棋棋盘中放置八个"皇后"，要求任意两个皇后不能处在同一行、同一列或同一条对角线上。问一共有多少种合法的放置方案？

为了通用，本题推广为 n 皇后问题：在 n×n 的棋盘上放置 n 个皇后，求合法方案数。

输入格式

一行一个整数 n（皇后个数，也是棋盘边长）。

输出格式

一个整数，表示合法方案的总数。

样例输入

8

样例输出

92

数据范围

1 ≤ n ≤ 13。