Tiling allowing rotations only

Eric Goles, Ivan Rapaport

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We define a "rotating board" as a finite square with one tile fixed in each cell. These fixed tiles can only be rotated and, in addition, they belong to a particular set of four tiles constructed with two colors. In this paper we show that any set of tiles script T sign may be coded in linear time into a "rotating board" B in the following sense: i. There exists an injection from the colors of the tiles of script T sign into the set of border conditions of the board B. ii. There is a one-to-one relation between the set script T sign and the set of tilings of B (obtained by rotating its tiles) satisfying that each t ∈ script T sign is associated to a tiling Bθ in such a way that the (north, south, east and west) colors of t are related to the (north, south, east and west) border conditions of Bθ by the injection of i. The existence of this coding means that we can efficiently transform an arbitrary degrees of freedom tiling problem (in which to each cell is assigned an arbitrary set of admissible tiles) into a restricted four degrees of freedom problem (in which the tiles, fixed in each cell, can only be rotated). Considering the classical tiling results, we conclude the NP-completeness (resp. undecidability) of the natural bounded (resp. unbounded) version of the rotation tiling problem.

Original languageEnglish
Pages (from-to)285-295
Number of pages11
JournalTheoretical Computer Science
Issue number2
StatePublished - 26 May 1999
Externally publishedYes


Dive into the research topics of 'Tiling allowing rotations only'. Together they form a unique fingerprint.

Cite this