  The problem of counting tilings of a plane region using specified tiles can
often be recast as the problem of counting (perfect) matchings of some subgraph
of an Aztec diamond graph A_n, or more generally calculating the sum of the
weights of all the matchings, where the weight of a matching is equal to the
product of the (pre-assigned) weights of the constituent edges (assumed to be
non-negative). This article presents efficient algorithms that work in this
context to solve three problems: finding the sum of the weights of the
matchings of a weighted Aztec diamond graph A_n; computing the probability that
a randomly-chosen matching of A_n will include a particular edge (where the
probability of a matching is proportional to its weight); and generating a
matching of A_n at random. The first of these algorithms is equivalent to a
special case of Mihai Ciucu's cellular complementation algorithm and can be
used to solve many of the same problems. The second of the three algorithms is
a generalization of not-yet-published work of Alexandru Ionescu, and can be
employed to prove an identity governing a three-variable generating function
whose coefficients are all the edge-inclusion probabilities; this formula has
been used as the basis for asymptotic formulas for these probabilities, but a
proof of the generating function identity has not hitherto been published. The
third of the three algorithms is a generalization of the domino-shuffling
algorithm described by Elkies, Kuperberg, Larsen and Propp; it enables one to
generate random ``diabolo-tilings of fortresses'' and thereby to make
intriguing inferences about their asymptotic behavior.

Combinatorics