The Mathematics of Jigsaw Puzzles

The Mathematics of 

Jigsaw Puzzles

Scott Davidson is a jigsaw puzzle fan and has been from the days when Springbok was independent. He is also a retired computer scientist. He wrote this article about the mathematics of doing puzzles - for instance, how much harder is a 1,000 piece puzzle than a 500 piece puzzle and how well various solving techniques work. The Piece Memory section was of particular interest however there are other strategies for gaining speed too. 

While this article is extensive in itself, the math equations show examples for visual purposes. It's actually quite interesting to read the perspective of a Computer Scientist who is also a seasoned jigsaw puzzler - it's quite the combination.

We thank Scott Davidson VERY much for sharing his insight with our Readers.  Enjoy the read...

The Mathematics of Jigsaw Puzzles

©Scott Davidson

scottfrombayside@yahoo.com

@scottd687

I. Introduction

Doing jigsaw puzzles doesn’t use a lot of your thinking brain. I do them while watching TV, and I’ve done them during involved conference calls without losing track of the call one bit. Toddlers do puzzles before they can count.

But if you think more deeply about puzzles, you can come up with some interesting questions. Why are some puzzles harder than others? Certainly, the more pieces there are the greater the difficulty, but by how much? And why do some puzzles of the same piece count vary so much in difficulty? You can tear through some 1,000-piece puzzles in a few hours, but I had one of the roofs of Vienna which took weeks of struggle to complete. 

This essay tries to answer some of these questions by analyzing jigsaw puzzles mathematically. I’m going to try to come up with some objective criteria for assessing a puzzle’s difficulty. Any experienced puzzle doer can usually assess how hard a puzzle is, but I hope to give you more than a gut feeling to go on.

The math in this piece will be Algebra 1 level, so don’t fear. And I’ll write in words what the equation means.

I will cover standard puzzles of any size. I won’t cover puzzles where one has basically identical pieces to connect based on logical reasoning from the picture. Some puzzles from Buffalo Games are like this. I also won’t consider wooden puzzles with non-standard and interesting cuts, though some of the techniques described here could be used for them. I’ll also only consider interlocking puzzles, which predominate today. Puzzles without the standard frames will be considered. While the impact of edge pieces will be covered, they are not essential for this analysis.

II. Basics

A jigsaw puzzle piece in a standard puzzle has four connecting pieces. There are three possibilities for the interface to adjoining pieces: tabs (knobs), blanks (holes) or smooth or jagged borders. Edge pieces have three interfaces, corner pieces have two.  See Figure 1.

How do we put together a puzzle? Let us consider a completely naïve solver, such as a toddler. A naïve solver might start with the left bottom corner piece (though they could start with any piece.) Next, they would pick a piece at random from the store of unconnected pieces and try to connect it. (We will treat the operation of trying to connect two pieces as a basic operation, though in some cases you might need to rotate a piece to connect it.) 

If the puzzle has n pieces, the naïve solver would pick from n-1 remaining pieces the first time. On the average it will take (n-1) / 2 tries to find the right piece. So the solver would on average look through half the remaining pieces before finding a fit. This continues until there is only one piece left. The total number of tries then is

((n-1) + (n-2) + … + 1) / 2

or

(n * ((n-2)/2) + n/2) /2   (1)

This just says that you have to go through half the pieces left for each space in the puzzle in order to solve it, and that there are n-1 pieces which you have to connect. The difficulty or complexity of this is roughly of the order n2. A 1,000 piece puzzle would take 499,759 steps to solve. More than an evening’s entertainment for sure.

What does n2  complexity mean? In this case a 2,000  piece  puzzle would take 1,998,500 steps to solve, four times as much, and a 3,000 piece puzzle would take 4,498,500 9 times as much. Smaller puzzles take a lot less time. In other words, a 1,000 piece puzzle is a lot more than twice as difficult as a 500 piece puzzle (4 times as difficult) and a 2,000 piece puzzle would be 16 times as difficult. 

That’s why we can knock off small on-line puzzles in under 10 minutes, while a 1,000 piece puzzle takes many hours. We’re assuming everything about the puzzle except the number of pieces is the same. We’ll get into what makes some puzzles harder than others later.

