Filling an $n\times n$ board
Solution 1:
This is not an answer but a note how to compute the number of ways $\mathcal{N}_n$ for $n = 5$.
We can split the $5\times 5$ board into $8$ right angled triangles. Let us label the states in one of the triangle as follows:
$$\begin{array}{|ccccc|} \hline * & * & * & * & e\\ * & * & * & c & d\\ * & * & 0 & a & b\\ * & * & * & * & *\\ * & * & * & * & *\\ \hline \end{array}$$
It is easy to check given the constraint, there are
- 5 possibilities for $\verb/ab/$ - $00, 01, 10, 11, 12$.
- 12 possibilities for $\verb/ce/$ - $00, 01, 02, 10, 11, 12, 13, 20, 21, 22, 23, 24$.
Given any legal combination of $a, b, c, e$, the number of possibilities for $d$ can be counted by brute force. The result is summarized by following table. $$\begin{array}{r|lllll} & & & \verb/ab/ & & \\ \verb/ce/ & 00 & 01 & 10 & 11 & 12\\ \hline 00 & 2 & 2 & 2 & 2 & 1\\ 01 & 2 & 2 & 2 & 2 & 1\\ 02 & 1 & 1 & 1 & 1 & 1\\ 10 & 2 & 2 & 2 & 2 & 1\\ 11 & 2 & 3 & 2 & 3 & 2\\ 12 & 1 & 2 & 1 & 2 & 2\\ 13 & 0 & 1 & 0 & 1 & 1\\ 20 & 0 & 0 & 1 & 1 & 1\\ 21 & 0 & 0 & 1 & 2 & 2\\ 22 & 0 & 0 & 1 & 2 & 3\\ 23 & 0 & 0 & 0 & 1 & 2\\ 24 & 0 & 0 & 0 & 0 & 1\\ \end{array}$$
For the other 7 triangles, it is clear each of them have a similar set of possibilities. If we pick 8 admissible configurations, one for each of the 8 triangles and glue them together. We can construct a legal configuration for the whole board provided the configurations of the triangles match at their boundaries.
A consequence of this is if we define $M_5$ as the $12\times 5$ matrices with entries in above table, the total number of ways for $n = 5$ can be evaluated as a trace!
$$\mathcal{N}_5 = \text{Tr} \left( (M_5^T M_5 )^4 \right) = 178383613 $$
As a double check, for the easier case $n = 3$, the corresponding $M_3$ has entries given by the table:
$$\begin{array}{r|rl} & \quad\rlap{\verb/ a/} & \\ \verb/c/ & 0 & 1\\ \hline 0 & 1 & 1\\ 1 & 1 & 1\\ 2 & 0 & 1 \end{array} $$ This leads to $$\mathcal{N}_3 = \text{Tr}\left( \begin{bmatrix}1 & 1 & 0\\1 & 1 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & 1\\0 & 1\end{bmatrix} \right)^4 = \text{Tr}\begin{bmatrix}2 & 2\\ 2 & 3\end{bmatrix}^4 = 433 $$ as expected.
Notes
- This way of counting $\mathcal{N}_n$ is inspired by the general technique Transfer-matrix method for solving problems in statistical mechanics. The key is break the configuration into units similar to each other. Compute the possibilities for individual units and represent them as matrices. Finally, convert the original sum into the trace of product of these matrices.