プロジェクトオイラー628.

この記事の所要時間: 458

No.628 Open chess positions

問題.

与えられたサイズのチェス盤の上にチェスの駒を配置することを考える. 以下では, n\times n のチェス盤において, 各行, 各列に1つだけあるような, n 個のポーンの配置を考える.

ルークが盤の左下隅のマスから右上隅のマスまで, 縦, 横の移動の繰り返しのみで, ポーンのあるマスを通らずに到達できるような配置を “開いた配置” と呼ぶことにする. (左下隅, 右上隅のマスもポーンは置かれていないとする. )

n\times n のチェス盤における開いた配置の個数を f(n) とする.

例えば, f(3)=2 であり, 3\times 3 のチェス盤における開いた配置は以下の図の2つである.

          

また, f(5)=70 となる.

f\left(10^8\right)\bmod{1008691207} を求めよ.

考え方とプログラム例.

開いた配置の個数を直接数えるのは難しいので, ここではすべての駒の配置から “開いていない” 配置 (“閉じた”配置) の個数を引くことを考えます.

“閉じた”配置は, 左下隅から右上隅まで縦横の移動のみではたどり着けない配置です.

ポーンの配置が, 各行,列 に 1 個しか置けないことを考慮すると, “閉じた”配置とは, 以下のうち少なくとも一方が成り立つような配置だとわかります.

\left(P_i\right) : (i,1), (i+1,2),\ldots, (n,n-i+1) にすべてポーンがある. (i=1, 2, 3, \ldots, n)

\left(Q_j\right) : (1, j), (2, j+1),\ldots, (n-j+1,n) にすべてポーンがある. (j=1, 2, 3, \ldots, n)

(\ast1)

(P_1Q_1 は同じ条件になります.)

ここで, チェス盤の上から i 行目, 左から j 行目のマスを (i, j) と表しています(\ast 2).

つまり, 右下がりの斜めの列のどこかがすべてポーンで塞がれているような状態です.

まず, (P_i) を満たすようなポーンの配置は, 残りの i-1 個のポーンの配置を考えると

\begin{align*} (i-1)! \end{align*}

通りです.

同様に, (Q_i) を満たすようなポーンの配置も (i-1)! 通りです.

次に, (P_i)(Q_j) が同時に満たされるような配置を考えます.

このとき i+j\geqq n+2 である必要があり, このような配置は残りの i+j-n-2 個のポーンを考えればよく,

\begin{align*} (i+j-n-2)! \end{align*}

通りとなります.

N\times nの盤へのすべてのポーンの置き方は n! 通りなので, (P_1), (Q_1) がかぶっていることも考慮すれば

\begin{align*} f(n) &= n! - 1-2\sum_{i=2}^n (i-1)!+\sum_{i+j\geqq n+2}(i+j-n-2)!\\ &= n! - 1 - 2\sum_{i=1}^{n-1} i! + \sum_{k=n+2}^{2n} (2n-k+1)\cdot (k-n-2)!\\ &= n! - 1 - 2\sum_{i=1}^{n-1} i! + \sum_{i=0}^{n-2} (n-i-1)\cdot i!\\ &= n!+\sum_{i=1}^{n-1}(n-i-3)i!+n-2\\ &= \left(\left(\left(1\times n-2\right)\times(n-1)-1\right)\times(n-2)\cdots+n-5\right)\times2+n-4\\ &\quad +n-2 \end{align*}

となります. 最後の式は, プログラムで計算するときに i!i=1, 2, \ldots, n についてそれぞれ計算すると大変なので, まとめて計算するための変形です.

今回は C言語のプログラム例です.

答えはこの下にあります. 反転してください.

A.210286684

注.

(\ast1). チェスにおいてこのような斜めの列のことをダイアゴナル(diagonal)といいます. この用語に従えば, 条件(P_i) は (i, 1)-(N,N-i+1)ダイアゴナルにすべてポーンがある, というような言い方になります.

(\ast2). 通常の8×8のチェス盤のマスでは, 各行を下から 1,2,…,8 として, 各列を左から a,b, …, h として表します. 例えば左上隅のマスは a8, 右下隅のマスは h1.

ここでは式で扱いやすいように列の方も 1,2,… で考えています.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加