*** Welcome to piglix ***

Domino tiling


In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

For some classes of tilings on a regular grid in two dimensions, it is possible to define a height function associating an integer to the vertices of the grid. For instance, draw a chessboard, fix a node with height 0, then for any node there is a path from to it. On this path define the height of each node (i.e. corners of the squares) to be the height of the previous node plus one if the square on the right of the path from to is black, and minus one otherwise.


...
Wikipedia

...