Since the start of the corona crisis, solving these has probably become one of your biggest hobbies. Webshops cannot cope with the growing demand and the largest warehouse for this product, located in Missouri (USA), has reported mind-boggling revenue growth of 2000%. We are, of course, talking about jigsaw puzzles. At the moment it is almost impossible to buy a new ‘Jan van Haasteren’ puzzle and Instagram and TikTok are full of stylized pictures and videos of puzzles being solved. At first, a jigsaw puzzle seems like a fairly easy task, you can do them during other activities, and toddlers can solve them before they can count. However, mathematically speaking, there is more to them than meets the eye.
Disclaimer: for the ease of this article, the operations needed to connect the subgroups of the puzzle are not taken into account.
There are many different kinds of jigsaw puzzles around the world, starting with the four-piece puzzle you have solved as a two-year-old up to Kodak’s humongous 51,300 pieces puzzle “17 wonders from around the world”. If you can solve the first one in under 5 seconds, does that mean that you will be able to solve the latter one with a speed of 4 pieces every 5 seconds? You will understand that this is most certainly not the case. Obviously, you have to look through a far greater amount of pieces before finding the one piece you are looking for.
Suppose you are using the most basic solution approach there is: you start with one piece, which can be anyone in the box, then you look for the piece that can be connected at a specific side. If you have a puzzle with $n$ pieces, this will mean that you have to look through $n-1$ pieces. The expected amount of pieces you will have to try before finding the right one is $\frac{n-1}{2}$. Hence, to solve the complete puzzle your total number of operations is given by $$ \frac{\sum_{i = 1}^{n-1} n – i }{2}$$. Therefore, a four-piece puzzle will require 3 operations, while a 51,300 puzzle will require over 650 million operations. So instead of being almost 13,000 times as difficult, such a puzzle is over 210 million times as difficult. You probably see that the difficulty grows quadratically with the number of pieces.
Luckily, during the years you will have developed better solving methods than such a brute force solution. One of the most common approaches is starting with the edges, which is often used by professional jigsaw puzzlers. When using this method they want to know in advance how many border pieces they are dealing with. Hence, a method to calculate the number of border pieces has been developed. Suppose you have a puzzle with 2,000 pieces and you want to calculate B (# of border pieces) from P (# of pieces), the following steps need to be taken:
- 1. List the factors of P: 2*2*2*2*5*5*5=2,000
- Take the square root of P and round off: \sqrt{1000} \approx 45
- Look for numbers in the prime factor list within +/- 20 percent of this rounded off square root: Look between 26 and 54, this gives 2*5*5 = 50
- Determine the other edge length: 2,000/50 = 40
- Add the sides and subtract to correct for corner pieces: B = 50+50+40+40-4 = 176
Now the number of edges is known, solving can be started. Choose a corner piece to start with and try the remaining pieces. Brute forcing yourself through this method results in the number of operations to be:
$$ \frac{\sum_{i = 1}^{B-1} B – i }{2} + \frac{\sum_{i = 1}^{(P – B) – 1} (P – B) – i }{2} = 838988 $$
Starting with the edges thus results in needing approximately 20% fewer operations to solve the jigsaw puzzle. This is not even taken into account the interface of each edge piece. Since you have a border piece, you are looking for another border piece that fits on the knob or hole of your current piece. On average, the ratio of knobs versus holes is 50/50, so you would expect that you only have to check 50% of the remaining border pieces, which results in another small decrease in difficulty.
Taking into account the knob and hole pattern of each piece greatly reduces the number of pieces that should be considered. When implementing this on every piece instead of only the border pieces, one should start in a corner with filling the void. This piece will be constrained on two edges and thus fewer pieces have to be checked. Working through each row in this manner causes the last piece of each row to be constrained on three of the edges so scarcely any of the pieces have to be considered. It can be concluded that considering the piece interface greatly reduces the number of operations needed.
It is now clear that differentiating between edge pieces and non-edge pieces and taking into account the piece interface greatly reduces the number of operations needed. However, you could argue that this can be seen as a reduction in difficulty since this manner of solving is still a method of brute force. Another drawback is that you would have to separate the pieces based on their form, which takes time that is not spent on creating the picture. This could be disadvantageous since there is also a psychological factor in solving jigsaw puzzles. Separating such a small amount of pieces from the big pile could seem tedious, while starting with solving a big chunk immediately could be inspiring to keep solving.
That is the reason that many solvers choose to solve the puzzle based on the color pattern, hence, by looking at the picture that should be created. Instead of separating the pieces based on their knob and hole pattern, it is opted to sort the pieces based on the color, pattern, or distinct features. Not only does this result in parts of the picture becoming clear faster, but mathematically speaking this also seems to be a wise strategy. It gives the opportunity to divide the remaining $P-B$ parts to be divided into sub-blocks $b_1$ up to $b_k$, where $k$ is the number of different colors, patterns, or features you differentiate. Each of these sub-blocks will consist of a certain number of pieces ($n_{b_i})$. Hence, the number of operations needed to solve the complete puzzle can be calculated using:
$$ \frac{\sum_{i = 1}^{B-1} B – i }{2} + \sum_{j = 1}^k \frac{\sum_{i = 1}^{(n_{b_j})) – 1} (n_{b_j})) – i }{2} $$
This again greatly reduces the number of operations needed to solve the puzzle. Based on the size of the sub-blocks, the solver can determine whether brute force solving or solving based on sight is more efficient. To minimize the number of operations, one should choose the number of sub-blocks and sizes of these sub-blocks as optimal as possible. Unfortunately, this will differ for each puzzle.
It can be concluded that there are multiple ways to approach a jigsaw puzzle and that all the methods can be described in the language of mathematics. Of course, not many people will solve puzzles purely using the brute force method, but at some moments, this will most certainly be used. It seems that separating the pieces based on the picture is an efficient way to reduce the time it takes to solve the jigsaw, so if the corona is here to stay, it could be a wonderful challenge to look into the problem of finding the optimal sub-blocks and sub-block sizes of your favorite jigsaw puzzle!
Dit artikel is geschreven door Jochem Hak
