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>.},
  updates       = {The stated open problem (minimum number of moves requires to solve an (<i>n</i><sup>2</sup> &minus; 1)-puzzle) is not open. The <a href="https://ianparberry.com/pubs/saml.pdf">cited 1995 paper by Parberry [12]</a> gives a lower bound of <i>n</i><sup>3</sup> and an upper bound of 5&thinsp;<i>n</i><sup>3</sup>. A <a href="https://doi.org/10.1007/978-3-031-39344-0_10">more recent paper by Zhong (2023)</a> proves a nearly matching upper bound of <i>n</i><sup>3</sup> + <i>O</i>(<i>n</i><sup>2.75</sup>).},
}

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.

Updates:

The stated open problem (minimum number of moves requires to solve an (n² − 1)-puzzle) is not open. The cited 1995 paper by Parberry [12] gives a lower bound of n³ and an upper bound of 5 n³. A more recent paper by Zhong (2023) proves a nearly matching upper bound of n³ + O(n^2.75).

Availability:

The paper is available in PDF (358k).

See information on file formats.

[Google Scholar search]