2012-05-07: Quilt Colouring

I got this email from my wife:

> Honey,

> I’m making a quilt with 25 blocks. Each block has four colors on it. The colors I’m using are red, pink, green, yellow, blue, and green plaid.

> I don’t want to duplicate colors in a block or in the corners and I don’t want pink and red in the same corner (but pink and red in a block is okay.) Similarly with green and green plaid.

She’s a mathematician, so she knows about the Four color theorem. But she wasn’t sure if the graph was planar, and didn’t want to lay it out manually anyways.

Let’s work through the solution.

-

The first thing I wanted to do was see the structure of the quilt as a graph. Naturally, Graphviz is a natural choice. But, first I’d have to represent the graph in some way. I decided to go with a 5x5 matrix of blocks where each block was a structure of the four corner colors. The values of the nodes won’t really matter, so I’m just using unique symbols.

This is, of course, just a representation of the nodes. A graph also has edges. I decided to make another list of those. The first step is to turn a block into a list of edges. That’s pretty trivial:

If we loop through each of the blocks and call this, appending the results together, we’d get a bunch of disconnected sub-graphs. We’d just need to add in the block-crossing (i.e. corner) edges. The structure will look like this:

I briefly thought about making a new for form that did the appending as it went, rather than using the (apply append ....) pattern, but decided it wasn’t worth the time right here.

The inner part of the loop is a little bit complicated though, at least if we want to do it elegantly. The problem is that on the edges there aren’t adjacent blocks, so we don’t want to try connect them with the block under consideration. I use a cute little macro that sets up an exception handler that will just return an empty list if an inner hash-ref fails.

I thought about working out which edges I didn’t need to write down because the graph is undirected, but figure that since the size of the graph is so small it doesn’t really matter if I have a few extra edges.

You can see the dot file here: dot file, but unfortunately the picture wasn’t very helpful. You can see it here:

Now that I have the edges, I can create an adjacency list really simply:

Now that I have graph structure, it’s a simple matter of selecting colors. I decided to write it as an exhaustive greedy search, with randomness (for artistic reasons). For every node u connected to nodes vs, figure out what the options are, shuffle them, and try them in order:

I decided to have the colouring be a hash table where the values where singleton lists (to facilitate the call to append-map.)

The interesting thing comes from properly handling back-tracking in case a choice leads to an empty option list eventually. In addition to folding the colouring, I also have a fail procedure that goes back.

For the heck of it, I decided to keep track of how many back-trackings happened. While the use of continuations to implement back-tracking is definitely neat, unfortunately I’ve never run it and observed any failures. (Unless I reduce the number of colours to three, in which case it fails.)

Now that I have a colouring, how can I show it to my wife? Well, I’ll just render it out. Racket’s 2htdp/image library supports an algebra of images that will make this really simple.

First, we’ll render each individual square in the quilt as a square, assuming we have a way of turning our colours into colors that Racket supports.

Then, we’ll assemble each block (and give it a nice thick outline):

Finally, we go through and put each block in the right order:

Then stitch it all together and save it to a file:

The final thing is to write the function to translate between our colours and Racket’s colors. For simplicity, I’ve made a stronger colouring than my wife wanted. She didn’t want some colours to connect across corners, but I have treated every color uniformly. Even though she will use six colours, I’m really only using four and delaying the selection of which of the two variations of green and red she uses for the end.

You can see an example colouring:

When she finishes the quilt, I’ll update this post with a picture of what she went with.

(*UPDATE* Here’s her blog post about the finished quilt: read it!)

By the way, if you use this code at home, make sure you put the code in this order: