Observations on Solving a Jigsaw Puzzle
Table of Contents
A. Mathematics
3. Paradox
5. Shapes
7. Summary
B. Vocabulary
C. Orientation
D. Psychology
E. Artificial Intelligence (AI)
F. Strategy
G. Conclusion
A. Mathematics
1. Ad Hoc Approach: As each random piece is affixed to the puzzle, that leaves one less piece to find. The odds of being successful with the next random piece is directly proportional to the number of pieces attached to the puzzle (or inversely proportional to the remaining random pieces).
For example, if you have a puzzle with 1500 pieces, and the border consists of 34 columns x 45 rows, then the border represents:
2·34 + 2·45 = 158 pieces
Since you have counted each corner pieces twice, you have to subtract by 4:
158 – 4 = 154 pieces
The remaining random pieces are:
1500 – 154 = 1346 pieces
If you were to use only this ad hoc approach, then it would take exactly 1346 steps to complete the puzzle. The success rate in percent with each step would go up; but, by how much?” To calculate this, I have created the following table:
Table: Ad Hoc Approach
| Pieces | Percent | ||
|---|---|---|---|
| Step | Remaining | Odds | Completed |
| 1 | 1346 | 0.000743 | 0.07% |
| 2 | 1345 | 0.000743 | 0.07% |
| 3 | 1344 | 0.000744 | 0.07% |
| … | … | … | … |
| 135 | 1212 | 0.000825 | 0.08% |
| 269 | 1128 | 0.000887 | 0.09% |
| 404 | 943 | 0.001 | 0.11% |
| 538 | 809 | 0.001 | 0.12% |
| 673 | 674 | 0.001 | 0.15% |
| 808 | 539 | 0.002 | 0.19% |
| 942 | 405 | 0.002 | 0.25% |
| 1077 | 270 | 0.004 | 0.37% |
| 1211 | 136 | 0.007 | 0.74% |
| … | … | … | … |
| 1344 | 3 | 0.333 | 33.33% |
| 1345 | 2 | 0.500 | 50.00% |
| 1346 | 1 | 1.000 | 100.00% |
Notice that relying only on the Ad Hoc Approach will have very low success (0.12%) for the first 538 steps (~40% completion = 538/1346). This stays quite low until you approach the end of the process: step 1344 has a success rate of 33.33%. This is reflected in the graph where you see an asymptote until the graph climbs rapidly at the end.
2. Edge Calculations: If you concentrate only on the edge of a random piece, what are the odds that the next piece that you pick up will match one of the edge pieces? Let us assume that you have a regularly cut puzzle where each piece has four edges. Then the odds are related to the number of edges on the random piece matched against the number of edges exposed at the border:
The number of edges on a random piece:
1 x 4 = 4 edges
The number of edges on the border:
1 · 154 = 154 edges
Since the corner pieces have no exposed edge, you subtract by 4:
154 – 4 = 150 edges
Therefore the odds of matching this random piece is:
4:150 = 0.0267 or 2.67%
Empirically, I noticed that when I am about half-way through the puzzle, using the ad hoc technique, my success rate is around 1:50, or about 2%, which is in agreement with this figure.
3. Paradox: Let us say you find a pice that matches. The number of edges actually goes up: you have covered one edge but have exposed three additional edges by placing the random piece. This is a net increase of 2 (3 – 1). Therefore, the calculated the odds for the next piece is:
4:152 = 0.0263 or 2.63%
Note: this success has dropped from 2.67% to 2.63%.
To simplify the process, imagine a puzzle that has 6 columns and 6 rows (6 x 6). I represent this theoretical puzzle using the following image:
The first step is to fill in the boarder (red squares)—easy enough. The next step is to affix random pieces concentrically that do not represent corner pieces (orange squares). Subsequently, affix a random piece on the next concentric row (green squares); then the next (blue squares), and then go back to the first concentric row and select the corners (yellow). You are left with the white squares. The step by step calculations are represented in the following table and graph:
Table: Edge Count
| Steps | Color | Edges | Odds | Success |
|---|---|---|---|---|
| 0 | Red | 16 | 0.250 | 25.00% |
| 1 | Orange | 18 | 0.222 | 22.22% |
| 2 | Orange | 20 | 0.200 | 20.00% |
| 3 | Orange | 22 | 0.182 | 18.18% |
| 4 | Orange | 24 | 0.167 | 16.67% |
| 5 | Green | 26 | 0.154 | 15.38% |
| 6 | Green | 28 | 0.143 | 14.29% |
| 7 | Blue | 26 | 0.154 | 15.38% |
| 8 | Blue | 24 | 0.167 | 16.67% |
| 9 | Yellow | 22 | 0.182 | 18.18% |
| 10 | Yellow | 20 | 0.200 | 20.00% |
| 11 | Yellow | 18 | 0.222 | 22.22% |
| 12 | Yellow | 16 | 0.250 | 25.00% |
| 13 | White | 16 | 0.250 | 25.00% |
| 14 | White | 12 | 0.333 | 33.33% |
| 15 | White | 8 | 0.500 | 50.00% |
| 16 | White | 4 | 1.000 | 100.00% |
Notice that at first the puzzle gets harder as the success rate in percent goes down (from red to orange to green in the table). Then the success rate rises at step 7 (in blue). This is reflected in the graph which matches the graph taken from the Ad Hoc Approach (see above).
4. Colors & Patterns: The above argument appears counter intuitive that the puzzle should get harder before it gets easier. This would be true if affixing random pieces to the puzzle by edge alone were all that was needed. However, edges are not the only variable. Each puzzle piece has a color and pattern. These random pieces can be grouped into populations. As the population in each group diminishes, so too does the number of locations on the fixed puzzle. The above principles apply.
5. Shapes: Now suppose you separate the random pieces into six groups:
Table: Shapes
| Group | Heads | Sockets | Type | Pieces | Percent |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 94 | 7% | |
| 2 | 1 | 3 | 390 | 29% | |
| 3 | 2 | 2 | Opposite | 390 | 29% |
| 4 | 2 | 2 | Left-sided | 94 | 7% |
| 5 | 2 | 2 | Right-sided | 94 | 7% |
| 6 | 3 | 1 | 190 | 14% | |
| 7 | 4 | 0 | 94 | 7% | |
| Total | 1346 |
Let us assume that we divide our 1346 random puzzle pieces into 7 groups according to the table above. Then at random the chance of finding an edge piece to match in group 1 would be 94:1346 or 6.98%. Already this exceeds the success rate of 0.07% presented in the table under step1 of the Ad Hoc Approach.
6. Empirical Counting: We decided to construct a regularly cut puzzle with 1500 pieces. The puzzle was a diagram of the Cosmos. It took us approximately 8 days and took approximately 48 hours. During this time I took 14 photographs to document the progress. Therefore, each image represents an interval of approximately 3.5 hours. I counted the number of affixed pieces of each image and created the following table and graph:
Table: Empirical Counting
| Steps | Pieces | Ratio | Percent |
|---|---|---|---|
| 1 | 154 | 0.103 | 10.27% |
| 2 | 282 | 0.188 | 18.80% |
| 3 | 364 | 0.243 | 24.27% |
| 4 | 697 | 0.465 | 46.47% |
| 5 | 771 | 0.514 | 51.40% |
| 6 | 927 | 0.618 | 61.80% |
| 7 | 975 | 0.650 | 65.00% |
| 8 | 1136 | 0.757 | 75.73% |
| 9 | 1315 | 0.877 | 87.67% |
| 10 | 1403 | 0.935 | 93.53% |
| 11 | 1459 | 0.973 | 97.27% |
| 12 | 1488 | 0.992 | 99.20% |
| 13 | 1499 | 0.999 | 99.93% |
| 14 | 1500 | 1.000 | 100.00% |
Notice: Compare this graph to the Ad Hoc Approach and the Edge Counting. This curve rises much more quickly. This is because we are taking advantage of the colors and patterns in the puzzle: in particular, the ring shape grows more rapidly than any other area.
1500 pieces in 48 hours; 8 days: Full resolution
7. Summary: Given the above data, you may consider the following strategy.
(a) First, place all the edge pieces to frame the puzzle (almost everyone does this).
(b) Use the color and pattern technique to place pieces into groups. Amy usually uses the Match Approach, using the poster to match random pieces to the precise location on the fixed puzzle. This creates multiple islands of puzzles inside the fixed puzzle. Eventually, the islands give way to attach to form multiple peninsulas.
(c) As you complete about 40% of the puzzle, you can switch to the Ad Hoc Approach in which random pieces can be affixed to the fixed puzzle. Your success rate climbs rapidly at this point.
B. Vocabulary
1. Very few of us grow up naming the parts or shapes of puzzle pieces. If you were to learn a new language, does the professor start by saying, “These are the names of puzzle pieces …” When I land in Amsterdam, getting to my hotel room may be puzzling to me, but I am not communicating to the taxi driver the names of puzzle pieces.
2. If you work with a team to complete a puzzle, then it is useful to come up with names for puzzle pieces. The names that I coin may not be thee same as those chosen by you. If I tell my partner “I am looking for ‘elephant ears’ ” she may look at me with a funny face.
3. In the image above, I have given names to many puzzle parts: Head, Socket, and Shoulder. You shall notice that these pieces are relatively symmetric and have no color or pattern. Once you consider colors and patterns, then you can give additional names to these patterns. I organize groups according to the colors of the rainbow: red, orange, yellow, green, blue indigo and violet (ROYGBIV).
4. I went to nautiluspuzzles.com and made note of their names for puzzle pieces:
• Tabs or Knobs (what I call Heads): These are the parts that stick out, rounded, curved, or sometimes whimsically shaped extensions that connect with other pieces.
• Blanks or Sockets: The inverse of tabs, these are the indentations or holes into which tabs slide.
• Edges: Pieces with a flat edge define the boundary of the puzzle. These are your anchor pieces, the first many puzzlers seek.
• Corners: The VIPs of edge pieces. With two flat sides, they mark the true beginning or satisfying end of any puzzling journey.
• False Edges: Tricky pieces with one straight edge that don't actually belong on the outer border, added for challenge and misdirection in advanced puzzles.
C. Orientation
• Very often a regular puzzle is cut with a die that leaves a certain orientation. You will notice that some rows are tall while others are rather squat in height. This is very useful. Of course, if there is printed pattern, then this improves the orientation.
• Asymmetry is your friend. When you find that one piece in a thousand that has that weird shape, you know exactly where it goes: at least you have narrowed it down considerably. Asymmetry defines orientation on its own, since the matching fixed piece is oriented only in one direction.
• Irregularly-irregular cut puzzles. These are very difficult. Throw away the math! Perhaps re-gift it!
D. Psychology
• If I receive a puzzle with more than 1000 pieces, or where the background is all one color. I know instinctively that this one is going to be difficult. It usually sits on the shelf for months. I am thinking to define how crazy I must be to even attempt to solve this puzzle. I also know that I will block off over a week of my time, and need to schedule accordingly. If I have a team member, are they willing to help or just say “Hasta la vista, baby!”
• At the beginning of the puzzle there is enthusiasm. The border is the easy part. After 20 minutes, it is all famed in. You marvel at your accomplishment. Then you realize, the hard part begins. Let’s call it a day!
• There are times I can’t go to sleep because I am thinking about the puzzle: that piece with that shape, that asymmetry, that color! I know where it goes! Or do I? I got to get up and find out!
• I find a piece that I cannot solve. I push it to the other side when my team-mate is not looking and pretend that it is hers, and she will think that piece was meant for her!
• You have been working on the puzzle for hours, or even days. You daughter comes over for a visit. She takes one look at the puzzle, walks over, picks up a random piece and places it right where it belongs. Then she looks smug as if to say, “So what is so hard?” Then I want to say, “Okay, smarty—finish the rest of it!”
• When you finish, nobody understands how much effort this took. All you did was a puzzle; but you want people to think you actually painted that thing! You want to show it to everyone—but deep down inside they couldn’t care less. So jubilation quickly turns to angst,
• When is it time to do another puzzle? Right away while your trained brain is agile. Perhaps you should give it a rest. I have another puzzle sitting on the shelf. I wake up the next day thinking of puzzles. Oh no! I am a puzzle addict.
E. Artificial Intelligence (AI)
1. Everyone is talking about AI. There are data centers with billions of dollars of investment, using up to 15% of our energy and significant amounts of our precious water. Should I use AI to solve a puzzle?
2. I decided to ask AI this question: “Can AI solve a jigsaw puzzle?” This is the answer:
Yes, AI can solve jigsaw puzzles by using image processing and machine learning techniques to identify, sort, and assemble the pieces based on their shapes and colors. Various projects and algorithms have been developed to automate this process effectively. (Source: GitHub)
Table: Key Steps in AI Puzzle Solving
| Step | Description |
|---|---|
| Image Processing | The AI processes the puzzle image to detect individual pieces using techniques like edge detection and contour identification. |
| Piece Sorting | It sorts pieces based on their shape, identifying edges and corners using machine learning models. |
| Piece Orientation | The AI determines the correct orientation of each piece by comparing edges and colors. |
| Puzzle Completion | Finally, it assembles the pieces in the correct order to complete the puzzle. |
3. AI Methodology
• Brute Force: AI can use brute force to try out different combinations of solutions until it finds the correct one.
• Heuristics: AI can use heuristics, which are rules-based methods that help guide the search for a solution.
• Machine Learning: AI can use machine learning techniques, such as neural networks and decision trees, to learn from data and improve its puzzle-solving abilities.
4. It took Amy and I working about 6 hours a day for 8 days to solve this 1500 piece puzzle. That is a total of 48 hours. When I questioned AI how long this would take AI to do it, the answer was 11-18 hours. Taking the average of 14.5 hours, then this is about 30.2% of the time it takes two humans. The difference is that AI does not lose any sleep over it!
5. Something tells me that if I had AI do it, I would still need to scan all the pieces, which would probably take hours of human effort. So much for efficiency!
F. Strategy
• Start with the border.
• Separate the pieces into colors.
• Separate the pieces into shapes.
• Take a single “random” piece and match it sequentially against the fixed puzzle piece. This can be done with or without the poster image that is often included with the puzzle. I call this the “Match Approach.” (Amy’s technique)
• Take a single “random” piece and match it sequentially against the fixed puzzle, moving from row to row and column to column, covering the entire puzzle. I call this an “ad-hoc” approach.. (Kevin’s technique)
• Take groups of similar colors or similar patterns and create a mini-puzzle: a puzzle inside a puzzle. When completed, these float inside the fixed puzzle like “islands.” I call this the “island” approach.
G. Conclusion
Think about these topics the next time someone gifts you a puzzle of that quilt, or painting from the 1800s, or that astrological view from one of the satellite telescopes!