Problem 628: Open Chess Positions

Project Euler Problem 628 Solution

EulerSolve provides an optimized solution for Project Euler Problem 628, Open Chess Positions, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary On an $n\times n$ board, exactly one square is blocked in every row and exactly one square is blocked in every column. So every board is determined by a permutation $p\in S_n$, where the blocked square in row $i$ lies in column $p_i$. A position is called open if there exists a path from the top-left square to the bottom-right square using only right and down moves and never stepping on a blocked square. If $f(n)$ denotes the number of open boards, the task is to compute $f(10^8)$ modulo $1008691207$. The important point is that the implementations do not search for paths on the huge board. They use an exact combinatorial identity that reduces the whole problem to factorials and a prefix sum of factorials. Mathematical Approach Let $f(n)$ be the number of open permutation boards of size $n$. Since every placement is a permutation, there are $n!$ total configurations. The mathematical job is therefore to understand which permutations force every monotone path to fail. Step 1: Encode the Board as a Permutation Choose a permutation $p=(p_1,\dots,p_n)$. The blocked cells are then $$ (1,p_1),(2,p_2),\dots,(n,p_n). $$ Because the blocked columns are all distinct, the board is a permutation matrix of forbidden cells. This observation removes the need to think about arbitrary obstacle patterns....

Detailed mathematical approach

Problem Summary

On an $n\times n$ board, exactly one square is blocked in every row and exactly one square is blocked in every column. So every board is determined by a permutation $p\in S_n$, where the blocked square in row $i$ lies in column $p_i$. A position is called open if there exists a path from the top-left square to the bottom-right square using only right and down moves and never stepping on a blocked square.

If $f(n)$ denotes the number of open boards, the task is to compute $f(10^8)$ modulo $1008691207$. The important point is that the implementations do not search for paths on the huge board. They use an exact combinatorial identity that reduces the whole problem to factorials and a prefix sum of factorials.

Mathematical Approach

Let $f(n)$ be the number of open permutation boards of size $n$. Since every placement is a permutation, there are $n!$ total configurations. The mathematical job is therefore to understand which permutations force every monotone path to fail.

Step 1: Encode the Board as a Permutation

Choose a permutation $p=(p_1,\dots,p_n)$. The blocked cells are then

$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$

Because the blocked columns are all distinct, the board is a permutation matrix of forbidden cells. This observation removes the need to think about arbitrary obstacle patterns. The geometry is rigid enough that the counting problem can be translated into a combinatorial question about permutations.

A monotone path uses only right and down moves, so only the relative order of the blocked cells matters. That is the reason a closed formula exists at all.

Step 2: Switch from Path Search to Barrier Counting

It is more convenient to think about closed boards, where every monotone path is blocked. Those closed boards can be organized by the depth of the first effective barrier that separates the reachable northwest region from the unreachable southeast region.

The simplest closed families occur near the corners: the starting square may already be blocked, the ending square may already be blocked, or a very shallow corner barrier may immediately cut off all progress. After those easy cases, the remaining closed boards are indexed by an interior barrier depth. Once that depth is fixed, the leftover rows and columns can be permuted freely, which is why factorial terms dominate the final answer.

Step 3: Use the Exact Counting Identity

The C++, Python, and Java implementations all evaluate the same exact identity:

$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$

together with

$$ f(n)=0 \qquad (n\le 2). $$

The large negative factorial terms remove the dominant closed families. The constant correction $2$ and the tail term $(n-3)\sum_{k=0}^{n-4}k!$ add back the configurations that were removed too often when the barrier families overlap. For the actual computation, this identity is the whole story: once it is known, there is no need to inspect individual paths.

Step 4: Reduce the Problem to Four Factorials and One Prefix Sum

Define the factorial prefix sum

$$ S_m=\sum_{k=0}^{m} k!. $$

Then the formula becomes

$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$

So the entire computation consists of two tasks:

$$ \text{compute } S_{n-4}, \qquad \text{and compute } (n-3)!, (n-2)!, (n-1)!, n! \pmod{1008691207}. $$

This is exactly why the implementations can stay linear and use constant extra memory.

Worked Example: $n=5$

For $n=5$, the prefix sum is

$$ S_1=0!+1!=1+1=2. $$

Substituting into the exact identity gives

$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$

This matches the standard small checkpoint. The same formula also gives $f(3)=2$, which is the smallest nontrivial open case.

How the Code Works

The implementations treat the problem as pure modular arithmetic. They first handle the small base case $n\le 2$, where the answer is $0$. For $n\ge 3$, they maintain one running factorial and one running sum of factorials.

The first pass accumulates

$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207}. $$

Then the same running factorial is continued through the last four multiplications so that the implementation obtains $(n-3)!$, $(n-2)!$, $(n-1)!$, and $n!$ modulo the given prime. Those values are substituted directly into the closed formula, and the result is normalized back into the standard modular range.

The C++ implementation also performs a small brute-force verification for tiny $n$: it enumerates permutations, checks path existence with a grid dynamic program, and confirms that the formula matches exact counting before evaluating the large target.

Complexity Analysis

The running time is $O(n)$ modular multiplications, because the algorithm makes one forward pass from $1$ up to $n$. The extra memory usage is $O(1)$, since only a few integers are stored for the current factorial, the factorial prefix sum, and the final expression. That scaling is exactly what makes $n=10^8$ practical.

