The why of colored domino puzzles

Yesterday I spent some time writing about a probably-very-simple mathematical recreation I’d been musing about.

Here’s a colored domino:

Here are two different tilings with plain dominoes of a 6x6 square region:

And here are the same two tilings, with “colors filled in” on those same dominoes:

The whole point here, I guess, is surfaced by those three diagrams.

When I tile a finite (or even infinite) region of a square lattice with plain dominoes, and then color each domino with exactly one blue and one orange square, there is a resulting pattern of orange and blue shapes produced by the edge-adjacent orange and blue squares of the dominoes. If we look at those “derived shapes” and ignore the domino tiling itself, we see they form a whole new tessellation of the same lattice region. I say “tessellation” instead of “tiling” because in general the resulting polyominoes may be different sizes and shapes… but it could be a tiling with a single polyomino, and it might even be a regular tiling.

In the left colored-in square above, for example, here’s an inventory what I see in the derived pattern, with a tally of how many squares they account for just as a check:

• two blue and three orange monominoes (5 squares)
• one orange and two blue dominoes (6 squares)
• one orange and three blue L-trominoes (12 squares)
• one blue I-tromino (3 squares)
• a big-ass orange decomino (10 squares)

In the right colored-in square, I see:

• fourteen blue and fourteen orange monominoes (28 squares)
• one orange and one blue T-tetromino (8 squares)

If you can’t see those shapes in the colored derived patterns—either because the colors are an accessibility problem¹, or because I’ve counted them up wrong, or done a poor job explaining—let me know.

So the overarching mathematical recreation here is something like: Which derived patterns can I make with colored dominoes, and is there some way to tell whether some particular pattern will be possible or impossible to derive?

Just what am I asking?

I made a few observations, and I then asked a few questions about the derived shapes. Here are a few I stumbled across along the way:

• For any tiling built with two-colored dominoes, is it always possible to flip some or all of the dominoes in place and produce a “derived checkerboard”?
• For some two-colored domino tilings, I found that the derived image is a tiling with I-trominoes. But I also noticed that some other I-tromino tilings can’t be derived from two-colored dominoes. Which ones? Why?
• Is it possible for the derived image to ever be a tiling with L-trominoes, for any finite (or infinite) region?
• Sometimes, for irregular and/or infinite regions, it looks like we can derive square tetrominoes. When and why?
• What other derived tetromino tilings, if any, are possible? What about larger polyominoes?
• What’s the largest single polyomino that can produce a derived tiling?
• It doesn’t appear that any 3x3 solid-color square can be derived, ever, from a two-colored domino tiling, not even isolated or in an infinite plane. That’s a nine-unit nonomino². What’s the smallest polyomino that can’t ever be made, even once, with colored dominoes?
• If we tile a region “randomly” (which may be a tricky thing to define rigorously), what is the distribution of polyomino shapes and sizes we can expect to see? In what ways does it depend on the region?

In reviewing what I wrote yesterday, I realize that there are a few implicit questions that I didn’t really surface. Let’s do those now.

Recall that a lot of my work involves genetic programming, and that I’m especially interested in representations and the user experience of model-building with “automated software synthesis”. So maybe sometimes, because I’m too close to the work as they say, I neglect to say out loud why I’m here.

I did mention that I think that mathematical recreations are an excellent way to better understand the philosophy—and also the subjective experience—of “doing intelligence”. One particular (and stylized) version of “intelligence” at least.

Mathematical and computational recreations are, I think, the most humane of the abstractions we undertake. They’re “small” in the sense of presentation, but the best carry with them a whole shadowy network of abstruse and difficult mathematical infrastructure. It’s easy to say, “Can you fit these shapes into this outline?” but the little heuristic maneuver we make when we change that question to, “Under what circumstances can shapes be placed in a given outline?” is (as Clemens says) the difference between the lightning-bug and the lightning.

“Recreations” aren’t ever supposed to be daunting. They should rather delight us at some point, in much the same way as a good joke delights us with a punchline, by juxtaposing some well-known mundanities in a new-to-us way that makes us gawp—or at least say, “Huh!”—when we see their solutions. But even the simplest or most commonplace mathematical recreation drags around a penumbral potential network of little twists and side-steps into the most advanced and modern abstract thinking in the human world.

So here are my implicit questions for this “recreation”—my long-term goals, as it were:

• Is it feasible to build a “recognizer” that will determine whether a particular derived polyomino can or can’t be constructed from two-colored dominoes?
• Is it feasible to build a “recognizer” that will determine the feasibility of an entire derived color pattern? That is, given a color pattern, it will tell you whether it can be built from two-colored dominoes?
• Can that one provide an explanation for why a particular pattern is infeasible?
• You might have noticed I’ve said “two-colored dominoes” quite a few times just now. Generalize everything above to three-colored dominoes, or N-colored dominoes. Generalize everything above to two-colored trominoes, or two-colored polyominoes, or multiple shapes of polyomino—general tilings, with general colorings. Or to polykings instead of polyominoes. Or to different lattices. Or to abstract tessellations themselves, like Voronoi diagrams of random points… for abstracted versions of “random points”… in abstracted surfaces and spaces… and so on.

