Some tiling challenges

The start of a new mathematical recreation. I talk about colored domino tilings, and some odd problems about making one thing out of another thing, and the other thing out of the one thing. I end up being confused about what can and cannot be made. This is intended to be engaging and entertaining, rather than annoying and tiresome. Oh and also I try to talk about how crucial it is to make mistakes.

If it helps, there are some pretty pictures, including this one:

---

In my writing queue are a number of “small” puzzle-like problems involving tiling. There’s a lively and diverse community of mathematicians, physicists and extraordinary amateurs who find easily-described puzzles of the form “can you arrange these shapes inside this outline on a lattice?”

You’ve seen them, surely. Some of the most commonly-seen are

• Golomb-style tetromino packing puzzles, where you try to place one of every 4-square contiguous polyomino into a rectangular region
• Tangram puzzles, where you have a fixed set of simple plane pieces and are trying to match a proposed shadowy outline
• Domino tilings, where interesting advanced mathematical concepts and statistical mechanics models seem to magically drop out of simple challenges like “how many ways can you cover this shape with dominoes, and oh by the way do you notice anything strange about how the ensemble of solutions looks?” (For example, the fascinating effects of boundary conditions on random tilings of a square and an Aztec diamond)

This is like that, but somewhat different.

Tiling problems as attractive nuisance

I’ve lately been thinking back a lot to Martin Gardner’s columns in Scientific American, and how they influenced a generation of computer people and… well, whatever we all are. In his monthly columns in the back of the magazine, he wrote for a diverse audience about things not normally covered in publications they’d tend to run across in their daily lives. Now, all the nerds know about Conway’s Game of Life, not because of its inherent importance but because of the community of aficionados Gardner (and many other authors) constructed. So too with flexagons and fractals and game theory (the Prisoner’s Dilemma) and Penrose tilings and on and on….

I’ll write (a lot) more about “mathematical recreations” in a bit. Right now I just want to plant a flag, and remind myself how deeply these things—this entire category of behavior we call “puzzles” but which are not homework-problem or crossword-puzzle style there’s-a-correct-anwer challenges, and which are in fact open-ended invitations to a wilderness of unasked questions with unforeseen practical consequences—have infected nerd culture. Can you do this, with these simple components? is a sort of lever one can use to move a world, as long as we’re given a place to stand together. It’s not a constrained pedagogical exercise, not a “homework problem” with a “right answer”.

Indeed, some of the simplest questions you can ask, the simplest heuristic twists one can apply to the starting idea, like How many ways are there to do this, with these? or If you do this with these, what do you notice?, are often the best paths to doing actually useful work. By making these small twists, little “sure, but what if—” sidesteps of problems that seem trivial, we can quickly step off the textbook path and find ourselves in the wilderness of basic research, thesis-grade exploratory work that nobody ever has thought about.

And that stuff can be useful. Nobody much cared about the probability of matching the ends of random-seeming strings with the ends of other random-seeming strings, until we started filling up petabyte-sized databases of… well, basically just strings. That was a “recreational” problem for many decades, a weird old probability theory dead-end… until suddenly one day it wasn’t.

So for the duration of this brief (?) series of essays, that’s where I’ll be going. I’ll spend a little time on each of several tiling problems. I have quite a few tucked away in notebooks, of varying style and complexity. In general they’re all just little open-ended sidesteps from well-traveled paths, things you can find explanations of on Wikipedia pages or not far from there.

Why bother?

I want to talk about them for a few reasons.

First, because of a many-years suspicion of mine that Martin Gardner’s approach might save the world, or at least help it be a qualitatively better place. As you can probably imagine, this one feels to most people I talk with as if it will be the longest stretch. Not everybody sees what I do, in other words, and even I think it will end up being the most convoluted case I plan to make. And that’s fine. Just letting you know that it’s on the table, in the background, wherever we go, it’s there with us, &c &c.

Second, because I think the Coding Dojo culture in which one works through agile software developers’ “katas” (which may need a new name¹) is important and lovely. The ones I mean aren’t coding exercises in the traditional sense of learn-a-new-programming-concept end-of-the-chapter problems. Rather, the problems here are often ridiculously “easy” sounding to programmers who have never done a dojo, and they often have well-known “best practice” algorithms out there in Stack Overflow ready to be cut-and-pasted into one’s production codebase.

But the point of a Coding Dojo kata is to collaboratively see one’s self and one’s peers face and overcome the internal challenges that even “simple” programming can surface. To address them mindfully with skills one wants to improve and hone.

