Number of moves necessary to solve a generalized fifteen-puzzle with random moves Consider the famous fifteen-puzzle, but with size $m\times n$ ; $m,n\in \mathbb N$; $m,n>1$
Suppose, the initial position of the puzzle is random but solveable. Random moves
are made until the puzzle is solved.
Let $X$ be the number of moves.


*

*What is $E(X)$ and $Var(X)$ , depending on $m$ and $n$ ?

 A: This would take a long, long time.
The $15$-puzzle has even-odd parity, so of its $15! = 1307674368000$ configurations (up to a horizontal slide of the empty space), exactly half are unsolvable, leaving $15!/2 = 653837184000$ valid configurations.  Since the graph is large and symmetric, and we do not bar return visits, my guess (assuming that we are counting single-tile moves) is that $X$ is roughly geometrically (exponentially) distributed with mean $E(X) \doteq 15!/2$, and then the variance would be $Var(X) \doteq (15!/2)^2$.
This compares with a bounded solution length of $80$ (single-tile) moves.
More generally, if there are $mn-1$ tiles, then the number of valid configurations would be $(mn-1)!/2$, and the mean and variance of $X$ would be about $(mn-1)!/2$ and $[(mn-1)!/2]^2$, respectively.
ETA: The upper bound on solution lengths is not known for general $m, n$; in fact, it is not even known for the $5\times5$ puzzle.  Based on current estimates, it looks like it's roughly proportional to the three-halves power of the number of tiles, but that's just a WAG.
