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: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2022
|
| Online Access: | https://hdl.handle.net/1721.1/134978.2 |
| Summary: | © 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. |
|---|