A Puzzling Year

Ever since I can remember I've enjoyed putting together jigsaw puzzles. Even as an adult it's a fun diversion for me; of course there have been lots of opportunities to do simple ones with the kids over the years. Every once in a while, since we've been married, Shelly and I would get out one of the tougher ones and do it together - ones with 3000 pieces, or unusual shapes, or other challenges. Each is different, to some degree unique: dominant colors may greatly help find the right piece with one puzzle, while textures, element size and focus help with another, or sometimes you just have to go by piece shape.

Sometimes there are patterns that you can discern after a time, whether forced or just a whim of the maker. Many of these elements of puzzling became reinforced in my mind this past year as we worked on our greatest challenge yet - an 18,000-piece puzzle (separated into 4 4500-piece sections) which Shelly gave me last Christmas (it was on sale!) With some substantial breaks in between sections, it basically took us all year. The last quarter was the easiest (done in just 3 weeks), with the experience gained from doing the earlier sections - it also ended up having a slightly simpler pattern than the others.

Part of the reason for my interest in putting together puzzles is their similarity to the way I think about science. Just as with a jigsaw puzzle, scientific discoveries fit together with one another to make a coherent whole. There are often gaps, sometimes quite large, in regions where research effort has so far been limited, or especially challenging. Sometimes an initial research effort in one of these big gaps puts in a "piece" that turns out to be wrong, and has to be taken out again later, replaced by a piece that fits better, representing greater understanding. Just as with a jigsaw puzzle, individual pieces may not seem to represent anything important, but put them into the larger context and the barely statistically significant result in its own context becomes a well-defined piece of something much larger. A puzzle piece of blurry gray fading into green on its own can become the sharp edge of a black-furred animal against a leafy backdrop when placed in the full puzzle context.

And with science, as with a puzzle, the individual experience of learning and fitting things together for yourself, of understanding the patterns for the first time, is very different from just looking at the beauty of the final result. Outsiders can to some degree appreciate what they see in the outcome. But it is very hard for them to understand the degree to which reality forces the result, how the pieces really could only fit together this one way, to have an intuitive feel for when pieces fit well and when the fit is poor or just clearly wrong. You need to put in the effort - years of study and practice in the case of modern physical sciences - to be able to fully appreciate what science tells us, and to be able to add to that body yourself in meaningful ways. A dilettante can come along and appear to add a piece that seems to fit, but most probably it will just not fit quite right, color or texture will be slightly off, or perhaps it will break some fundamental underlying pattern that the experienced puzzler or scientist can see at once. Much of this is intuition that can be rather hard to explain verbally, but experience really does matter in these things.

But I'm going to try here to explain anyway, at least a little bit, how we went about doing this particular very large puzzle, and some of the patterns discovered on the way. With jigsaw puzzles (as with established science when new people learn it) we usually can see the big picture first, from the image that came with the box - here's what the completed sections looked like:

puzzle4_done.jpg puzzle1_done.jpg
puzzle3_done.jpg puzzle2_done.jpg

The first thing to note is the dominant colors and textures. For the human eye red naturally jumps out, but it's only a minor element except for the top right section with red parrot coloring. The left sections are dominated by green leafiness, while whites and browns of rocks and water are the main elements on the right. Each section has a collection of brown/purple/whitish tree trunk sections with distinctive textures. There are small concentrated red/pink/purple areas in the left sections, and similar concentrations of purple (and a bit of red) in the bottom right. The yellow/black of the jaguar in the bottom left section is distinctive, as are the smaller colored areas for animals in the other sections. And there are the broad pure untextured green border areas, with wide borders along the outer two edges of each section (which is where the only flat-sided pieces are located) and narrower borders on the inner edges where they would meet up with another section (these turn out to have a simple alternating "knob"-"hole" pattern presumably so the sections can be more easily joined at the end).

Part of the logic of puzzling is realizing that you are (usually) trying to turn an Order(N^2) problem into an Order(N) problem. That is, you could in principle do a puzzle just by trying out every piece next to every other piece, or scanning through all the remaining pieces to find the next one to fit in, which would take an effort of size (N) for each piece you put in (N pieces). With 20 pieces, that's not a bad strategy - you'd need to do maybe 200 comparisons (1/2 N^2) to put it all together. With 200 pieces that's 20,000 comparisons though, and with 2000 pieces you're up to 2 million comparisons, 10,000 times harder than the 20-piece case. Ideally you want to make the 2000-piece puzzle no more than about 100 times harder than the 20-piece puzzle. If you can't get something close to Order(N) scaling in puzzling, 4500-piece puzzles like these would be beyond human capabilities to solve.

Just as with science (and software development!), there's an extremely general approach that helps make solving things simpler: partition the problem into smaller chunks that can be done by themselves, and then fit together later. If you can cleanly partition N pieces into, say, 5 roughly equal-sized chunks, then you've gone from one problem of size N to 5 problems of size (N/5), plus the one added step of fitting the 5 chunks together later. If the time taken for splitting is b * N and the time taken for joining at the end is c, that means for order(N^2) problems, you've gone from a time a * N^2 to a time b * N + 5 * a * (N/5)^2 + c which should be just a bit more than a * N^2/5. Partitioning (if it's a good, clear, usable partitioning) saves you a factor of close to 5 immediately, in this example.

