论文标题
葫芦：带有转动的滑动拼图
Gourds: a sliding-block puzzle with turning
论文作者
论文摘要
我们提出了一种新型的滑动拼图，称为Gourds，其目的是在2n + 1个单元格的六角形网格板上重新排列1 x 2件，并使用滑动，转动和旋转移动。这个难题在板上有一个空牢房，并形成了15个插头的自然扩展，以包括旋转移动。我们分析了难题，并完全表征始终解决难题的情况。我们还研究了确定是否可以将一组有色碎片放在带有匹配颜色的彩色六角形网格板上的复杂性。我们显示，对于任意多种颜色而言，这个问题是NP完整的，但是如果颜色的数量为固定常数，则可以在随机多项式时间内解决。
We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1 x 2 pieces on a hexagonal grid board of 2n + 1 cells with n pieces, using sliding, turning and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant.