As I said above, most nerds know about the Game of Life. Many have written their own versions. In a Coding Dojo kata built on the Game of Life, the point is to not learn the algorithm or even the behavior, but to implement it— mindfully and introspectively—and to observe the path itself, and the steps one takes along that path. It’s not about the feature set as such, any more than a Dungeons and Dragons game is “about” getting all the gold or even fighting the monsters.²

Third, because I work in the field of genetic programming, and many of my colleagues imagine that what they do is a kind of “artificial intelligence”. An ability to work through even simple mathematical recreations seems to me to be a pretty straightforward facet of what we mean when we say a person is “naturally intelligent”. Therefore let’s use mathematical recreations as benchmarks for software synthesis systems. What could go wrong?³

Fourth, I want to practice my Learning in Public, and improve my own skills and expand what I’m able to build and communicate in that mode. This is more than just “deliberate practice”; more like visibly deliberate practice, with all the mis-steps and dead ends and stupid messy human crap right there written down in my permanent record.

Because people should see others making mistakes, they should see the fallible body of the author—even in a written work with pedagogical intent—the better to identify and place themselves in the author/teacher’s place. I’ve talked about that enough before, and I’ll speak over-much about it again soon. Suffice to say I’m not here to convince you it’s important. Just saying it’s on the list.

Then there’s the deep philosophical (and practical!) question of the composition and decomposition of problems themselves.

Tiling problems are a remarkably good example of what I mean here: Start with Can you fill this space with these shapes? There’s an implicit call in that to a whole big field of pretty-advanced mathematics and computer science—constraint satisfaction problems—because of course the explicit task can be framed of as something about optimally filling a container without simultaneously overlapping pieces or coloring outside the lines.

But then again, it might also be framed as something like a question about graph theory: maybe what I’m asking is for you to give me a perfect matching of some particular graph I’ve drawn, which is the lattice of squares inside the outline, connected by edges wherever two are next to one another.

So in other words, maybe this is about “subdividing” a thing according to rules, instead of “building” a thing without violating constraints. And in this particular exploration, I’ll plop another layer of tiling on top of a lower level of tiling. Do we approach both “layers” in the same way, or is it suddenly easier to use assembly for one, and subdivision for the other?

And finally, there’s the Great Frontier schtick. People hear “games” or “recreations” or even “theory” and all they hear is “useless”. Bullshit, and you’re an asshole if you think “theory” means “useless”. Because until somebody’s gone there and looked, nobody has a chance to know what these things might be good for.

Maybe not within the span of your or my lifetime. Revisit my throw-away comment about string overlaps and bioinformatics, or re-read the inevitable Galois-dies-in-a-duel-before-anybody-understands-his-work anecdote. The cognitive and technical pieces from which we build tools for working in these domains are the same pieces we might use to do any sort of engineering project.

And I literally mean any sort. Who would have imagined that you’d be using Number Theory to read this essay? And yet oh look hey what’s this? Alan Turing’s weird-ass paper in 1936 on some number theory stuff, right? That was super abstruse and esoteric. Nobody ever really looked at that again, did they?

Yeah well. If you don’t want to “waste your time” playing with tilings, don’t worry, it’s OK. But keep a close eye on the people who “play” with origami and artificial life now, is all I’m saying.

Getting set up

What I have typically done here is write (sometimes but not always too much), and show pictures, and maybe sometimes have some animated programmatic content. Little animations or interactive widgets with which one can explore in the browser.

But I usually do those in an ad hoc kind of way.

I wonder if there’s a style guide, or a standard library or visual grammar I can develop for these… things. For some of the more recent things, I’ve used graphics drawn (with some swearing) in Google Slides and exported as .png files. That’s pretty icky. And for animated stuff like the stuff about lattice polymers I’ve used the little ClojureScript Processing clone Quil. That was nice enough, though the infrastructure needed for me to create a new Quil project, write and test the code, and then “export” (more like “extract”) a self-contained JavaScript widget to place on the web page has not been especially elegant or charming.

So maybe it’s time to revisit some tools, is all I’m saying. Rather than speak specifically about the tools and prospects, let’s see what I find as I propose and work through a new tiling thing.

Making tiles out of tiles

Let me state the question here:

For any rectangle of at least two squares, there will be at least one way to tile it with dominoes. Here, for example, are two different tilings of a six-by-six square with (plain white) dominoes:

