#P1070. N皇后问题

N皇后问题

题目描述

在一张NNN * N的国际象棋棋盘上,放置NN个皇后,使得所有皇后都无法互相直接攻击得到,(皇后可以直接攻击到她所在的横行,数列,斜方向上的棋子),现在输入一个整数NN,表示在NNN*N的棋盘上放NN个皇后,请输出共有多少种使得所有皇后都无法互相直接攻击得到的方案数。 例如下面这样的摆法,是4皇后的一个解 (1代表有皇后,0代表没有)

0  1  0  0
0  0  0  1
1  0  0  0
0  0  1  0 

输入格式

一个整数NN

输出格式

能使得在NNN*N的国际象棋棋盘上放置NN个皇后,并且所有皇后都无法互相直接攻击得到的方案数

样例

####样例输入1

4

####样例输出1

2

####样例输入2

8

####样例输出2

92

数据范围与提示

1N131 \le N \le 13