How many different colors does this quilt need?

March 23, 2014 11:46 PM

My wife wants to make a 10 x 12 square quilt with a random-looking pattern. How many colors would she need for a quilt that follows these rules: 1) No two patches of the same color may touch each other, vertically, horizontally, or diagonally; 2) No pair of patches may be repeated in the same orientation (i.e., if there is a red patch above a blue patch, that combination may not be repeated, but you may have a blue patch above a red patch); 3) There are no patches of the same color that have the same vertical and horizontal offset: i.e., if there is a red patch with a second red patch that is one down and two across, there may not be a third red patch that's the same distance down and across from that second patch.
posted by Joe in Australia to Science & Nature (17 answers total)

How big are the patches meant to be? 10x12 made of 1" squares is going to be very different from 10x12 made up of 6" squares.
posted by MeghanC at 12:22 AM on March 24, 2014

Response by poster: I presume around six inches, but I don't actually know. It shouldn't change the answer, though.
posted by Joe in Australia at 12:24 AM on March 24, 2014 [1 favorite]

When she has the answer, your wife might find this granny-square-colour generator useful.
posted by Kerasia at 12:51 AM on March 24, 2014 [2 favorites]

Well is it 10 squares by 12 squares? If that's the case then their size wouldn't matter. But if it's a 10 foot by 12 foot quilt, for example, subdivided into squares, the smaller the squares the more of them there would be. And if it's 10 meters by 12 meters, people in Australia are much taller than I thought or perhaps just sleep in enormous Antipodean beds.
posted by XMLicious at 12:53 AM on March 24, 2014 [2 favorites]

It's clearly 10 squares by 12 squares for 120 squares of indeterminate size.
posted by Justinian at 12:57 AM on March 24, 2014 [4 favorites]

I think the technical term for what she is looking for is aperiodic tiling. Maybe that might lead her down the right path?
posted by arcolz at 4:43 AM on March 24, 2014

Four color theorem is close to what you're looking for, though it will let you put the same color across a diagonal.
posted by Garm at 6:19 AM on March 24, 2014 [1 favorite]

Rule #1 immediately leads to having no less than nine colors, assuming a rectangular grid wherein each cell has eight neighbors. A hexagonal grid (which would be unusual for quilts) would require seven colors. And that's without considering rules #2 and #3.

I'm pretty sure you're going to need a lot of colors.
posted by adipocere at 6:32 AM on March 24, 2014

You have 120 squares and 110 pairs of squares that must be unique (you also have a smaller number of pairs that must be unique in a different direction). This means, unless I'm nuts, that you need at least 11 colors.

Given your other requirements, I doubt 11 colors will do it, but that's a minimum.
posted by It's Never Lurgi at 7:13 AM on March 24, 2014

Here's a proof that you need at least 11 colors. On a 10x12 quilt, there are 110 pairs of adjacent up/down squares. By rule #3 they must all be distinct combinations. If you have N colors and no pair can have 2 of the same color, you can only fill in N x (N-1) distinct combinations, so N has to be at least 11.

I feel like you probably need more but have no idea how to get there. This is a really interesting problem though.
posted by leopard at 7:18 AM on March 24, 2014

Since I'm teaching graph theory this semester, the mathematical approach is to make a graph with 110 vertices (little circles, say), one for each square (might as well go ahead and arrange them in an 11 x 10 grid). Then connect pairs of vertices with an edge precisely when the pair of corresponding squares is not allowed to be the same color. This will take care of constraints (1) and (3).

