A simple proof that the (n2 − 1)-puzzle is hard
© 2018 Elsevier B.V. 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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134978 |
| _version_ | 1826213983003082752 |
|---|---|
| author | Demaine, Erik D Rudoy, Mikhail |
| author_facet | Demaine, Erik D Rudoy, Mikhail |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | © 2018 Elsevier B.V. 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. |
| first_indexed | 2024-09-23T15:57:56Z |
| format | Article |
| id | mit-1721.1/134978 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:57:56Z |
| publishDate | 2021 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1349782021-10-28T03:15:39Z A simple proof that the (n2 − 1)-puzzle is hard Demaine, Erik D Rudoy, Mikhail © 2018 Elsevier B.V. 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. 2021-10-27T20:10:09Z 2021-10-27T20:10:09Z 2018 2019-06-11T12:47:16Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134978 en 10.1016/J.TCS.2018.04.031 Theoretical Computer Science Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Demaine, Erik D Rudoy, Mikhail A simple proof that the (n2 − 1)-puzzle is hard |
| title | A simple proof that the (n2 − 1)-puzzle is hard |
| title_full | A simple proof that the (n2 − 1)-puzzle is hard |
| title_fullStr | A simple proof that the (n2 − 1)-puzzle is hard |
| title_full_unstemmed | A simple proof that the (n2 − 1)-puzzle is hard |
| title_short | A simple proof that the (n2 − 1)-puzzle is hard |
| title_sort | simple proof that the n2 1 puzzle is hard |
| url | https://hdl.handle.net/1721.1/134978 |
| work_keys_str_mv | AT demaineerikd asimpleproofthatthen21puzzleishard AT rudoymikhail asimpleproofthatthen21puzzleishard AT demaineerikd simpleproofthatthen21puzzleishard AT rudoymikhail simpleproofthatthen21puzzleishard |