Ribbon tilings and multidimensional height functions

We fix and say a square in the two-dimensional grid indexed by has color if . A ribbon tile of order is a connected polyomino containing exactly one square of each color. We show that the set of order- ribbon tilings of a simply connected region is in one-to-one correspondence with a set of height functions from the vertices of to satisfying certain difference restrictions. It is also in one-to-one correspondence with the set of acyclic orientations of a certain partially oriented graph.

Using these facts, we describe a linear (in the area of ) algorithm for determining whether can be tiled with ribbon tiles of order and producing such a tiling when one exists. We also resolve a conjecture of Pak by showing that any pair of order- ribbon tilings of can be connected by a sequence of local replacement moves. Some of our results are generalizations of known results for order- ribbon tilings (a.k.a. domino tilings). We also discuss applications of multidimensional height functions to a broader class of polyomino tiling problems.