Footnotes and References

Problem page: https://projecteuler.net/problem=628
Permutation matrix: Wikipedia - Permutation matrix
Lattice path: Wikipedia - Lattice path
Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
Factorial: Wikipedia - Factorial

Problem 628 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

using i64 = long long;

static constexpr int MOD = 1'008'691'207;

static inline int mod_norm(i64 x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return (int)x;
}

static int f_formula(i64 n) {
    if (n <= 2) return 0;

    // f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)*sum_{k=0}^{n-4} k! (mod MOD).
    i64 fact = 1;
    i64 sum_fact = (n >= 4 ? 1 : 0);  // 0!

    const i64 upto = n - 4;
    for (i64 i = 1; i <= upto; ++i) {
        fact = (fact * i) % MOD;
        sum_fact += fact;
        if (sum_fact >= MOD) sum_fact -= MOD;
    }

    i64 fn3 = (n == 3 ? 1 : 0), fn2 = 0, fn1 = 0, fn = 0;
    for (i64 i = std::max<i64>(1, upto + 1); i <= n; ++i) {
        fact = (fact * i) % MOD;
        if (i == n - 3) fn3 = fact;
        if (i == n - 2) fn2 = fact;
        if (i == n - 1) fn1 = fact;
        if (i == n) fn = fact;
    }

    i64 res = fn;
    res = (res - 2 * fn1) % MOD;
    res = (res - fn2) % MOD;
    res = (res - fn3) % MOD;
    res = (res + 2) % MOD;
    res = (res + ((n - 3) % MOD) * sum_fact) % MOD;
    return mod_norm(res);
}

static bool is_open(const std::vector<int> &p) {
    const int n = (int)p.size();
    std::vector<std::vector<char>> blocked(n, std::vector<char>(n, 0));
    for (int r = 0; r < n; ++r) blocked[r][p[r]] = 1;
    if (blocked[0][0] || blocked[n - 1][n - 1]) return false;

    std::vector<std::vector<char>> dp(n, std::vector<char>(n, 0));
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            if (blocked[r][c]) continue;
            if (r == 0 && c == 0) {
                dp[r][c] = 1;
            } else {
                dp[r][c] = (char)((r > 0 && dp[r - 1][c]) || (c > 0 && dp[r][c - 1]));
            }
        }
    }
    return dp[n - 1][n - 1];
}

static i64 brute_count(int n) {
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    i64 cnt = 0;
    do {
        if (is_open(p)) ++cnt;
    } while (std::next_permutation(p.begin(), p.end()));
    return cnt;
}

int main() {
    assert(f_formula(3) == 2);
    assert(f_formula(5) == 70);
    for (int n = 3; n <= 9; ++n) assert((i64)f_formula(n) == brute_count(n));

    std::cout << f_formula(100'000'000) << "\n";
    return 0;
}

Python

MOD = 1008691207

def f_formula(n):
    if n <= 2: return 0
    fact = 1
    sum_fact = 1 if n >= 4 else 0
    
    upto = n - 4
    for i in range(1, upto + 1):
        fact = (fact * i) % MOD
        sum_fact = (sum_fact + fact) % MOD
        
    fn3 = 1 if n == 3 else 0
    fn2 = 0
    fn1 = 0
    fn = 0
    
    start = max(1, upto + 1)
    for i in range(start, n + 1):
        fact = (fact * i) % MOD
        if i == n - 3: fn3 = fact
        if i == n - 2: fn2 = fact
        if i == n - 1: fn1 = fact
        if i == n: fn = fact
        
    res = fn
    res = (res - 2 * fn1) % MOD
    res = (res - fn2) % MOD
    res = (res - fn3) % MOD
    res = (res + 2) % MOD
    res = (res + (n - 3) * sum_fact) % MOD
    
    if res < 0: res += MOD
    
    return res

def solve():
    return str(f_formula(100000000))

if __name__ == '__main__':
    print(solve())

Java

public class Euler628 {
    static final long MOD = 1008691207L;

    static long fFormula(long n) {
        if (n <= 2)
            return 0;
        long fact = 1;
        long sumFact = (n >= 4) ? 1 : 0;

        long upto = n - 4;
        for (long i = 1; i <= upto; i++) {
            fact = (fact * i) % MOD;
            sumFact = (sumFact + fact) % MOD;
        }

        long fn3 = (n == 3) ? 1 : 0, fn2 = 0, fn1 = 0, fn = 0;
        long start = Math.max(1L, upto + 1);
        for (long i = start; i <= n; i++) {
            fact = (fact * i) % MOD;
            if (i == n - 3)
                fn3 = fact;
            if (i == n - 2)
                fn2 = fact;
            if (i == n - 1)
                fn1 = fact;
            if (i == n)
                fn = fact;
        }

        long res = fn;
        res = (res - 2 * fn1) % MOD;
        res = (res - fn2) % MOD;
        res = (res - fn3) % MOD;
        res = (res + 2) % MOD;
        res = (res + (n - 3) % MOD * sumFact) % MOD;

        if (res < 0)
            res += MOD;
        return res;
    }

    public static String solve() {
        return Long.toString(fFormula(100000000));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}