So, for example, the upper-left corner vertex is connected with edges to all the adjacent vertices to its left, diagonally down, and below, along with some other vertices in row three (which I wasn't totally clear about). So you draw in all these edges (connect the little circles with line segments). There will be a lot if them. Rule (3) means that for example you would need an edge between a vertetx and the one that was two rows down and one over, for all vertices. (Or something. This seems overly constraining. If you really can't have any possible pair repeated anywhere in the array, seems like you'd need to have the upper left vertex connected to all the others, so you'd need 110 different colors. So probably don't want that much constraint. Maybe restrict to maybe a "corona" of three away from a given square?)

Then you need to determine the chromatic number of the graph, which is the fewest number of colors needed to color the vertices so that vertices connected with an edge are different colors.

Now, determining the chromatic number of a graph is hard, but there are some algorithms. One algorithm that is easy to apply (although it can fail spectacularly by ending up saying you need too many colors) is the "greedy algorithm", which says you choose a vertex, assign a color, say red, and then move to the next vertex (works better if you choose one that's connected to it by an edge) and color it red if you can, green if you can't. (If it's connected to an edge to the red one, you can't, so color the second vertex green.).

Keep going, coloring vertices, using colors you've previously used whenever possible (that is, resist introducing a new color until you have no choice).

Once you're done, you at least have a coloring that respects the constraints, and you can use the coloring to color the squares, besides.

Now, this doesn't deal with constraint (2). To deal with pairs of squares whose pair-colors can't repeat, you could maybe make a new graph, with one vertex representing each pair of squares whose color-patterns aren't supposed to repeat or something...I'd have to think about it more carefully, but that constraint I think would be a pain to implement.

(By the way, true randomness of color assignment would allow adjacent squares to have the same color, etc., just like true randomness of coin flips allows the (not very likely) possibility of strings of arbitrary length of H and T).

So another approach is to choose some number (9?) of colors and get someone to generate a random strings of integers using 1 through 9 of length 110 and use that for your assignment. (Wolfram alpha can do this, for example).
posted by leahwrenn at 8:20 AM on March 24, 2014 [3 favorites]

You have many math based answers here, all good. But there may be a color-based approach needed here as well. When you are talking about 11 different colors, it can be hard to get colors that are different enough from each other to look random. It seems easy to think of 11 different colors until you have to translate them into fabrics. Suddenly that difference between light blue and grey is barely noticeable or the red, green or pink sticks out so much more than the others. This can be especially difficult when working with solid colors. To combat this, there are pieces of red and green translucent plastic that quilters use to find the shades of fabrics without regard to their color. Here is an example of how they are used.

Six inches might be a bit large, but they do sell pre-cut squares many places. This would be a quick way to get lots of different fabrics if they offer variety packs.
posted by soelo at 10:14 AM on March 24, 2014

In Rule #3, the maximum size where you have to be concerned about a "line" being formed by three points (squares), is at 9 by 11, such that you have a square in the lower left (1,1), then another square of the same color at (5, 6), then the third square of the same color at (9, 11).
posted by adipocere at 10:24 AM on March 24, 2014

The Costas array may be the most relevant mathematical object. I'm suspecting that this problem is very hard.
posted by leopard at 11:03 AM on March 24, 2014

I went ahead and wrote a quick python script to brute-force this problem. It starts at the top-left corner and proceeds left across each row. On each tile, it starts with color #1 and increments until it finds one that meets your given criteria. Proceeding in this fashion, there are only up to four nearest neighbors to check against which have been drawn already. It also maintains a collection of existing offsets between color pairs (including between a color and itself, making rule #3 a special case of #2).

Per leahwrenn's remark, this might not be the optimal solution and might use more colors than are actually required. Its solution uses 58:

01 02 01 03 02 04 01 05 03 06
03 04 05 06 01 07 08 02 09 10
02 11 12 13 14 03 15 16 04 11
05 08 09 06 17 01 18 05 19 07
07 10 20 21 22 23 24 25 02 12
13 03 14 26 27 28 29 30 09 13
04 12 15 08 11 16 31 06 32 33
18 17 34 35 36 37 38 01 04 10
19 02 05 39 40 41 42 20 43 14
22 07 44 45 46 47 21 03 48 49
10 23 50 24 51 52 53 54 26 25
29 06 49 55 56 57 58 12 18 15

posted by 7segment at 12:35 PM on March 24, 2014 [5 favorites]

I've kept working on this a little. My algorithm is provably non-optimal, at least for the simplified case of a 3x3 grid. It produces

01 02 01
03 04 05
01 06 02

which uses six colors. The problem is solvable by

01 02 01
03 04 05
05 01 03

which uses only five.

The lower-left tile is the seventh that my algorithm hits, and it chooses 01 since that's the first color index it tries that meets the criteria. It does so without foresight of that this decision forces the next square to be 06. Similarly, it finds for the 3x2 case

01 02 01
03 04 05

instead of

01 02 03
03 04 01

by a similar lack of foresight as of the third tile it assigns, at the top-right.

The next-least-dumb thing it could do would be to try tiles in a random order instead of the raster pattern described. I've coded this and will update the gist accordingly. It seems to come up with solutions requiring only 47-50 unique colors for the 10x12 grid. It takes around two minutes per run on my machine, so I'll try a batch overnight and see if it produces anything notably better than that.
posted by 7segment at 9:28 PM on March 24, 2014

I'm not clear on rule 2 or rule 3. Does rule 2 govern only directly adjacent squares, or does it forbid any parallelogram ABCD where A, B are both (say) red and C, D are both yellow? Does rule 3 only say that there can't be three squares A, B, C of a single color such that B is the midpoint of AC, or does rule 3 also forbid parallelograms of a single color?

Assuming that parallelograms like the two-red-two-yellow example from above are permitted, I think this is a valid 21-color solution:

  1   2   3   4   5   6   7   1   3   7
  3   5   1   6   1   4   2   4   6   5
 15  16  17  18  19  20  21  15  17  21
  2   6   4   7   5   3   1   5   2   1
  8   9  10  11  12  13  14   8  10  14
 10  12   8  13   8  11   9  11  13  12
 17  19  15  20  15  18  16  18  20  19
  2   7   3   6   2   5   4   1   7   4
  9  13  11  14  12  10   8  12   9   8
 16  20  18  21  19  17  15  19  16  15
  9  14  10  13   9  12  11   8  14  11
 16  21  17  20  16  19  18  15  21  18

Valid, but not in the spirit of the question. Being human-generated, it has all sorts of features that are the antithesis of random. For example, to make life easy, I divided the 12 rows into three "non-interacting" sets of four, using only colors 1-7 in the first of these sets, only colors 8-14 in the second set, and only colors 15-21 in the third set. I also recycled patterns wherever I could get away with it and not break the rules.

You could try to change the rules to better capture the visual randomness you want. However, more rules really produce more determinism, not more randomness! Aiming to minimize the number of colors only exacerbates the problem: if there is a solution with "unexpectedly" few colors, it probably has some orderly features. Thus I suspect (much as leahwrenn already remarked) that you should take the opposite approach, i.e. choose your colors* and then use actual random numbers with relatively few constraints. How does your quilt look if you only enforce rule 1?

* Minor correction to adipocere: You don't need 9 colors to satisfy rule 1. Just 4 colors are enough, though not if you want a random-looking pattern.
posted by aws17576 at 12:08 AM on March 25, 2014 [1 favorite]