Aztec diamond

In combinatorial mathematics, an Aztec diamond of order n consists of all squares of a square lattice whose centers (x,y) satisfy |x| + |y| ≤ n. Here n is a fixed integer, and the square lattice consists of unit squares with the origin as a vertex of 4 of them, so that both x and y are half-integers.

[1] The Aztec diamond theorem states that the number of domino tilings of the Aztec diamond of order n is 2n(n+1)/2.

[2] The Arctic Circle theorem says that a random tiling of a large Aztec diamond tends to be frozen outside a certain circle.

[3] It is common to color the tiles in the following fashion.

Each tile will cover exactly one black square.

Vertical tiles where the top square covers a black square, is colored in one color, and the other vertical tiles in a second.

Knuth has also defined Aztec diamonds of order n + 1/2.

[4] They are identical with the polyominoes associated with the centered square numbers.

Something that is very useful for counting tilings is looking at the non-intersecting paths through its corresponding directed graph.

These movements are similar to Schröder paths.

For example, consider an Aztec Diamond of order 2, and after drawing its directed graph we can label its sources and sinks.

On its directed graph, we can draw a path from

The number of tilings for order 2 is det

number of non-intersecting paths from S to T.[5] Considering the directed graph of the Aztec Diamond, it has also been shown by Eu and Fu that Schröder paths and the tilings of the Aztec diamond are in bijection.

[6] Hence, finding the determinant of the path matrix,

, will give us the number of tilings for the Aztec Diamond of order n. Another way to determine the number of tilings of an Aztec Diamond is using Hankel matrices of large and small Schröder numbers,[6] using the method from Lindstrom-Gessel-Viennot again.

[5] Finding the determinant of these matrices gives us the number of non-intersecting paths of small and large Schröder numbers, which is in bijection with the tilings.

for the first entry of the matrix in the top left corner).

block, and we can ask the same question as for the Aztec Diamond of order n. As this has been proven in many papers, we will refer to.

Focusing on how we can begin our tiling, we have two cases.

We can start with our first tile being vertical, which means we are left with

[7] Finding valid tilings of the Aztec diamond involves the solution of the underlying set-covering problem.

be the set of 1X1 squares lying within the diamond that must be covered.

Two dominoes within D can be found to cover any boundary square within S, and four dominoes within D can be found to cover any non-boundary square within S. Define

to be the set of dominoes that cover square

With these definitions, the task of tiling the Aztec diamond may be reduced to a constraint satisfaction problem formulated as a binary integer program:

will be covered by a single tile, and the collection of

This formulation can be solved with standard integer programming packages.

Additional constraints can be constructed to force placement of particular dominoes, ensure a minimum number of horizontal or vertically-oriented dominoes are used, or generate distinct tilings.

An alternative approach is to apply Knuth's Algorithm X to enumerate valid tilings for the problem.