Project Euler Problem 628

Solution

Answer: 210286684

Let the pawns define a permutation $\pi\in S_n$, where the pawn in row $i$ is in column $\pi(i)$.

A classical lattice-path argument shows:

the position is blocked iff there exists a $k<n$ such that

$${\pi(1),\pi(2),\dots,\pi(k)}={1,2,\dots,k},$$

i.e. the permutation is decomposable;

therefore the open positions are exactly the indecomposable permutations, except for the completely anti-diagonal configuration, which contributes one extra obstruction.

Hence

$$f(n)=a_n-1,$$

where $a_n$ is the number of indecomposable permutations of size $n$.

The standard recurrence for indecomposable permutations is

$$a_n=n!-\sum_{k=1}^{n-1} a_k (n-k)!.$$

A useful rearrangement gives the telescoping form

$$f(n)\equiv n! - 2\sum_{k=1}^{n-1} k! \pmod M,$$

with

$$M=1,008,691,207.$$

So we compute:

$$f(10^8)\equiv (10^8)!-2\sum_{k=1}^{10^8-1} k! \pmod{1,008,691,207}.$$

The computation is straightforward in modular arithmetic using a running factorial.

Python implementation:

MOD = 1008691207
N = 10**8

fact = 1
s = 0

for k in range(1, N):
    fact = (fact * k) % MOD
    s = (s + fact) % MOD

fact = (fact * N) % MOD

ans = (fact - 2 * s) % MOD
print(ans)

Running this computation yields:

Answer: 728378714