That gets penumbral pretty quick, doesn’t it?

But that’s what I see every time I come across a little abstract “game” like this. Down those paths are Number Theory and Graph Theory and Probability Theory, real practical engineering stuff about types and representations one would use for computer programs, about standard and exotic execution schemes, parallelization algorithms, user interface and experience, computational complexity, ontology and epistemology of science, mathematics and engineering. And if it doesn’t feel too ambitious already, consider that what my habit suggests is that these be approached in an iterative and agile way, by biting off small chunks and making a series of subjectively-confusing forays into the Mangle itself.

In other words: Before I’ll permit you to say you’re “working on artificial intelligence”, you need to be mindful enough to model your own internal dynamics as you work through a “simple” mathematical recreation like this. Including the open-endedness of the series of questions. Including the penumbral external knowledge you stumble across along the way. Including the dead ends and mistakes you make, the heuristics (good and bad) you bring to bear, the habits you have and the ways you represent starting points and endpoints and strive to build links between them.

What I’m asking for is more stories of what it feels like to think. To realize stuff; to notice; to stumble and recover. Because so far—and for the foreseeable future—it’s only natural human people who can think and then tell the story of what it felt like when they did it.

Some Mangle-side introspection

Thinking back, one of the things that struck me as odd yesterday didn’t bubble up until this morning. It involved the difficulty I had when I tried to build a derived I-tromino tiling out of colored dominoes.

I was able to fiddle with colored dominoes and end up with a derived tiling with I-trominoes. But then I drew a different I-tromino tiling, and tried to build it with colored dominoes, and failed. Here’s the image of the I-tromino tiling, and one domino:

I had said in passing that “you should find the stumbling block pretty quickly”. But I wanted to go back and see it for myself, not quickly. Why is it impossible to make this pattern, for at least some version of “why”?

I’ve been thinking about it, and tried to better capture what I meant when I thought I “saw pretty quickly”: that there’s a place in the impossible tiling where three trominoes share edges. Here’s a bit of exploratory drawing to try to help me understand what I “saw”.

In the upper left is the “impossible” I-tromino tiling, and I’ve colored as many of the trominoes as I could manage with blue and orange. That is, I started coloring the first tile, and then colored all the adjacent tiles I could manage with the opposite color, and so on. The uncolored tiles are ones that touch at least one tile of each color, and so—because these derived tiles are defined as being all the contiguous squares of one color that share edges—they can’t be colored orange or they would “merge” with the adjacent orange tiles, and they can’t be blue because they’d “merge” with the adjacent blue tiles.

So it felt as though there was something about the way in which these derived tiles were adjacent to one another. In the top right, I have drawn an appropriately-colored circle in the middle of each I-tromino, and connected those vertices with edges wherever they share adjacent lattice squares. Call it the “adjacency graph” of the derived tiling I was aiming for.

In the bottom row I did the same for the I-tromino derived tiling that “worked”.

Here’s what I notice: There’s no way to color the adjacency graph of the top “impossible” derived tiling with only two colors, so that each edge connects two nodes with the opposite colors. Just no way. You don’t need to know the theorems or mathematical background of graph coloring to realize this… but it does make me think something useful could be out there in that big part of the penumbra, for later.

But notice that this is a very different representation of the same underlying “stuff”. When I said there was a square lattice, and that putting colored blocks in that lattice would produce a derived “tessellation” of self-contained adjacent orange and blue blobs of squares that share edges, this adjacency graph was… well, kind of ruled out right there. Somehow.

In the bottom row, the feasible I-tromino tiling produces an adjacency graph that I can color with two colors. Well, OK, that should be obvious in some sense too, right? It’s still “the same thing”, just represented in a different way.

Is there something about the adjacency diagram of the top tromino pattern, disregarding the colors and just looking at the structure, that I can say is different from the one below? Well, I do notice one thing: there aren’t any triangles in it. That seems interesting, and I do a bit of Wikipedia surfing and stumble on this observation that “every 2-colorable graph is triangle-free”. To be honest, I’ve never had any formal Graph Theory training (I’m just a poor country Biologist, and a defrocked one at that), so I’m not sure the whispered stories I’ve picked up from the kids on the street are enough for me to really grok what that means.

It sounds cool. But this is a story of what it feels like to “do intelligence” (or whatever I substitute), so let me continue: Just as I thought, “Hey, I bet I could delete the nodes of the graph that form triangles, and hey those are the ones that are still white… and then it would be 2-colorable!” something else struck me.

