Abstract

In this paper we introduce tile rotation problems. The instances (or initial configurations) are tile assignments on a (n x n) lattice board, and the question to be answered is the following: does there exist any configuration obtained from the initial one by tile rotations only whose cost is less than a given bound? (notice that a zero-cost configuration corresponds to a perfect tiling). We prove here the NP-completeness for both the zero-cost problem (for a particular set of 5 tiles) and the minimization problem (for a particular set of 2 tiles). Finally, by showing the polynomiality of some subproblems, we establish complexity border results.