Problem 534

Weak Queens

The classical eight queens puzzle is the well known problem of placing eight chess queens on a 8×8 chessboard so that no two queens threaten each other. Allowing configurations to reappear in rotated or mirrored form, a total of 92 distinct configurations can be found for eight queens. The general case asks for the number of distinct ways of placing n queens on a n×n board, e.g. you can find 2 distinct configurations for n=4.

Lets define a weak queen on a n×n board to be a piece which can move any number of squares if moved horizontally, but a maximum of n−1−w squares if moved vertically or diagonally, 0≤w<n being the “weakness factor”. For example, a weak queen on a n×n board with a weakness factor of w=1 located in the bottom row will not be able to threaten any square in the top row as the weak queen would need to move n−1 squares vertically or diagonally to get there, but may only move n−2 squares in these directions. In contrast, the weak queen is not handicapped horizontally, thus threatening every square in its own row, independently from its current position in that row.

Let Q(n,w) be the number of ways n weak queens with weakness factor w can be placed on a n×n board so that no two queens threaten each other. It can be shown, for example, that Q(4,0)=2, Q(4,2)=16 and Q(4,3)=256.

Let $S(n)=\displaystyle\sum_{w=0}^{n-1} Q(n,w)$.

You are given that S(4)=276 and S(5)=3347.

Find S(14).

弱皇后问题

八皇后问题是一个著名的经典问题：将八枚皇后棋子摆放在8×8的国际象棋棋盘上，且它们两两之间均不构成威胁。考虑旋转和翻转，八皇后问题一共有92种不同的摆放方式。将八皇后问题一般化，也即将n枚皇后棋子摆放在n×n的棋盘上的不同摆放方式数，例如，当n=4时只存在2种不同的摆放方式。

我们在n×n棋盘上定义一种弱皇后棋子，当横向移动时它能够移动任意步数，但在纵向移动或沿对角线移动时至多只能移动n-1-w步，其中0≤w<n称为“弱系数”。例如，在n×n棋盘上，如果将弱系数为w=1的弱皇后摆放在最下一行，无法威胁到任何最上一行的方格，因为它需要在纵向或沿对角线移动n-1步才可能到达最上一行，但是它只能纵向或沿对角线移动至多n-2步。相反地，由于弱皇后的横向移动不受限制，无论它处在这一行的哪个位置，都能够威胁到同一行的所有方格。

将n枚弱系数为w的弱皇后棋子摆放在n×n的棋盘上，且它们两两之间均不构成威胁，考虑旋转和翻转，不同的摆放方式数目记为Q(n,w)。我们可以计算得出Q(4,0)=2，Q(4,2)=16以及Q(4,3)=256。

记$S(n)=\displaystyle\sum_{w=0}^{n-1} Q(n,w)$。

已知S(4)=276以及S(5)=3347。

求S(14)。