I did a small experiment on the relationship of puzzle size to time needed. A puzzle website has a collection of online puzzles to do, based on the boxes of puzzles they are selling. I chose one I had already done (both online and in the real) and did it at their three levels of difficulty: 12 pieces, 35 pieces and 99 pieces. Here are the results

12 pieces: 17.3 seconds.

 35 pieces: 88 seconds.

99 pieces: 6 min. 16 seconds (376 seconds.)

Tripling the size resulted in doing the puzzle in five times the time. I used some of the tricks described below, such as doing the edge pieces first and sorting by color, which reduced the time in all cases. 

None but a small child would do a puzzle this brute force way, which is why puzzles for small children have only a few pieces. We use a set of tricks and heuristics to cut down our choices and simplify our solving. The next section talks about edge pieces. The section after that will consider how the shape of pieces affects solving, the one after that will describe how colors and patterns affect solving.

III Edge Pieces

Say we have an =ℎ∗ puzzle. For instance, a 1,000 piece puzzle could be 25 x 40. In this case there are 126 edge pieces. We should not double count corner pieces – there are 80 horizontal edge pieces with 2 * 23 = 46 vertical ones left over. 

By the way, a 1,000 piece puzzle usually contains more than a thousand pieces. The ratio in this example would yield a puzzle not suited to most pictures. Puzzles have heights and widths more closely matched and are thus over 1,000 pieces. This bonus for the solver has no impact on our discussion. 25 by 40 is a convenient height and width for our example.

In the simplistic analysis above, after the initial corner piece there are 999 pieces to consider. In an actual analysis, there are 123 pieces to consider – 126 edge pieces less the three remaining corner pieces which cannot connect to another corner piece. The situation is even better than this when shapes are considered. Assuming all pieces are rotated so the edge is on the bottom, and that all edge pieces use tabs and blanks only, there will be approximately 50% tabs (blanks) if the right bottom interface of the corner piece is a blank (tab). To connect each subsequent piece, only half the remaining edge pieces need to be considered. 

If  e= ℎ∗ w−4 (the number of edge pieces) we can express the complexity of solving the border as

(e * ((e-1)/2) + e/2) / 4   (2)

Equation 2 is almost the same as equation 1, except we divide by a further factor of two to account for filtering by tabs and blanks. To compute the base complexity of solving the rest of the puzzle in a naïve way we just substitute (n-e) for n in equation 1. Since equation 1 is the order of n2, this significantly reduces the complexity. 874 squared (the number of non-edge pieces) is a lot less than 1,000 squared.

Why do we subtract 4 in the equation for the number of edge pieces? Because an edge piece is a part of both the horizontal and vertical borders, and so would be counted twice if we just used h * w. Subtracting four makes sure they are only counted once. Equation 2 looks complicated, but it just says that if you are working on edge pieces you only have to look at half the pieces, and you will find a match after looking through half of those on the average, so you will find your next match after looking through about a quarter of the remaining edge pieces.

III.1 Complications

The analysis in section III works for standard grid puzzles with tabs and blanks. There is an additional assumption: a solver connecting a tab and a blank will know if the connection works. This is not always the case. If there is a distinct pattern mismatch between the pieces this won’t be an issue, but it is a contributor to the difficulty of some puzzles as will be described below.

Some puzzles with non-standard grids may have edge pieces not easily identified as edge pieces, and some might have internal pieces with straight borders which will lead the solver to consider more than e pieces while solving the edge. 

These factors depend strongly on the design of a puzzle and won’t be considered here.

Should you work on the edge pieces first?

Extracting and connecting edge pieces is the standard first step in doing most puzzles, but some experienced solvers will start somewhere else for certain types of puzzles.

This involves colors, which will be considered in the next section. However, consider a puzzle with a border which is all white, and several internal regions of specific colors, such as a large bright red barn. There may be fewer possibilities to consider in constructing this barn portion than in doing the edge, and as we will see in the next section piece shapes may allow significant filtering for internal pieces, more so than for edge pieces.

Another factor is certainty of making a good connection. If the white border described above has many similar tab and blank shapes, a solver can easily make a mistake. In this case it is often a good strategy to wait until internal pieces next to all or some of the border are placed, which makes mistakes less likely.

