Solution of the 15 puzzle problem

A generalized $15$ puzzle' consists of an $n \times n$ numbered grid, with one missing number. A move in the game switches the position of the empty square with the position of one of its neighbors. We solve Diaconis' 15 puzzle problem’ by proving that the asymptotic total variation mixing time of the board is at least order $n^4$ when the board is given periodic boundary conditions and when random moves are made. We demonstrate that for any $f(n) \to \infty$with$n$,thenumberoffixedpointsafter$n^4 f(n)$ moves converges to a Poisson distribution of parameter 1. The order of total variation mixing time for this convergence is $n^4$ without cut-off. We also prove an upper bound of order $n^4\log n$ for the total variation mixing time.