But you can go further, splitting each of these partitions into even more do-able sub-components. Sometimes that's not possible, but the farther you can take this, using whatever discriminatory elements you can (color, shape, texture, particular elements like edges or lines that cross many pieces) the faster things will go. For the top left puzzle section in this case I came up with the following initial split of the pieces:
* pure border-green (later split into side and inner pieces, and further split by shapes characteristic of each side)
* partly border-green/partly main puzzle colors
* red, pink, purple (various flowers and the toucan beak)
* orange (the orangutans)
* brown with running-water texture (the river at bottom)
* patterned yellow (the snake in the upper left)
* white and off-white (with small amounts of green or other elements)
* leaf green (later split into 3 characteristic textures)
* purple and gray tree trunk (later split into specific color and textures characteristic of specific trees)

Similar partitions, specific to their characteristic colors and textures, worked quite well for the other puzzle sections.

It's a common practice in puzzling to do the outer border first, the flat-sided pieces that are easy to find and give yourself a nice overall frame to work within. That proved essentially impossible with this puzzle - the border-green side pieces could fit together in too many different ways on their own. You actually needed the inner pieces as well - preferably at least three pieces connected to any given one - to know whether you had a good fit or not. So we mostly left the side pieces for last in this puzzle, and did several of the inner groupings first. The partly border/partly main puzzle pieces did provide a rough frame, though that often proved tricky to put together itself without more of the inner sections worked out, since those pieces could also go together several different ways if the non-border colors in the pieces were not distinctive enough. We often found ourselves switching some of these "inner-border" pieces around even very late in the working of a particular puzzle section, after realizing the reason we weren't able to find a matching inner piece next to one spot was because it had been swapped with another.

Aside from color, piece shape really determines where a puzzle piece goes - it has to fit into those around it. These puzzles were made of mostly regular-shaped pieces, of which there were two subtly distinct principle varieties:

elong_reg.jpg square_reg.jpg

With two knobs on opposite sides and two holes on the remaining two opposite sides, these two pieces look almost the same. The difference is in the aspect ratio. Taking away knobs and holes, for both pieces the width of the main body is about 15 to 20% greater than the height. In these puzzles, the longer dimension was always horizontal and the shorter vertical, so just by looking at these pieces they could be pretty reliably classified as to whether their knobs were horizontal ("elongated" - width 60-90% greater than height) or vertical ("square" - height 20-50% greater than width). Irregularly-shaped pieces had similar aspect-ratio considerations:

1knob_elong.jpg 3knobs_elong.jpg

The vast majority of these irregular pieces with one or three knobs in our puzzle were "elongated" like these, so the extra knobs or holes were pointed horizontally and not vertically. There were occasional exceptions, as with this pair:

1knob_3knob_sq_pair.jpg

These exceptions with vertical extra knobs and holes almost always occurred in enclosed pairs like this, so the extra knob and hole canceled one another out and the pair could be entirely surrounded by regular-shaped pieces. There were even rarer cases of pieces with 4 knobs, or no knobs, which then had to have a compensating piece on either side so they came in groups of 3 or more, rather than just 2 as in this case.

These puzzles also had many irregular pieces with two knobs and two holes but with the knobs on neighboring instead of opposite sides, as in these two examples:

2knobs_irreg_left.jpg 2knobs_irreg_right.jpg

Here we can distinguish right- and left-handed varieties, but the "elongated" vs. "square" distinction doesn't apply since no one side is preferred. As with the 3- and 1- knob pieces, these irregular pieces cannot be on their own surrounded by regular-shaped pieces, because they break the in-out pattern that would otherwise apply. There has to be a chain of irregular pieces that either crosses the entire puzzle or closes in on itself (the two-piece example above is the simplest such case). Puzzle-makers have many choices on how to resolve these irregularity "defects" within a largely regular pattern. The makers of this 18,000-piece puzzle decided on largely having chains of irregularities crossing the entire puzzle, as can be seen in the following close-up of one section of the top right section:

trsample.jpg

Starting at the left of this image we have a column of completely regular pieces, then a column of irregular pieces with hole and knob opposite and alternating down the column, then two regular columns, one irregular, two regular, then a pair of irregular columns, then two regular ones again. The single isolated irregular columns are logically constrained to be that way (they can wander off horizontally, but they cannot just end) - essentially it represents a boundary between one "elongated/square" pattern and the other one. The double irregular column is however completely superfluous - it could be terminated and taken up again at any point without disturbing the surrounding "elongated/square" pattern at all.

Also note the second irregular column here is actually of smaller width than surrounding columns. Each of the puzzle sections had a special central column of this sort, with a slight vertical offset as well to the pieces on the right. This was a particularly distinctive column to identify within the overall puzzle layout. It took quite a bit of frustration before we discovered the puzzle-maker's extensive and predictable use of these columns of irregular pieces. Since those types of pieces were a factor of 4 or so rarer than the regular ones, the discovery greatly accelerated getting major internal framing put in - as can be seen in this half-done example from the top right puzzle section:

puzzle1_halfdone.jpg

So - those are some of our secrets to getting a huge puzzle like this done in a reasonable (ha!) amount of time. Like doing science, it's impossible to explain the many "tacit" components to doing it, you really need the experience for yourself. But some of these approaches will surely help. If you choose to do a huge puzzle like this some time, well, good luck!

This site has some good tips on puzzling - discovered after we finished the 18,000 piece one, but their ideas include many techniques we use.