4.3 Article

Computational complexity of jumping block puzzles

期刊

THEORETICAL COMPUTER SCIENCE
卷 983, 期 -, 页码 -

出版社

ELSEVIER
DOI: 10.1016/j.tcs.2023.114292

关键词

Combinatorial reconfiguration; Computational complexity; Jumping block puzzle; Sliding block puzzle; Token jumping

向作者/读者索取更多资源

Sliding block puzzles play a crucial role in computational complexity, with their complexity varying depending on the rules and set of pieces. In this study, we explore the computational complexities of jumping block puzzles, a newer concept in the puzzle community. We analyze different variants of these puzzles based on real puzzles and a natural model, and determine their complexities. Our findings show that these puzzles are generally PSPACE-complete, with additional cases being NP-complete or solvable in polynomial-time.
In the context of computational complexity of puzzles, the sliding block puzzles play an important role. Depending on the rules and set of pieces, the sliding block puzzles can be polynomial-time solvable, NP-complete, or PSPACE-complete. On the other hand, a relatively new notion of jumping block puzzles has been proposed in the puzzle community. This is a counterpart to the token jumping model of the combinatorial reconfiguration problems in the context of block puzzles. We investigate some variants of jumping block puzzles, which are based on actual puzzles, and a natural model from the viewpoint of combinatorial reconfiguration, and determine their computational complexities. More precisely, we investigate two generalizations of two actual puzzles which are called Flip Over puzzles and Flying Block puzzles and one natural model of jumping block puzzles from the viewpoint of combinatorial reconfiguration. We prove that they are PSPACE-complete in general. We also prove the NP-completeness of these puzzles in some restricted cases, and we give polynomial-time algorithms for some restricted cases.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据