Open Chess Positions

A position in chess is an (orientated) arrangement of chess pieces placed on a chessboard of given size. In the following, we consider all positions in which $n$ pawns are placed on a $n \times n$
board in such a way, that there is a single pawn in every row and every column.

We call such a position an open position, if a rook, starting at the (empty) lower left corner and using only moves towards the right or upwards, can reach the upper right corner without moving onto any field occupied by a pawn.

Let $f(n)$ be the number of open positions for a $n \times n$ chessboard.
For example, $f(3)=2$, illustrated by the two open positions for a $3 \times 3$ chessboard below.

You are also given $f(5)=70$.
Find $f(10^8)$ modulo $1\,008\,691\,207$.

This problem can be solved by using dynamic programming concepts and combinatorics.

The dp[i][j] holds the number of valid positions on an i by j chessboard such that a rook can move from the bottom left to top right. For a fixed i, as j increases, every dp[i][j] is the sum of the previous dp[i][k] times a combinatorics term, P(j, k).

The combinatorics term P(j, k) is the number of ways to pick and order k items from an available j items. In our context, this would show how many ways we can choose k slots in the j columns for the chessboard to place the pawns such that a rook can move from the lower left to the upper right.

Now, if we compute the prefix sum, prefix[j] = Σ(k=0 to j) dp[i][k] * P(j, k), we can derive dp[i+1][j] from prefix[j].

Therefore, we have dp[i+1][j] = dp[i][j] + prefix[j-1] – dp[i][j-1] * P(j, j-1). The first two terms in the equation come directly from the prefix sum. The last term gets subtracted because, in the prefix sum, we double count scenarios when there is a pawn in the (j-1)th and jth columns because our rook can’t pass through.

By iterating through every j from 1 to n, we can compute every dp[i][j] and compute the prefix sums simultaneously. In terms of implementation, we only need to keep track of 2 rows at a time (the previous dp[i] row and the current dp[i+1] row). This saves space as the board size n gets larger.

Finally, at dp[n][n], if we multiply by n!, the number of ways to assign each pawn to each row such that one pawn is in every row, we have the number of open positions, f(n).

We aren’t done yet, because we cannot compute the entire dp table for a board size of 10^8 because of memory constraints. So instead, we look at the problem differently.

Notice the product to calculate f(n) from dp[n][n] has a degree of n. Taking f(n) modulo m for large n is essentially finding the nth degree term in the power series expansion of f(n). Those terms are determined by differentiating f(n) n times since we only care about the nth degree term.

This leads us to a key insight:
By differentiating the recursive formula for dp[i+1][j] that was previously developed and described, we can write the formula for dp'[i+1][j] in terms of dp'[i][j], dp[i][j], and constants. In other words, the recursive formula to find dp[i+1][j] is linear.

By representing this recursion as a matrix, the nth term can be computed in O(log n) time using matrix exponentiation. The matrix A would look like:

[[0, 1, 2, 3, 4, …, n-1],
[1, 1, 2, 3, 4, …, n-1],
[0, 1, 1, 2, 3, …, n-2],
[0, 0, 1, 1, 2, …, n-3],
…,
[0, 0, 0, 0, 0, …, 1]]

and B would be [[0], [B_2], [B_3], …, [B_n]]

Using fast matrix exponentiation to find the nth power of the matrix, we can calculate f(10^8) modulo 1,008,691,207.

Note: This might exceed the capacities of standard integer types, so you’d likely need to use arbitrary-precision arithmetic (like Python’s built-in arbitrary-precision integers) to carry out the calculations. Also be aware to take modulo m for each step to avoid overflow.

More Answers: