![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
A friend of mine semi-jokingly put this 24,000 piece jigsaw puzzle (the world's largest) on her Amazon wishlist. A family member surprised her with it as a Christmas present. The box is the size of a small coffee table ... when laid out, the puzzle is 5 ft x 14 ft.
It got me thinking about how much work it would be to solve this puzzle.
Puzzles can range from easy to hard depending on the picture and the design of the pieces.
In a worst-case scenario, the picture on the puzzle is something completely uniform (eg a giant pile of needles), making it impossible to tell where any given piece might go in the puzzle by looking at the picture. The positions of edge and corner pieces are more well known, but these form a small minority of the pieces. In this scenario, the shapes of the pieces are nearly identical, so you more or less have to try every piece against every other piece to see if it fits. This means, for a puzzle with N pieces, you'll have to do some multiple of N^2 comparisons. In terms of the computer science concept of computational complexity, it's O(N^2)
In the best-case scenario, the picture provides a lot of detail and variety, allowing you to pinpoint the location of any given piece of the puzzle by looking at the picture on the box. In this case, you'll only have to try each piece once. Each piece will only have to be compared against a small number of neighbors. Identifying the rough location of all the pieces is probably slightly slower than O(N) if the picture has so much variety that our (massively parallel) brains can quickly spot the correct location even in a large image, and trying the pieces with their immediate neighbors is likely slightly slower than O(N) as the cluster of neighbors will likely be somewhat larger for a really large puzzle.
The good news is that the 24,000 piece puzzle is more like the best-case scenario. Still, solving it is hard enough that one solver got a newspaper article written about him.
I got curious how these speed estimates change if you have a large number of solvers.
There are high speed house building competitions in which large teams compete to build a standard house design from raw materials in as little time as possible. Apparently they can get a full house built in under 3 hours... or at least, they can do it when there's cheesy 80s music playing in the background.
For this jigsaw puzzle, I'm thinking the team-based approach would go like this:
- Make lots of high-resolution copies of the puzzle picture, one for each user.
- Divide the puzzle into small subregions, grouping areas of similar appearance together. Label them on the pictures.
- Give each person a portion of the pieces and ask them to sort the pieces into likely subregions based on their appearance. (Each person would have a set of bins, one for each subregion)
- Merge each person's bins for a given subregion into a master bin for that subregion.
- Print a full-size view of the puzzle picture, cut it into the subregions, and then arrange the pieces spread out in a large room in the same overall position as in the original picture. Put the bin for each subregion with the picture.
- Assign one or more people to each bin as necessary, and let them begin to solve the minipuzzle of their subregion. As they get closer to completion, they can start to link up with their neighbors' subregions. Pieces that do not seem to belong in their subregion can be returned for reclassification.
I'm thinking that with a team of 50 people, you could probably get this puzzle solved in under a day. That's one match every two minutes per person for 16 hours. That seems doable.
It got me thinking about how much work it would be to solve this puzzle.
Puzzles can range from easy to hard depending on the picture and the design of the pieces.
In a worst-case scenario, the picture on the puzzle is something completely uniform (eg a giant pile of needles), making it impossible to tell where any given piece might go in the puzzle by looking at the picture. The positions of edge and corner pieces are more well known, but these form a small minority of the pieces. In this scenario, the shapes of the pieces are nearly identical, so you more or less have to try every piece against every other piece to see if it fits. This means, for a puzzle with N pieces, you'll have to do some multiple of N^2 comparisons. In terms of the computer science concept of computational complexity, it's O(N^2)
In the best-case scenario, the picture provides a lot of detail and variety, allowing you to pinpoint the location of any given piece of the puzzle by looking at the picture on the box. In this case, you'll only have to try each piece once. Each piece will only have to be compared against a small number of neighbors. Identifying the rough location of all the pieces is probably slightly slower than O(N) if the picture has so much variety that our (massively parallel) brains can quickly spot the correct location even in a large image, and trying the pieces with their immediate neighbors is likely slightly slower than O(N) as the cluster of neighbors will likely be somewhat larger for a really large puzzle.
The good news is that the 24,000 piece puzzle is more like the best-case scenario. Still, solving it is hard enough that one solver got a newspaper article written about him.
I got curious how these speed estimates change if you have a large number of solvers.
There are high speed house building competitions in which large teams compete to build a standard house design from raw materials in as little time as possible. Apparently they can get a full house built in under 3 hours... or at least, they can do it when there's cheesy 80s music playing in the background.
For this jigsaw puzzle, I'm thinking the team-based approach would go like this:
- Make lots of high-resolution copies of the puzzle picture, one for each user.
- Divide the puzzle into small subregions, grouping areas of similar appearance together. Label them on the pictures.
- Give each person a portion of the pieces and ask them to sort the pieces into likely subregions based on their appearance. (Each person would have a set of bins, one for each subregion)
- Merge each person's bins for a given subregion into a master bin for that subregion.
- Print a full-size view of the puzzle picture, cut it into the subregions, and then arrange the pieces spread out in a large room in the same overall position as in the original picture. Put the bin for each subregion with the picture.
- Assign one or more people to each bin as necessary, and let them begin to solve the minipuzzle of their subregion. As they get closer to completion, they can start to link up with their neighbors' subregions. Pieces that do not seem to belong in their subregion can be returned for reclassification.
I'm thinking that with a team of 50 people, you could probably get this puzzle solved in under a day. That's one match every two minutes per person for 16 hours. That seems doable.
