A generalized @math puzzle' consists of an @math 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 @math when the board is given periodic boundary conditions and when random moves are made. We demonstrate that for any @math with @math , the number of fixed points after @math moves converges to a Poisson distribution of parameter 1. The order of total variation mixing time for this convergence is @math without cut-off. We also prove an upper bound of order @math for the total variation mixing time.
 Following Wilson (J. Comb. Th. (B), 1975), Johnson (J. of Alg., 1983), and Kornhauser, Miller and Spirakis (25th FOCS, 1984), we consider a game that consists of moving distinct pebbles along the edges of an undirected graph. At most one pebble may reside in each vertex at any time, and it is only allowed to move one pebble at a time (which means that the pebble must be moved to a previously empty vertex). We show that the problem of finding the shortest sequence of moves between two given "pebble configuations" is NP-Hard. The 8-puzzle and the 15-puzzle have been used for many years as a domain for testing heuristic search techniques. From experience it is known that these puzzles are "difficult" and therefore useful for testing search techniques. In this paper we give strong evidence that these puzzles are indeed good test problems. We extend the 8-puzzle and the 15-puzzle to a nxn board and show that finding a shortest solution for the extended puzzle is NP-hard and thus computationally infeasible. We also present an approximation algorithm for transforming boards that is guaranteed to use no more than c L (SP) moves, where L (SP) is the length of the shortest solution and c is a constant which is independent of the given boards and their size n.