Tetris and decidability |
| |
Authors: | Hendrik Jan Hoogeboom Walter A. Kosters |
| |
Affiliation: | Leiden Institute of Advanced Computer Science (LIACS), Universiteit Leiden, The Netherlands |
| |
Abstract: | We consider a variant of Tetris where the sequence of pieces (together with their orientation and horizontal position, which cannot be changed anymore) is generated by a finite state automaton. We show that it is undecidable, given such an automaton, and starting from an empty game board, whether one of the generated sequences leaves an empty game board. This is contrasted with more common situations where piece translations and rotations are allowed. |
| |
Keywords: | Tetris Decidability Theory of computation |
本文献已被 ScienceDirect 等数据库收录! |
|