**Reference**:- Erik D. Demaine and Mikhail Rudoy, “A simple proof that the (
*n*^{2}− 1)-puzzle is hard”,*Theoretical Computer Science*, volume 732, July 2018, pages 80–84. **Abstract**:-
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely
labeled unit squares within a 4 × 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*×*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 [1]. We provide an alternative simpler proof of this fact by reduction from the rectilinear Steiner tree problem. **Comments**:- This paper is also available from ScienceDirect and as arXiv:1707.03146.
**Availability**:- The paper is available in PDF (358k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated January 15, 2021 by Erik Demaine.