Abstract

"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. © 1999 Elsevier Science B.V. All rights reserved."