There is a psychological factor also. Doing borders can be taxing in the situations described above. Sometimes having a big chunk of the puzzle completed quickly can inspire the solver to keep solving.

Here is an example from my current puzzle, a 3,000 piece Star Trek puzzle. There are lots of edge pieces, and almost all of them are black

Notice that there are only a few edge pieces. Now, the pieces connected to the edge pieces within the puzzle have a border between the black rim of the puzzle and the colors of the inside of the puzzle.

So my next step is going to be to hook up as many of these as I can, and then connect edge pieces together and hang them off the inner rim. Since I’ll be connecting several pieces at once, there is less chance of making mistakes. 

I’m not sure this way is faster than doing the edge pieces first, but it is more satisfying to me. And since my wife can see my progress, she is more willing to let me clutter up the living room with this puzzle.

IV. The Piece Shape Heuristic

For this discussion, assume that the solver has completed the frame and is proceeding to solve the puzzle starting from the lower left empty place and proceeding across to fill in the next w -3 pieces, in other words, all the pieces in a row except the edges and the piece just placed. She reaches the end and starts with the new lower left place and continues to complete another w -3 pieces. This is done h -2 times.  Remember h is the number of pieces in a column and w is the number of pieces in a row.

If the pieces are picked randomly, the jth internal piece to be filled in must be tried up to  n  – (e+ j−1) times, since e+j −1pieces have already been placed. On average (n– (e+j−1))/2 pieces must be tried, in other words, half of the remaining pieces.

As in the end piece discussion, however, we can filter pieces based on their shape. For the first w -3 pieces in a row, there are two adjoining pieces already completed. (See Figure 2). Assuming an even distribution of tabs and blanks, only ¼ of the pieces will have the proper combination, assuming the piece can be oriented in space based on its pattern. This gives ( n– (e+j−1))/8pieces on average to try. (This can be higher if there is no special orientation, for instance in an area of pure color.) So, in Figure 2 we only need to consider pieces with a tab on the left and a blank on the bottom, not the three other possibilities: two tabs, two blanks or a blank on the left and tab on the bottom.

The final piece in the row is more constrained, with three adjoining pieces already placed, and so there are only 

 ( n– (e+j−1))/16

choices. This is because only 1/8 of the possible pieces need to be considered. I won’t list all of them, but you can see that one of the two possible choices (blank or tab) are valid on the left, one of two are valid on the bottom and one of two are valid on the right, or ½ * ½ * ½ = 1/8. 

This is true for the first h -3 rows placed. The final row placed, just below the top border, has 3 adjoining pieces already placed, and so there are only (n – (e+j−1))/16 choices left. For the final piece, j = n – e -1, so there are no choices left.

This analysis holds no matter which direction the puzzle is done in. It still works if this order is not followed. Say that instead of building to the right in a row a solver chooses to build up after the first two pieces in the row are placed. (See Figure 3). The piece in the created gap is easier to place, having 3 adjoining pieces already placed, thus filtering the choices by a factor of 8. However,  the choices for the piece to the right of the space were only filtered by a factor of 2, not 4.

In fact, the row method is more efficient. Say you are placing 20 pieces inside a larger puzzle. Also say there are 64 pieces remaining when you start. In the row method, each of the 20 pieces you place gets filtered by a factor of 4, so you have

64/4 + 63/4 + … + 45/4 = 272.5 pieces to look at, worst case. (On the average we’d divide this by 2.) 

In the other case you’d start with 64/2 possible choices for the piece to create the gap, then place the next in the gap for 63/8, then 62/2, 61/8, etc. Summing, we get 342.5 tries in the worst case, substantially more.

So why don’t all solvers use the row method? It is because all pieces are not created equal, nor are all patterns.

IV.1 Variations in Knobs and Blanks

Very hard puzzles have nearly identical knobs and blanks, or irregularly shaped connections which make it difficult to determine adjacent pieces without reference to colors and patterns. Regular puzzles however have a variety of knob and blank sizes (see Figure  4)  When looking for a piece to connect, the solver will reject clear mismatches, such as a small knob for a large blank. When there are many pieces left to consider, it sometimes helps to presort them by knob size or shape.

