Tiling allowing rotations only

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 pape r we show that any set of tiles T may be coded in linear time into a "rotat ing board" B in the following sense: i. There exists an injection from the colors of the tiles of T into the set of border conditions of the board B. ii. There is a one-to-one relation between the set T and the set of tilings of B (obtained by rotating its tiles) satisfying that each t is an element of T is associated to a tiling B-theta in such a way that the (north, sout h, east and west) colors of t are related to the (north, south, east and we st) border conditions of B-theta by the injection of i. The existence of this coding means that we can efficiently transform an arb itrary degrees of freedom tiling problem (in which to each cell is assigned an arbitrary set of admissible tiles) into a restricted four degrees of fr eedom 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. (C) 1999 Elsevier Science B.V. All rights res erved.