Problem 534 「弱いクイーン」

古典的なパズルである8クイーンパズルは, 8x8 のチェス盤上にお互い取られることがないように8個のクイーンを配置するというおなじみの問題である. 回転や鏡像として作られる配置を含めると, 8クイーンの場合計 92 個の配置が可能である. nxn の盤上に n 個のクイーンを配置する場合の数を求める一般解によれば, 例えば n = 4 の場合 2 個の配置が求められる.

水平移動は何マス目でもできるが, 0 ≤ w < n の範囲の「弱さ係数」があって, 垂直と対角線上の移動は最大 n - 1 - w マスしかできない, という弱いクイーンを定義しよう. 例えば, 弱さ係数 w = 1 の場合に nxn の盤上の一番下の列に配置された弱いクイーンは, 一番上の列のマスのクイーンを取ろうとすると垂直または対角線上に n - 1 の移動が必要になるが, n -2 しか移動できないため取ることはできない. それとは対照的に, 弱いクイーンは水平に対しては制限がないので, 列内の現在の位置にかかわらず, 自身が配置されている列のすべてのマスを取ることができる.

n 個の弱いクイーンを, 弱さ係数 w で, nxn の盤上にお互い取られることがないように配置できる方法の数を Q(n, w) としよう. 例として, Q(4,0)=2, Q(4,2)=16, そして Q(4,3)=256 であることがわかる.

&ref(): File not found: "p534_eq.png" at page "Problem 534"; としよう.

S(4)=276, S(5)=3347 が与えられている.

S(14) を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-11-15 (日) 00:47:10