Suppose that instead of plain white dominoes, we use colored dominoes. For example, suppose every domino we use is blue on one end, and orange on the other. Like this:

I suppose we can think of a tiling of a region with colored dominoes is just a regular tiling with plain dominoes, plus an orientation for each domino in its place. If a tile is horizontal in the tiling, is it orange-on-the-left or orange-on-the-right? If it’s vertical, is it blue-on-top or blue-on-the-bottom?

Here are the same tilings I showed above, with an arbitrary assignment of colored dominoes instead of plain white ones:

In the left diagram, I just dropped a colored domino on top of each white domino “slot” in the plain diagram above. And you can sort of tell I was playing around when I was filling in the right-hand one, because it’s almost a perfect checkerboard. It turns out that—in this case at least—I could have made a perfect checkerboard. Here, let me leave out one domino, so you can see how I might have chosen differently:

That seems interesting, somehow. I begin to suspect I could make a checkerboard pattern out of the colored squares in any domino tiling. But frankly checkerboards are kinda boring, and I actually stumbled across that observation while I was doing something else. That signals me to look a bit deeper.

Looking at the left colored square, it seems to me that several sorts of blue-and-orange patterns can be made by (somehow) picking the “right” arrangement of both dominoes in the tiling, and then also the colors for each domino. Not every possible pattern maybe, but some interesting ones.

So: If we place the dominoes and then look at the contiguous polyomino shapes the blue and orange squares have formed, what can we build? What can’t be built?

For instance, can the dominoes be arranged to form a higher-order tiling of a region, using only blue-and-orange I-trominoes (that is, \(1\times3\) blocks of non-adjacent blue and orange)? Yes, at least in some cases; here’s a proof of concept I’ve made using a very simple domino tiling (on the left) which I’ve colored on the right:

Based on the observation (suspicion, really) that I could make any domino tiling into a checkerboard tiling if I tried hard enough, it feels as if the next question should probably be something like “Can any I-tromino tiling of a region be made using colored dominoes?” And if not, then which I-tromino tilings can be constructed using colored dominoes?

I spent a few minutes just now playing with diagrams, and I think it’s likely that only a few I-tromino tilings can be constructed in this way. Here’s an I-tromino tiling that I found that can’t be formed from colored domino patterns, with a colored domino floating there so you can practice visualizing where things break down. Try placing dominoes on the grid, in such a way that each tromino is only one color, and no tromino shares an edge with any other tromino of the same color.

You should find the stumbling block pretty quickly: In this arrangement of trominoes, there’s a place at the bottom of the top left square where three trominoes touch. The fact that there are dominoes involved doesn’t even matter; you can’t color these trominoes at all with only two colors—even just using individual squares—and still avoid a shared edge between two of the same color. And since I’m (implicitly) defining a “colored polyomino” as any blob of same-colored squares that share edges, two “trominoes” of the same color that touch on an edge aren’t really “trominoes” at all, they’re a hexomino. Or worse.

So I suppose, given one that worked and one that didn’t, I can say that sometimes a tiling with orange and blue I-trominoes can be formed out of a tiling of orange-and-blue dominoes.

That begs the question: When? Which domino tilings can be “translated” into valid two-color tromino tilings? Which tromino tilings can be formed from colored dominoes? Why? Is it enough to avoid three-way edges in the higher-order level?

I hope you’re starting to get a feel for the overlapping composed problems here, at least a bit. Not every region can be tiled with dominoes, and also not every region can can be tiled with I-trominoes. A first approximation to my questions here would be to find the regions that can be tiled with either shape. But it feels as if there’s something more lurking down inside there, something that’s may be very interesting when we dig down into it.

Let me shift the ground a bit more, and get a bit more general. For any given tiling of the region with polyominoes of any shape and size, can you tell if it can be formed from a tiling of colored dominoes?

I want to be very general here. I don’t just mean tilings with one particular polyomino—though that is definitely an interesting path to walk along. For instance, I showed at least one I-tromino pattern that worked, and one that didn’t. What about L-trominoes? (I don’t know.)

What about square tetrominoes?

Things are getting trickier, but it’s possible to build a tiling of 2x2 color squares out of colored dominoes, at least for some regions (including an infinite plane).

Here’s a sketch I made of one possible domino/square arrangement. All of the dominoes are in the same (vertical) position, and they’re colored so that in each row we have two columns containing dominoes colored with blue above, then two with blue below; within each column they alternate “up” vs “down” in every row.

