Take the 2-minute tour ×  The domino shuffling algorithm first
appeared in the following paper by Propp and Kuperberg:
Alternating-sign matrices and domino tilings  They used this
algorithm to give a fourth proof that the number of domino
tilings of the $n$th aztec diamond is $2^{\frac{n(n+1)}{2}}$.
Now the domino shuffling has been a powerful tool in the
combinatorics of domino tilings. The algorithm is quite simple,
but its correctness is very subtle to illustrate.  Consider the
infinite chessboard on the lattice $\mathbb{Z}^2$, color the
cells black or white such that adjacent cells get different
colors. Then any $1\times2$ domino (if placed on the chessboard)
will cover exactly one white cell and one black cell.  Now
suppose some dominos (the number of the dominos may be infinite)
are placed on the chessboard with out overlapping with each
other, they cover the whole chessboard partially, so we call it
a partial tiling $T$.  A $2\times2$ square is called odd block
with respect to $T$ (following Propp's