经典的八皇后难题是一个众所周知的问题,把八个棋皇后放在一个8×8的棋盘上,这样就不会有两个皇后互相威胁。允许配置以旋转或镜像的形式重新出现,总共可以为八个皇后找到92个不同的配置。一般情况下,需要求在n×n板上放置n个皇后的不同方式的数目,例如,对于n=4,可以找到2个不同的配置。

让我们在N×N棋盘上定义一个弱皇后,如果它是水平移动的,它可以移动任意数量的正方形,但是如果垂直或对角地移动,则最多有N-1-W方块,0 < W < N是“弱因子”。例如,位于最下面一行的弱因子为w=1的n×n棋盘上的弱皇后将无法威胁到最上面一行的任何正方形,因为弱皇后需要垂直或对角移动n-1个正方形才能到达那里,但只能在这些方向移动n-2个正方形。相比之下,弱皇后在水平方向上没有残疾,因此独立于当前在该排中的位置,威胁着自己排中的每一个正方形。

设Q(n,w)为n×n棋盘上n个弱因子为w的弱皇后不相互威胁的方法个数。例如,可以得出Q(4,0)=2,Q(4,2)=16和Q(4,3)=256。

设 S(n)=∑w=0->n−1 Q(n,w).

已知 S(4)=276 , S(5)=3347.

求S(14).