Transformations of domino tilings

Given a domino tiling of a rectangle, we can transform it to a new tiling by the following move: pick two dominos that share a long edge, and rotate them in place 90 degrees. Is it possible to change any domino tiling to any other domino tiling by repeating this move?

This is supposedly proved by Bill Thurston in his classic paper Conway's tiling groups.

Here is some more information from O. Bodini, Th. Fernique, E. Rémila, Characterizations of flip-accessibility for domino tilings of the whole plane and S. Desreux, E. Rémila, An optimal algorithm to generate tilings. To follow the explanation, please open the first paper at page 2 and look at Figure 2.

Given a domino tiling, there is a way to assign heights to vertices (right part of Figure 2). Pick your favorite $2\times 2$ rectangle covered by two dominoes. Notice that the heights of all four corners are the same, say $h$, and the point at the center has height $h \pm 2$. Moreover, the point in the center is a local extremum. The move (also called a domino flip) changes the sign: see Figure 1 on page 5 of the second paper.

Apply repeatedly the following algorithm: While the function has a local minimum, flip it into a local maximum. The algorithm increases heights of points, so must converge. Moreover, it is not hard to show that there is a unique local maximum: the corresponding heights can be determined explicitly subject to the constraints. The corresponding tiling appears in Thurston's paper, Figures 4.4 and 4.5 on pages 14 and 15 (769 and 770), respectively.

Since any tiling can be flipped into this tiling of maximal height, flips can transform any given tiling to any other given tiling.

Eric Rémila explains everything in his paper The lattice structure of the set of domino tilings of a polygon. He shows that there is a unique maximal tiling by proving that the pointwise maximum of two height functions is also a height function; he does that by showing that every edge comes from one of the tilings.

He also provides an optimal algorithm to flip from one tiling to another. This algorithm goes through the pointwise maximum of the height functions of both tilings, and changes each vertex in only one direction. Therefore the number of flips needed is exactly one fourth of the total height difference $(L_1$ distance$)$, a formula he attributes to an earlier 1995 paper, Spaces of domino tilings.

The latter paper, by Saldanha, Tomei, Casarin and Romualdo, may be the first to which proves this result. Still, usually the result is attributed to (Bill) Thurston's paper.

A generalization of this result appears in Dylan Thurston's paper "From dominoes to hexagons".