An optimal algorithm to generate tilings (Q2466003)

The authors study tilings of finite simply connected regions of the square or triangular lattice with dominoes (\(2\times 1\) rectangles) or lozenges (consisting of two equilateral triangles of unit size sharing a whole side), respectively. They describe an algorithm that is optimal with respect to both space and execution time to generate all domino or lozenge tilings of a given region. An essential tool is the height function which associates to each vertex of a tiling an integer in such a way that it encodes the tiling uniquely. The height function is then used to further encode a tiling by a word, and the algorithm produces to each such word the successor with respect to the lexicographical order, starting with the minimal tiling which is constructed by an algorithm due to \textit{W. P. Thurston} [Am. Math. Mon. 97, 757--773 (1990; Zbl 0714.52007)].