Detailed mathematical approach

Problem Summary

The rooms of an \(N\times N\) board are labeled in row-major order by \(1,2,\dots,N^2\). The special rooms are those with square labels, namely

$Q=\left\{1^2,2^2,\dots,N^2\right\}.$

A robot performs a random walk on this board under two different rules. The required value is the arithmetic mean of the long-run probability of being in a room from \(Q\) under rule A and under rule B. The key observation used by the implementations is that both rules define reversible Markov chains on the same grid graph, so the stationary distribution depends only on the degree of each room.

Mathematical Approach

View the board as an undirected graph. Each room is a vertex, and edges connect orthogonally adjacent rooms. Let \(d(v)\) be the number of neighbors of room \(v\). On a square grid, every room has degree \(2\), \(3\), or \(4\) depending on whether it is a corner, an edge room, or an interior room.

Step 1: Classify the Grid by Degree

There are exactly \(4\) corners, \(4(N-2)\) non-corner edge rooms, and \((N-2)^2\) interior rooms. Therefore

$\sum_{v} d(v)=2\cdot 4+3\cdot 4(N-2)+4(N-2)^2=4N(N-1).$

This is the denominator that appears in the second random rule. For the first rule we will also need

$\sum_{v}\bigl(d(v)+1\bigr)=\sum_{v} d(v)+N^2=5N^2-4N=N(5N-4).$

The extra \(+1\) comes from the option to stay in the same room.

Step 2: Stationary Distribution for Rule A

Under rule A, from a room \(v\) the robot chooses uniformly among all legal options: stay put, or move to one of the \(d(v)\) neighbors. Thus

$P_A(v\to v)=\frac{1}{d(v)+1},\qquad P_A(v\to u)=\frac{1}{d(v)+1}\quad\text{when }u\sim v.$

This is a reversible walk. For any adjacent rooms \(u\) and \(v\),

$\bigl(d(v)+1\bigr)P_A(v\to u)=1=\bigl(d(u)+1\bigr)P_A(u\to v).$

So detailed balance holds with weights proportional to \(d(v)+1\). After normalization, the stationary probability of room \(v\) is

$\pi_A(v)=\frac{d(v)+1}{\sum_w \bigl(d(w)+1\bigr)}.$

Step 3: Stationary Distribution for Rule B

Under rule B, the robot stays with probability \(1/2\), and the remaining \(1/2\) is shared equally among the \(d(v)\) neighbors:

$P_B(v\to v)=\frac12,\qquad P_B(v\to u)=\frac{1}{2d(v)}\quad\text{when }u\sim v.$

This chain is also reversible. For adjacent rooms \(u\) and \(v\),

$d(v)\,P_B(v\to u)=\frac12=d(u)\,P_B(u\to v).$

Hence the stationary distribution is proportional to \(d(v)\):

$\pi_B(v)=\frac{d(v)}{\sum_w d(w)}.$

So rule A weights a room by \(d(v)+1\), while rule B weights it by \(d(v)\).

Step 4: Locate the Square-Numbered Rooms

Because the board is labeled from \(1\) to \(N^2\), the square labels are exactly \(k^2\) for \(1\le k\le N\). The room with label \(k^2\) has coordinates

$r_k=\left\lfloor\frac{k^2-1}{N}\right\rfloor+1,\qquad c_k=\bigl((k^2-1)\bmod N\bigr)+1.$

Its degree is determined only by whether these coordinates lie on the boundary:

$d_k= \begin{cases} 2,&\text{if }(r_k,c_k)\text{ is a corner},\\ 3,&\text{if }(r_k,c_k)\text{ is an edge but not a corner},\\ 4,&\text{if }(r_k,c_k)\text{ is interior}. \end{cases}$

Let

$S=\sum_{k=1}^{N} d_k.$

Then the total rule-A weight of all square-numbered rooms is \(S+N\), because each of the \(N\) target rooms contributes one extra self-loop unit.

Step 5: Sum the Target Probabilities

From the stationary distributions, the total long-run probability of landing in a square-numbered room is

$P_A(Q)=\sum_{k=1}^{N}\pi_A(k^2)=\frac{S+N}{5N^2-4N},$

and for rule B it is

$P_B(Q)=\sum_{k=1}^{N}\pi_B(k^2)=\frac{S}{4N^2-4N}.$

The problem asks for their arithmetic mean, so the final quantity is

$\boxed{P(Q)=\frac12\left(\frac{S+N}{5N^2-4N}+\frac{S}{4N^2-4N}\right).}$

Once \(S\) is known, the whole problem is solved.

Step 6: Why Only One Pass Over \(k\) Is Needed

The global denominators \(5N^2-4N\) and \(4N^2-4N\) are closed forms, so no simulation is required. The only nontrivial computation is to inspect each square label \(k^2\), map it to its row and column, decide whether it is a corner, edge, or interior room, and add \(2\), \(3\), or \(4\) to \(S\). That is exactly what the implementations do.

Worked Example: \(N=5\)

The square labels are \(1,4,9,16,25\). Their coordinates are

$1\mapsto(1,1),\qquad 4\mapsto(1,4),\qquad 9\mapsto(2,4),\qquad 16\mapsto(4,1),\qquad 25\mapsto(5,5).$

So their degrees are \(2,3,4,3,2\), giving

$S=2+3+4+3+2=14,\qquad S+N=19.$

For the whole grid,

$\sum_v d(v)=4\cdot 5\cdot 4=80,\qquad \sum_v\bigl(d(v)+1\bigr)=5\cdot 25-20=105.$

Therefore

$P_A(Q)=\frac{19}{105},\qquad P_B(Q)=\frac{14}{80}=\frac{7}{40},$

and the required average is

$P(Q)=\frac12\left(\frac{19}{105}+\frac{7}{40}\right)=\frac{299}{1680}=0.177976190476\ldots$

This matches the validation value used by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same plan. First they compute the closed-form totals for the whole \(N\times N\) grid: the number of corners, edge rooms, and interior rooms, then the two denominator sums needed for the stationary distributions. Next they loop through \(k=1,2,\dots,N\), form the square label \(k^2\), convert that label to a row and column, and test whether the room lies on the top, bottom, left, or right boundary. From those boundary tests the implementation assigns degree \(2\), \(3\), or \(4\), adds it to the running square-room total, and also adds one more unit for rule A.

After this single pass, the program has exactly the two numerators required for the formulas above. It divides by the two global denominators, averages the two probabilities, and prints the result to twelve decimal places. No matrix exponentiation, simulation, or iterative convergence is needed because the stationary measure is obtained directly from detailed balance.

Complexity Analysis

All whole-board quantities are computed in constant time from closed formulas. The only loop runs once for each square label \(k^2\) with \(1\le k\le N\), and each iteration performs only a few integer operations and boundary comparisons. Therefore the time complexity is \(O(N)\) and the extra space usage is \(O(1)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=575
2. Detailed balance: Wikipedia - Detailed balance
3. Stationary distribution: Wikipedia - Stationary distribution
4. Random walk on a graph: Wikipedia - Random walk on a graph
5. Markov chain: Wikipedia - Markov chain