Rolling block mazes are PSPACE-complete

K. Buchin, M. Buchin

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

8 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)719-722
TijdschriftJournal of Information Processing
Volume20
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2012

Citeer dit