Paper by Erik D. Demaine

Erik D. Demaine and Mikhail Rudoy, “A simple proof that the (n2 − 1)-puzzle is hard”, Theoretical Computer Science, volume 732, July 2018, pages 80–84.

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 n2 − 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.

This paper is also available from ScienceDirect.

The paper is available in PDF (358k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated April 22, 2019 by Erik Demaine.