Since each puzzle is different in terms of the distribution of known shapes, it is impossible to provide a precise difficulty value, but in general the values in the discussion above can be divided by the fraction of knob or blank pieces of the type being looked for. This is usually smaller for outlier knobs or blanks, which is why it is common to not just assemble left to right, but to look for the mate for an outlier knob or edge first. An outlier knob here means a funny looking one – either very big, very small or distorted.  That is why we don’t construct puzzles strictly left to right and upwards. The filtering of pieces based on knob and blank shape can more than make up for the disadvantage of not going left to right as discussed above. 

Many solvers never worry about the details of knobs and blanks however, since it is far more common to solve based on colors and patterns. This is covered in the next section.

V. The Color and Pattern Heuristic

The first thing most solvers do after completing the frame is to sort by color or pattern. This might involve selecting one color from the box or sorting all the pieces by color. Taking all the pieces out and sorting them on a table or sorting board means that you only need to make one pass through the pieces, but it also means that you must decide which pile a piece goes into before doing the puzzle. Selecting colors from the box takes multiple passes, but lets you be flexible and reduces clutter. And it is safer if you have a puzzle piece eating dog. Which is best? It seems to me that this is purely a matter of personal preference. 

The sorting criteria varies by puzzle. Options include

·   Pure color

·   Pieces with a similar pattern

·   Pieces with a combination of a few colors

·   Pieces with a distinct feature, for example a fence

·   Pieces with writing, such as the legend on a map puzzle.

Solvers who choose a region to work on first usually choose a small one. Few solvers choose the sky when that takes up half the puzzle area.

Is this a good strategy? It is, and our analysis above tells us why. Let us consider a block of a single color first. Doing this is effectively doing a smaller puzzle, usually much smaller. Often the edges of this region have the color of interest and parts of the surrounding area. The pieces with this property are virtual edge pieces. Since the complexity of doing a puzzle is n2 doing this part will be much easier than doing the entire puzzle. This part is done faster than doing n other pieces and reduces the size and thus complexity of the remaining puzzle. Further, when attached to the frame or another completed chunk, there are areas where the number of interfaces to consider is much reduced. This can be when an “L” is created (see Figure 2) and sometimes a strip of empty pieces is created (Figure 5) which can be filled in by filtering on three already placed adjacent pieces.

Sequences of pieces with a distinguishing linear feature, such as a gate or a path, are like edge pieces. Once pieces with the feature are sorted into a pile, there are just one knob or blank to consider. These pieces might be slightly harder than edge pieces to assemble if they run diagonally in the picture, and if there are interruptions, such as people or gates, in the pattern.

Dealing with writing is still easier, since consulting the puzzle picture will give you the coordinates of any individual piece within the block of text. The beginnings and endings of lines are other clues. The only time when writing might be difficult is when almost the entire puzzle is writing, such as in a puzzle of a newspaper’s front page. In this case pictures within the page, and their borders, are easier to start with than the writing. 

When dealing with writing different font sizes and styles can help also. In the newspaper example, one might start with the larger headline before working on the text of the page.

We mentioned above that some solvers like to start with internal blocks of the puzzle instead of edge pieces. We can now understand when this makes sense. If a color block is of size smaller than the number of edge pieces, e, then constructing the block will go faster. Not only is the size reduced, but edge pieces can only be filtered on knob versus blank in one dimension, while an internal block will have many spots with two adjoining pieces, which allows better filtering. A set of edge pieces with a single color will also be harder to solve than an internal block with a useful pattern. 

Some solvers may choose to do edge pieces first out of neatness (since this defines the puzzle’s size on the solving board) or to keep from accumulating blocks of pieces not attached to the frame. This is an esthetic choice.   No one requires us to do puzzles in the most efficient way.

VI Complexities and Heuristics

In our discussion of color blocks above, we assumed just one block per color. Puzzles, however, usually have multiple blocks of the same color, such as patches of grass or multiple balloons. How do we treat them?

Since each block will have a boundary, we can treat these as one block with multiple disconnected edges. If there are two blocks, b1 and b2, one with “edge” piece count e1 and the other e2, one with internal piece count n1 and the other n2, the solver can do the e1 edge pieces first, choose an additional edge piece at random, then complete the remaining e2 pieces. After this the solving is almost identical to that of a larger block of n1 + n2 pieces, except that since we get into the more highly constrained (3 surrounding pieces placed) we can solve more rapidly. This analysis can be extended to any number of blocks of the same color. 