I’ve shown eight dominoes with colors, and another sixteen without the colors filled in. You can see, I hope, that if we extend both tilings out in all directions, we can get a “checkerboard” of 2x2 squares. As long as we’re happy having either infinite or jaggy edges, that is. It does not seem to be possible to tile a rectangle with dominoes and (only) colored squares.

At least I think not…?

We can play this game for quite a while, expanding the colored “meta-tiles” to be bigger and more convoluted. Where does it become impossible to even draw a single polyomino of one color, surrounded on all edges by the other color?

I can’t say where the exact limit is yet, but I’m pretty confident that neither you nor I can draw even a single 3x3 blue square surrounded on all sides by orange squares. Because that would demand we use at least one domino with two blue squares.

I could be wrong. You should check.

But on the other hand, it’s also clear that I could construct an arbitrarily-large “polyomino” that was long and thin and possible not too squiggly. For instance, I could make an arbitrarily tall blue rectangle that’s one square wide. There are lots of indefinitely big single-color blobs I can build, though I don’t think many of them will tile.

For example, in the original random colored domino examples I showed above, there’s a big orange decomino in the left diagram, leaning in from the top right edge like a top-heavy gallows or something.

Seeing that big blob, and thinking about the prospect of indefinitely long “strands” of the same sort, I start to wonder about the distribution of colored polyominoes sizes, for various random tilings. This takes us over towards Percolation Theory, a whole other region of Physics we might get sucked into some time soon.

Let’s pull back for now, and think about what it is we’re seeing. Rather, what the story is we seem to be telling.

There is a lattice. As long as it’s empty, it’s everywhere and infinite and all the same.

There are (plain) dominoes. Before I place the first one on the lattice, they are all the same. Once they’re on the lattice, something has happened to the lattice-and-domino combination. The first domino I place gives me distance, and to some extent orientation, on the lattice. Colored dominoes do something more.

But it’s not necessarily correct to think of this merely as a progression of new things affecting earlier or simpler ones. In this problem of translating one tiling “into” another, there’s a sense that influence reaches both directions.

The first placed domino (colored or not) in some sense restricts the places I can put a second valid one on the lattice; they can’t overlap. But it’s also the case that no single-colored “higher-order tile” can contain even one entire domino. It seems as though I can “get into trouble” whether I start from a plain domino tiling and try to color the dominoes in place to make a higher-order colored tiling, or whether I start from the outlines of the higher-order tiling and try to assemble dominoes to cover it. It is even true (for example, with 3x3 higher-order colored tiles) that even if I try to place dominoes one at a time in the best possible order to avoid violating the domino rules and the higher-order rules, I’m still shit out of luck.

But it’s not the dominoes’ fault, and it’s not the colors’ fault, and it’s not even the fault of the higher-order lattice I’m trying to make. Something is emerging from the overlapping constraints.

And yet if I just drop random colored dominoes on a lattice, I see all kinds of big wobbly polyominoes. They’re not all the same size, and they don’t make a (uniform) tiling, but they do make a tesselation of the region, and there are sure a lot of different shapes. As long as I don’t care about the size and/or shape of the higher-order color tiles, every arrangement of colored dominoes is some tesselation composed simultaneously of both dominoes and higher-order colored blobs.

Just writing that makes me want to ask a new question: If I just randomly tile a region with colored dominoes, how many other tilings of colored dominoes will form the same color pattern? That just feels salient.

I’ll have to look into that….

Heuristic moves

I’ve mentioned before how much I admire Andrew Abbott’s Methods of Discovery. It’s framed as advice to young academics on their career path in the social sciences, but the thing I want to surface here is what Abbott calls his “heuristics” for transforming ideas into actionable new ideas for new projects. In his context, this is a collection of often-straightforward maneuvers one can undertake to move from an interesting-but-published (and therefore “done” in the Academic sense) research project to another—hopefully and probably new—project.

You might also say it’s a collection of design patterns for research questions, or something closer to software developers’ refactoring patterns: “When you see something that is about one level of social organization (for example, cities), consider it from an adjacent level (for example, neighborhoods of cities).” I like the book so very much because it’s cast not just in the context of research, and surely not just in some particular social science, but as a suite of moves that can help frame questions generally. I can see the way to map almost every one of them onto any subdiscipline in Complexology.

So here’s the analogy with what I’m writing about now. The academic literature on tilings, even just domino tilings, is remarkably large, and spans many decades. What we might call the “peripheral” literature of puzzles and columns and blog posts and online communities and mailing lists and monthly competitions is even larger, since I will assume almost all the professional mathematicians, physicists and computational geometers out there will also follow and contribute to the puzzle literature.

