*[[Problem 534:https://projecteuler.net/problem=534]] 「弱いクイーン」 [#rc9bbaac]
古典的なパズルである''8クイーンパズル''は, 8x8 のチェス盤上にお互い取られることがないように8個のクイーンを配置するというおなじみの問題である. 回転や鏡像として作られる配置を含めると, 8クイーンの場合計 92 個の配置が可能である. '''n'''x'''n''' の盤上に '''n''' 個のクイーンを配置する場合の数を求める一般解によれば, 例えば '''n''' = 4 の場合 2 個の配置が求められる.
水平移動は何マス目でもできるが, 0 ≤ '''w''' < '''n''' の範囲の「弱さ係数」があって, 垂直と対角線上の移動は最大 '''n''' - 1 - '''w''' マスしかできない, という%%%弱いクイーン%%%を定義しよう. 例えば, 弱さ係数 '''w''' = 1 の場合に '''n'''x'''n''' の盤上の一番下の列に配置された弱いクイーンは, 一番上の列のマスのクイーンを取ろうとすると垂直または対角線上に '''n''' - 1 の移動が必要になるが, '''n''' -2 しか移動できないため取ることはできない. それとは対照的に, 弱いクイーンは水平に対しては制限がないので, 列内の現在の位置にかかわらず, 自身が配置されている列のすべてのマスを取ることができる.
'''n''' 個の弱いクイーンを, 弱さ係数 '''w''' で, '''n'''x'''n''' の盤上にお互い取られることがないように配置できる方法の数を Q('''n''', '''w''') としよう. 例として, Q(4,0)=2, Q(4,2)=16, そして Q(4,3)=256 であることがわかる.
&ref(p534_eq.png,nolink); としよう.
'''S'''(4)=276, '''S'''(5)=3347 が与えられている.
S(14) を求めよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
