Paper by Erik D. Demaine

Reference:

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

BibTeX

@Article{FifteenPuzzle_TCS,
  AUTHOR        = {Erik D. Demaine and Mikhail Rudoy},
  TITLE         = {A simple proof that the $(n^2-1)$-puzzle is hard},
  JOURNAL       = {Theoretical Computer Science},
  journalurl    = {https://www.journals.elsevier.com/theoretical-computer-science},
  VOLUME        = 732,
  PAGES         = {80--84},
  MONTH         = {July},
  YEAR          = 2018,

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1016/J.TCS.2018.04.031},
  dblp          = {https://dblp.org/rec/journals/tcs/DemaineR18},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.tcs.2018.04.031">ScienceDirect</A> and as <A HREF="https://arxiv.org/abs/1707.03146">arXiv:1707.03146</A>.},
}

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² − 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]