Thursday, June 30, 2011

The Pseudo-Random Quilt Block Distribution Problem

After cutting up my 10 colors of Quilter's Tweed (very carefully, with no room for error, in order to get the most out of the fabric), I found myself with a problem that I've encountered more than once in my not-so-terribly-long quilting career. Since it's such an interesting fabric, I'm going with a very simple quilt design--rectangular blocks sewn in columns, half-offset. I don't want to go with a constantly repeating order of colors; rather I want them randomly scattered across the quilt.

Except, of course, I don't really want a random pattern.

I first encountered this problem a couple of years ago with my best-friend-from-high-school's wedding quilt:

I can't believe I didn't take better pictures of it.

It's a double wedding ring that I put together from a quilt kit I bought, because I wasn't confident enough to try cutting all those teeny curved pieces myself. If you look closely in this picture, you can see that the fabrics in the kit were, in more than one instance, the same fabric but in a different color.

I wanted the 24 fabrics in the pieced arcs to be random--except, of course, I didn't ever want the same fabric next to itself, and while the same pattern but different colors next to each other was OK, I didn't want that to happen too often. And I didn't want the one color of fabric to another fabric of a very similar color too often. So it really wasn't random at all, with all those rules, and it became rather difficult.

After I finished the top, I mentioned the problem to a crocheter friend who was, at the time, working on a baby blanket made up of log cabin-patterned granny squares that used four different colors. She realized she was going to face the same problem when she was ready to put them together, and we started talking about the fact that there really ought to be a computer program that could tell you what block you should put where.

Unfortunately, once you start thinking about how to codify the rules, you realize that this is actually a much more difficult problem than it at first appears. Things like "these fabrics should sometimes but not often be next to each other" and patterns like a double wedding ring which doesn't fit nicely into a computer grid are actually really hard to deal with. Nevertheless, since my friend is a much better computer programmer than I am, she managed to write a simple program that can handle a rectangular grid and minimum separation distances. (At the moment, it's not stand-alone software, so unfortunately if I were to share it with you at this point you'd still need the programming language software. Someday, though...)

At the moment, you set up a grid of allowable distances between each different block (in this case, color of Quilter's Tweed) and tell the program how many of each block you have.

You give it the size of the quilt grid into which to put the blocks, and the program goes through the grid methodically, selecting a random block and then checking to see whether or not it meets the distance requirements. If not, it selects a different one; if it can't find one that will fit, it starts backtracking.

As you might imagine, this ends up being rather, as they say in the programming world, "computationally intensive." For my Quilter's Tweed quilt, I said that at least one other block had to separate the same color. With 10 colors, the program managed to spit out a grid in a minute or so. Then, I thought I'd change it to two blocks separating identical colors--and after 3 hours, it was still running (at which point I either accidentally quit, or the software crashed). It also took about 3 hours to find a layout for my friend's baby blanket--so we would like to find a way to do this whole thing more efficiently, in addition to adding a bunch of other features that might make it more versatile.

In the meantime, though, I'm going with one of the grids that the program did spit out.

Every other column will be half-offset.

I'm eager to see if the final quilt will show the desired effect!

1 comment:

  1. WOW....that is impressive!!! Cant wait to see the finished product!!!