$\left(56^{16}\times2\right)^2 =$ number of possible outcomes, right?
Each row of pawns can be in every place except the first row, so I thought of it as $4$ separate superimposed boards where the first two rows of two of the boards were removed [because pawns can't travel backward] then I multiplied the number of board-spaces to the 16th power because that's the number of states that a given board-square can be in at any given time, then I squared the answer to account for the fact that pieces can go missing overtime [because that's how you play].
These are my first thoughts however, it may also be the sum of $\left(56^8\times2\right)^2$ and/plus $\left(64^8\times2\right)^2$. I'm trying to approach it as an information theory problem (like an integrated circuit) but instead of bits-per-chip I'm trying (and probably failing miserably) to read it as board-square/board-space_states_per_board, it's particularly challenging because half of the pieces [plus horses and bishops (Bishops or, maybe castles? The "diagonal moving dudes")] are restricted to never being able to reach certain spaces, so if we could: subtract those from that piece's version of the board; think of the board as a binary data equation where each valid board-square was considered as being able to be in one of 3 states (yours the enemy's, or empty); add that data to equations that had those piece-states removed from them, and then subtract one from the total [because there will always be one piece left: therefore: meaning that the outcome where all spaces are empty is invalid]
-Hope this helps. I for one: would also like to solve this mystery.
We will prove the general case: In a $ n \times n$ board filled with integers $1$ to $n^2$, then there exist 2 neighboring squares whose difference is at least $n$.
Explanation of main idea: Find $n$ distinct pairs of neighbors where one term is $\leq K$ and the other neighboring term is $\geq K+1$. Then, the smallest of this terms is at most $K-n+1$, and it's neighbour is at least $K+1$, so their difference is at least $n$.
For each row, let $r_i$ be the largest number in that row.
For each column, let $c_i$ be the largest number in that column.
Let $N$ be the smallest of these $2n$ values. WLOG $N=r_I$, and cell $(I,J)$ is equal to $N$. Then, every other integer in this row is $\leq N-1$.
For every column not equal to $J$, we can find adjacent cells where one is $\leq N-1$ (starting with row $I$) and one is $\geq N+1$ (otherwise, this contradicts the minimality of $N$).
In column $J$, either $N$ is adjacent to a number $<N$, or to a number $>N$.
Case 1:$N$ is adjacent to a number $< N$
We now have $n$ distinct pairs of neighbors (since they are in different columns) where one term is $\leq N-1$ and the other is $\geq N$. Let the smallest of the terms be $S$, then $S \leq N-n$. Hence, the difference between $S$ and its neighbor is at least $n$.
Case 2:$N$ is adjacent to a number $> N$.
We now have $n$ distinct pairs of neighbors (since they are in different columns) where one term is $\leq N$ and the other is $\geq N+1$. Let the smallest of the terms be $S$, then $S \leq N-n+1$. Hence, the difference between $S$ and its neighbor is at least $n$.
Best Answer
We have $64$ cells:
The total number of ways to choose $2$ out of $64$ cells is $\binom{64}{2}=2016$.
The number of ways to choose $2$ adjacent cells is $\frac{36\cdot4+24\cdot3+4\cdot2}{2!}=112$.
So the probability of choosing $2$ adjacent cells is $\frac{112}{2016}=\frac{1}{18}$.