文章基本信息

标题：Rolling Block Mazes are PSPACE-complete
本地全文：下载
作者：Kevin Buchin ; Maike Buchin
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2012
卷号：7
期号：3
页码：1025-1028
DOI：10.11185/imt.7.1025
出版社：Information and Media Technologies Editorial Board
摘要：In a rolling block maze, one or more blocks lie on a rectangular board with square cells. In most mazes, the blocks have size k × m × n where k , m , n are integers that determine the size of the block in terms of units of the size of the board cells. The task of a rolling block maze is to roll a particular block from a starting to an ending placement. A block is rolled by tipping it over one of its edges. Some of the squares of the board are marked as forbidden to roll on. We show that solving rolling block mazes is PSPACE-complete.
关键词：constraint logic;puzzle;rolling block maze