Can you see it, before I tell you about it? Look at the colored I-tromino design, and recall how we got here. Think about assembling it with two-colored dominoes. Not there yet? Think about building it with two-colored dominoes after you’ve torn out the white squares. Because that what it means when I say “remove the nodes from the adjacency graph”: it means that the squares under those trominoes are part of the region I’m tiling at all. I can’t put dominoes there, and I can’t see trominoes there. Nothing is there.

So while the triangles seem to be important and possibly useful, it’s also clear thet’re not the whole story. Because it’s also impossible to form a derived pattern of three blue squares in a row—at least if there aren’t orange squares right next to them. You might be able to build the top of the blue dongle tromino in the middle, by tiling two-color dominoes out from the “good” part of the diagram at the right side. But even if you manage to make the top square blue, where will you get the other two blue squares from?

Same with the blue and orange trominoes on the left side of the diagram. Maybe somehow you can color the top and bottom squares of each; the tops by “reaching across” from… well probably you can’t do the top and bottoms, because something far away in the diagram will reach over and cause trouble for you.

What is that “something far away”, I wonder? I don’t quite know.

Maybe, I think, there’s something about the domino tiling that I also need to take into account. I mean, that will also have an adjacency graph of its own. And (I suppose) maybe there’s some kind of relation between the lattice adjacency graph of the tiled region of squares, and the adjacency graph of the domino tiling, and the adjacency graph of the derived color tiling.

But what’s a “relationship”, in this case? And will it be enough to see what might be useful? For me, or for my evolved programs?

Summing up

So in any case, this is what it’s been like sketching this exploration, or recreation, or project, or whatever I should call it. You might feel it’s not much “implementation”—not of software, though it’s not clear to me yet exactly what software is called for, but neither is it “implementation” of anything well-formed enough to have “answers” yet. I don’t know whether it’s possible to construct tilings of other polyominoes, and I haven’t even bothered making random two-colored domino tilings to see what derived polyominoes I get.

Imagine a napkin, and I’ve drawn some little circles-and-arrows diagrams and scratched a bunch of stuff out, and maybe written 2-COLORABLE PLANAR GRAPHS? right over a little frowny-face caricature of Leonhard Euler. But not much else.

But what does that napkin “mean”?

Well, as you can imagine, I’m thinking about writing some code. For example, a lot of my questions right now involve vague stuff that sounds like types or classes: Region and Lattice and Tile and Tesselation. Some of the stuff I’ve talked about involves functions or methods that sound like feasible?(tiling) or adjacent?(tile1,tile2,tiling) or Tesselation#random-tiling(tiles). And some of this stuff I’ve realized overnight feels like maybe those types or objects are reaching over towards Graph Theory somehow, and that maybe I’ll need to consider it part of my toolkit sooner than later.

And in the derived layer of my own long-term goals—the ones where I’m considering what it would be like for an automated software synthesis system to be “working on” these same open questions—I have to ask what it would need to “know” before it had a chance.

Now a lot of people, possibly some of them reading this, may be tempted in these trying times to mutter a deep network might work. Hey, that’s true! For example, it seems feasible that you could drop a region you wanted tiled with 2-colored dominoes into a neural network as a sort of binary array, and that it would “place tiles” on that region, and that it might then try to match a given target pattern. Or maybe you could just address the predicate questions I’ve been asking: show it (in some format) a target derived tiling, and have it predict whether or not that derived pattern could be produced from two-colored dominoes.

Those seem like reasonable tasks.

But you know how people are always saying “neural network representations are opaque”? This might be as good example as I’ve seen of the ways in which those folks mean “opaque”. This is not to say the approach is infeasible, and indeed I think I may try it out myself some time soon, now I’ve said it out loud. I mean: What does it tell you about intelligence for a network to have learned to classify patterns? If, as it appears, some insights from Graph Theory about 2-colorable graphs might be useful for you or me to solve the problem, does that imply that Graph Theory is “somewhere inside” the matrix algebra executed by the working neural network?

Honestly, I’d like to think it was in there somewhere. Because almost immediately I’d ask you to point to it, and then you’d be where I am now. And yes—of course there’s no place in my neural network where you could point and say, “That is Graph Theory.” Granted.

But I can tell you what I realize I’m thinking, and what I’m looking up, and whose books and web pages I’m reading, and what I remember I learned twenty years ago when some older kid in the Math Gang gave me a dim glimpse of his tattered copy of Mathematical Intelligencer, just enough to whet my appetites, and then chuckled and said, “Not until you’re older.”

OK, that part didn’t happen. But—will your neural network tell jokes? Will my genetic programming thing?

We all want something to strive for.