A simple proof that the $(n^2-1)$-puzzle is hard
A simple proof that the $(n^2-1)$-puzzle is hard
复制标题
$(n^2-1)$-难题很难的简单证明
DOI：
10.1016/j.tcs.2018.04.031
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Mikhail Rudoy
中科院分区：
文献类型：
--
作者：
E. Demaine;Mikhail Rudoy
15个拼图是一个经典的重构拼图，在一个4×4的棋盘中有15个唯一标记的单元方块，目标是将这些方块(永远不重叠)滑动到目标配置中。通过将其推广到具有n 2−1正方形的n×n板上，我们可以研究与之相关的问题的计算复杂性；特别地，我们考虑了确定从给定的起始构形到给定的终点构形是否可以通过至多给定的移动次数到达给定的终点构形的问题。这个问题在文献[1]中被证明是NP完全的。我们从直线Steiner树问题出发，给出了这一事实的另一种更简单的证明。
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 2− 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.