A simple proof that the $(n^2-1)$-puzzle is hard

Erik D. Demaine; Mikhail Rudoy

doi:10.1016/j.tcs.2018.04.031

paper

A simple proof that the $(n^{2} - 1)$ -puzzle is hard

arXiv:1707.03146 · doi:10.1016/j.tcs.2018.04.031

Abstract

The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely labeled unit squares within a $4 \times 4$ board in which the goal is to slide the squares (without ever overlapping) into a target configuration. By generalizing the puzzle to an $n \times n$ board with $n^{2} - 1$ squares, we can study the computational complexity of problems related to the puzzle; in particular, we consider the problem of determining whether a given end configuration can be reached from a given start configuration via at most a given number of moves. This problem was shown NP-complete in Ratner and Warmuth (1990). We provide an alternative simpler proof of this fact by reduction from the rectilinear Steiner tree problem.

6 pages, 3 figures

A simple proof that the (n2−1)-puzzle is hard

Abstract

Cited by in corpus (4)

A simple proof that the $(n^{2} - 1)$ -puzzle is hard