Solution of the 15 puzzle problem

MaRDI QIDQ6323903zbMATH OpenFDO

Authors Yang Chu, Robert D. Hough

Publication date 19 August 2019

Abstract: A generalized `$15$ puzzle' consists of an $nimesn$ 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)oinfty$ with $n$, the number of fixed points after $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}logn$ for the total variation mixing time.

This page was built for publication: Solution of the 15 puzzle problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323903)