This also applies to the case of many very small blocks, for example lots of independently placed 4 or 5-piece balloons. The difficulty here is block clutter, which we will discuss below.

 Piece Memory

While we have developed a way of figuring out how many pieces should be tried on average, most experienced solvers will complete a puzzle using far fewer moves. There are two reasons for this.

First, most filtering is done visually, without having to try a piece. This is why single color or few color puzzles (like the classic Springbok puzzle “Little Red Riding Hood’s Hood, which is all red) are considered so difficult. Even if colors or patterns are not pre-sorted, few pieces will be removed from the puzzle box and attempted.

Most solvers do this, with differences in solving ability depending on visual acuity. A bigger differentiator is what I will call piece memory. This is the ability of some solvers to remember where a needed piece is among hundreds. 

I’m sure many non-expert solvers working with an expert solver have had the experience of searching for a piece only to have the expert reach out a hand to the middle of the piece depository and grab the wanted piece. Expert solvers have the experience of doing just this. 

My experience is that I can do this more often for “interesting” pieces, that is pieces with odd colors, patterns, or shapes. I somehow build a map of where these pieces are located and can go right to them. Even when I don’t know exactly where the piece is, I remember what it looks like and can find it right away. I also remember the probable color and shape of missing pieces, and when I come across one in the search for another piece can place it even though I was not working in that area. 

It would be interesting to study how piece memory operates. Perhaps it is like the way chess experts can memorize real board positions better than random ones.

Piece memory speeds solving in another way. What we do is to search for many pieces at once as we search through the piece repository, as opposed to one at a time. We turn our brain into a parallel processor. The more pieces you remember the faster your solving will go.

V. Putting the Pieces Together

Our analysis lets us construct an optimal solving strategy, in general. Details of the best way to solve depends on the puzzle being worked on. How fast the puzzle will be solved also depends on the piece memory of the solver and how good they are at filtering pieces to reduce the number of choices.

1. Examine the frame and color blocks. Determine if the frame is the place to begin (it has pieces differentiated by color or pattern) or if there is a single-color block or pattern easier to assemble.

2. Repeat decision for next color block. When the frame is the simplest to assemble, work on it. You might also work on a simple section of the frame or wait until assembled blocks next to the frame can be connected to individual frame pieces.

3. When working on a difficult single-color block or pieces between blocks where the pattern or color does not aid you much in placement, sort blocks by shape and look for holes in the puzzle with the smallest set of shape candidates. For example, a space in the puzzle might take a piece with two adjacent knobs. 

4. When a block is complete, check to see where that block goes in the puzzle and whether it can be connected to an already completed block. If not, check the interface between blocks. Sometimes pieces to be placed here contain two colors and can be picked out from the pool of pieces without much effort. Connecting a block to the rest of the puzzle is satisfying. It also can reveal a row of missing pieces that is constrained enough to be filled in easily.

5. You will find that as you solve the puzzle goes from islands of blocks floating in the frame to islands of space floating in the mostly solved puzzle. At this point switch from finding and connecting blocks to sorting the remaining pieces, which probably do not have distinct colors and patterns, into the block of space they might go into.  This is also a good time to find distinctive piece shapes matching those revealed as blocks are connected. If you have a small section without distinctive colors and patterns, your solving will go quickly. If you have a large section, such as a sky or bushes with random patterns, you will have more of a struggle. The Vienna rooftop puzzle I mentioned above was 90% like this. 

6. Finally, enjoy the rush you get as the final pieces are discovered and connected into the almost complete puzzle. When I finish a puzzle, I take a picture of it to save. Some keep track of completed puzzles in a list. If it is a particularly nice puzzle you could glue it into place, but I do too many, and have too little free wall space, to do this.

7. Put the pieces back into the box and start on your next puzzle project.

VI Conclusion

I hope this has given you insight into the art of jigsaw puzzles. You probably do most of the things I recommend already, and so can feel justified. I hope I have also given you some reasons to try some new methods.

But if you don’t, that’s okay too. Solving jigsaw puzzles is fun, so whatever makes your puzzling experience the most fun is the strategy to use.