So it’s almost certain that something very much like the colored dominoes thing I’ve talked about here is tucked away in either the “umbral” literature in journals and preprints, or in the “penumbral” literature of old magazine columns and suchlike. Maybe somebody said something back in 1993 on one of the mailing lists or online collections like Erich Friedman’s Math Magic or George Sicherman’s Polyform Curiosities.

The heuristic moves I’ve made in taking domino tilings—which will appear in any introductory piece on tiling—to colored dominoes is surely not new. But I wouldn’t be surprised, having done a few passes through Google Scholar looking, to find that nobody’s done much about this sort of “higher-order” tilings “drawn” with colored dominoes. And by the same token (but its other side), I also wouldn’t be surprised if this turned out to be exactly the same as some well-known textbook stuff from, say, Percolation Theory. Or maybe the algorithms used in developing dithering patterns since the 1970s. I wouldn’t know.

And it doesn’t matter. I doubt that this is completely unexplored territory, and I also doubt that it’s well-explored. The former, because I’m old enough to have learned that I’m not very smart or creative; the latter because I have a bad habit of reading more or less everything. Not remembering it… just reading it.

I’d like to hear about anything related, though, and I’ll pass it along here, or in the subsequent chapters of this exploration. Twitter is the best public route, as of this writing.

Some observations and plans

While I haven’t been programming or doing fancy-ass mathematics in this particular essay, I’ve been doing some technical stuff in the background that I should take note of.

First, the diagrams here are quite different from the ones I’ve been using in earlier writings. Those were made, because of convenience and my own laziness, with the drawing tools of Google Slides, and exported as .png image files. While those older images sufficed for the day, they weren’t ever very nice. So I’ve tried here to use a better format—the vector-based resolution-independent svg format—so the diagrams are reusable, scalable, and potentially even something people could download and edit for themselves.

There’s a week-long back-story I’m not telling you. It involved looking at Adobe Illustrator, and LaTeX drawing tools and packages, and eventually settling on the open source Inkscape app. And then several days trying to get it to install and/or compile on my Mac, and finding dependencies, and learning the new muscle skills I need to be able to draw a square (Inkscape uses ctrl as its scale control modifier key, while all Mac programs tend to use command) or Undo vs Zoom (Inkscape uses ctrl-Z for undo, command-Z for Zoom; Macs use command-Z for undo, and leave ctrl-Z, and most other control-keys, undefined). And so there was swearing. And there are bugs. And crashes. But… well, so far it has been remarkably painless.

So I can now make and share svg diagrams—at least some simple ones. And unlike the png bitmaps I had been using, these files are actually served in situ in their editable format [view the source], so if I ever find an error or need to revisit an older diagram, I can re-open it in Inkscape and edit the kinks out. So that will be my plan for the future.

As for the writing part: While I was able to state some questions and problems, and then work through a few examples and diagrams by hand, what I haven’t yet done is the programming or mathematics it will take to really get ahold of these topics. I want to do that in the Learning in Public mode I accuse Ron Jeffries of inventing: Telling the story of how I proceed, including the mistakes and backtracking and confusions and dead ends, because (I think) too often we present our work as if those things never happened.

Not just academics, mind you. Teachers lie all the time about how one works in service of giving you the right answer… but so do programmers, so do doctors, so do home improvement sites and novelists. I think we could all use a bit more, “Huh. Would you look at that. Now see what I did there? That was dumb.”

Which is to say, not more that was dumb said to ourselves, but rather seeing people we admire, who are teaching us how to think and work and act, themselves saying that was dumb about what they’re experiencing as they live over here, on the other side of the keyboard and the printed page. I’d like to be a person you admire because I say “that was dumb” about myself, and then go on to explain why. The biggest trick the Devil ever pulled was when he made it seem as though the stories we read in books were born correct and complete in the lives of the people acting them out. So I aim to fix that. Or do my part to make the point.

Finally, there’s something I haven’t yet done here, which I should and will do next time: provide references. I should connect this stuff I’m talking about to the community of people already out there in the world who have done similar, or the same, or who have gotten close and therefore explored some nearby part of the terrain. Even if they haven’t necessarily informed my paltry scant insights here, I want this account to be connected to their own versions of the world. And so, as to citations, references, inspirations, suggestions: I needs those.

More soon.