Where things go wrong

A belated return to domino-tiling processes here.

I’m not including pictures in this version; that’s a matter of updating inkscape, not a permanent issue. Remember why everything always says “Draft” in the margin!

Suppose we have a single polygonal region of contiguous squares of a lattice. It doesn’t have to be an even number of squares, and it doesn’t need to be a rectangular region. It can be of any size, but for now let’s make sure it has at least three cells in it.

I’ve already written a lot about dominoes. These are two-square rectangles, the sort that would exactly cover two edge-adjacent squares of this square lattice. Imagine the lines between the squares are little ridges (like on a modern Scrabble board), and that the dominoes have a little crease on their equator so they can straddle one of those ridges.

You “place” a domino in a region by positioning it so it covers two adjacent unoccupied squares of the region, without crossing the outer boundary of the region.

Here’s a simple random process I’d like to investigate:

1. Pick an arbitrary adjacent pair of squares in the region of interest, and place the first domino there. The “color” of the two ends of the domino doesn’t matter for us now; just plop it down somewhere, either horizontally or vertically. It can be in the middle, it can be at an edge. Pick the location with uniform probability over all the possible locations in the region we’re tiling. [That may be the first puzzle.]
2. To place the next domino, pick one of the possible positions in the lattice where at least one edge is touching an existing domino. The next domino could be touching two prior dominoes, or it could be end-on touching one, or it could be nestled against the long side of one. But it must share at least one edge of some existing domino. If there are one or more such possible position, pick one of them with uniform probability and place a domino there. Whether you were able to place a domino or not in this step, go to the next step.
3. If you have placed a domino in the previous step, go back and repeat step 2. If you’ve managed to tile the region completely, then put a “marker” into the special cup to the side labeled “done”. If the region isn’t completely tiled with dominoes, but you can’t place the next domino—and therefore there are some edge-adjacent positions that are single squares—what I want you to do is leave a “marker” in every single unoccupied square that is adjacent to the dominoes you’ve placed.
4. Keep the markers to record where the “unsolved squares” are. Remove all the dominoes, and start again at step (1), picking a random starting position at random again.

Where will the markers tend to accumulate, for the region you’ve picked?

Some examples

Let’s start small. Suppose you were tiling a three-square region. I don’t think it matters whether it’s L-shaped or I-shaped. You have two possible places to start with the first domino, and as soon as you place one of those the other end will become unavailable. So for a three-square region, you’ll end up over time with about half the markers on one end, and half on the other, and none in the middle, and none in the cup.

Suppose you were tiling a four-tile region (a tetromino). There are a few different ones, right? Let’s look at some of those:

• An I (straight) tetromino: There are three different places to put the first domino. If you pick the ones at either end for the first domino, then you can tile the whole tetromino and so there will end up being a marker in the cup (signifying completion). If you pick the middle pair of squares, then you’ll end up one one marker in each of the two end squares in those cases. So the “marker pile” will tend to be 2/3 in the cup, and 1/6 on each end of the tetromino, and none in the middle two squares of the tetromino.
• An O (square) tetromino: There are four different places to put the first domino. No matter which one you pick, you will always be able to place the second domino and completely tile the region, so all markers will end up in the cup.
• A T-tetromino: There are three different places to put the first domino. In each of those cases, you immediately block the other two “ears” of the T shape, and you can never completely tile the region. So no markers will end up in the cup, no marker will ever be in the center of the T, and an equal number will end up on the three ears of the tetromino.
• The L/J and S/Z tetrominoes work out to be just like the straight one.

Obviously, the shape of the region does have an effect on the outcomes. The “histogram” of markers we end up with after many trials of this little game would help, in some sense, identify the “topological type” of the tetromino, even if you didn’t have a picture. So if for example I said “four squares, and all markers in the cup”, you’d know that the region was a square.

Needless to say, things get more complicated as we grow the region. That’s the point!

The suspicion (and one I hope to make time to write the ClojureScript to explore) is that something like the effects we were seeing in these earlier experiments I did with Aztec diamonds will come into play. But in a roundabout way, right? Where will the tokens end up if we start from an Aztec diamond shape? Will they be near the edges, or be near the center? These are qualitatively different “states” in these regions, when it comes to tiling and diffusion. What will happen when we apply this “marking problems” process?

Formulate your hypotheses and suspicions, and take some time to write some code to explore this if you like. I’ll see if I can get my ClojureScript environment back into shape so I can try it for myself.