# reference for a edge-matching problem

Perhaps not surprisingly, a variation of a recreational math puzzle (a so-called edge-matching puzzle or scramble square) is equivalent to a combinatorics question of interest (in this case, about quantum knot mosaics, question #9). In a traditional edge-matching puzzle, you are given $n^2$ tiles, each tile square in shape and bearing a design, with the goal of arranging the tiles in an $n\times n$ grid so that the designs on the side of adjacent tiles "match". For instance, here's a puzzle with 24 possible tiles (4 sides, 3 colors, 2 halves) of which at most 9 actually appear (link here if the image is broken):

For what it's worth, solving a general edge-matching puzzle is NP-complete (see article of Demaine). The combinatorics problem is phrased in a slightly different fashion. You begin with a finite collection of designs (such as quadruples of colored halves of butterflies) and for each design an ample supply of square tiles bearing that design. The problem is to calculate the number of arrangements of these tiles in an $n\times n$ grid so that, as in the game described above, the designs on sides of adjacent tiles match. The number of arrangements should be in terms of the size of the grid and the collection of designs on the tiles.

Is anyone aware of results along these lines or, even better, able to provide a quick calculation of the number of arrangements of tiles into an edge-matched grid?

My suspicion is that the number of arrangements goes like $\lambda^{n^2}$ where $\lambda$ is determined from the collection of designs on the tiles.

-

In many systems, there is a constant entropy per area, and the constant is not easy to compute. See, for example, the hard square constant.

If you specify boundary conditions, you can express some interesting combinatorial problems this way. For example, alternating sign matrices correspond to square ice configurations with specified boundary configurations. I don't recall the asymptotics of the number of alternating sign matrices, $\prod \frac{(3k-2)!}{(n-1+k)!}$, but I think there is a positive entropy per area and it shouldn't be too hard to calculate it from the exact formula. It should be lower than the entropy in the square ice model with no boundary conditions, computed by Lieb, since there is an Arctic region.

It is possible to have a number of tilings in a $d$-dimensional cube which grows like $\lambda ^{n^{d-1}}$, and not just by forcing the tiling to be essentially constant in one direction. For example, one collection of tiles means every tiling corresponds to an order ideal: a partition for $d=2$, a plane partition for $d=3$, etc.

-
These references look very useful---many thanks. Now that you mention it, this puzzle does look like a slight generalization of an alternating sign matrix. I'll definitely try to see if Zeilberger's or Kuperberg's proofs of the alternating sign matrix conjecture generalize. –  Russell May Feb 22 '11 at 18:03
By the way, it's not hard to come up with partial configurations for the knot tiles so that you have a binary choice for completing each $3 \times 3$ area, so you have a positive entropy per area and the number of tilings will grow like $\lambda^{n^2}$. –  Douglas Zare Feb 22 '11 at 21:12