Journal
THEORETICAL COMPUTER SCIENCE
Volume 732, Issue -, Pages 80-84Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.04.031
Keywords
(n(2)-1)-puzzle; Complexity of games; NP-hardness; Rectilinear Steiner tree
Categories
Ask authors/readers for more resources
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely labeled unit squares within a 4 x 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 x 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. (C) 2018 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available