6
$\begingroup$

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 knots and mosaics", S.J. Lomonaco, L.H. Kauffman, 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: alt text (source)

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ As an aside, Elchanan Mossel and Nathan Ross have studied the jigsaw problem from a probabilistic perspective - given a set of random tiles using q butterflies for the sides, does the puzzle have a unique solution? arxiv.org/pdf/1504.07682.pdf $\endgroup$
    – Zach H
    Oct 21, 2015 at 16:12

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Russell May
    Feb 22, 2011 at 18:03
  • $\begingroup$ 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}$. $\endgroup$
    – Douglas Zare
    Feb 22, 2011 at 21:12
0
$\begingroup$

There might not be a nice quick and dirty formula because tiles with the same boarder can have different designs on the interior, which when there are two red lines in your paper. You can get pretty quick bounds though.

As in the butterfly example, if you know what the designs are on the boarder you know what the tile is. On the perimeter of your grid you have 4n edges, and 2n(n-1) on the interior. So if you have d butterfly designs, you have d^(2n^2+2n).

If each tile has a maximum multiplicity of m (meaning the same edge designs could mean at most m different designs), then you have at most m^(n^2) * d^(2n^2+2n) total designs. So your hunch was right. Sorry my mathjax syntax wasn't working so I dropped it.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Spelling pedantry: a "boarder" is "one who boards" as in "one who pays a stipulated sum in return for regular meals (often with lodging)" or "one who boards a ship". The line you cross when you go from one country to another is the "border". $\endgroup$
    – JBL
    Feb 22, 2011 at 3:14
  • $\begingroup$ I also am having trouble making sense of some parts of your answer; for example, what is the meaning of "which when there are two red lines in your paper"? $\endgroup$
    – JBL
    Feb 22, 2011 at 3:16
  • 1
    $\begingroup$ The "red lines" come from the referenced paper on quantum knot mosaics by Lomonaco and Kauffman, in which the tiles bear designs of zero, one or two strands of rope (which are drawn in red). $\endgroup$
    – Russell May
    Feb 22, 2011 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.