I Built a Computer Program That Can Solve Jigsaw Puzzles
My passion project in computer vision has finally come to completion.
Hello! I’m proud to share with you a side project that’s been a long time coming: A software program that can solve jigsaw puzzles.
Background
One of my favorite activities growing up was solving puzzles. As an adult, I still love to solve them.
But it can also be very difficult, especially halfway through a big 1000 piece puzzle. Where does each piece belong? Even though I am patient, sometimes I just want to flip the table.
On the one hand, this is the challenge that makes a puzzle fun in the first place. But on the other hand, it can also be extremely frustrating. So why not get some help … perhaps from a computer?
When I worked at Matterport a few years ago, I realized the power of computer vision. I got a glimpse into all the cool things they were doing on stitching photos together. So I said to myself:
Why not build a program that can help me solve puzzles? Or even solve the puzzle entirely on its own?
Thus, the impetus for this side project that combined 3 of my passions: puzzles, computer vision, and robotics.
Goals
I had two simple goals when doing this project:
- Reduce the amount of human time it takes to solve a jigsaw puzzle
- Develop my skills in computer vision and robotics
For a full description in a typical PRD (product requirements document) format, see this Notion page:
How It’s Used in Action
For the MVP (minimum viable product, aka version 1), I decided to first create a system where the human and the computer work together. Here’s how it works in practice:
- Connect an external webcam to the computer. Point it down at the table.
- Start program.
- Import a picture of the entire puzzle (ie the art on the box).
- Pick up a piece and place it under the webcam.
- Hit the ‘Capture Piece’ button in the program. The program will automatically take a photo. Then it will compare it to the box art and determine exactly where in the puzzle this piece belongs.
- Pick up the piece and place it in the location as specified by the program. Connect it to other pieces as needed.
- Repeat steps 4 to 6 until the puzzle is complete.
Mission Accomplished
I can say with pride I definitely achieved my two goals.
22% reduction in puzzle solve time
I measured this by actually solving the puzzle twice: (1) status quo, entirely manual and (2) computer assisted. I simply tracked how long it took to complete the puzzle in both times and compared the difference.
For the MVP I used a medium size puzzle with 300 pieces.
The end results were:
- Entirely manual: 85 minutes
- Computer assisted: 66 minutes
That’s a 22% reduction in solve time due to computer help. Not bad!
Learned a lot about coding and computer vision
While I’m not an expert yet, I did learn a boat load about Python and the OpenCV library.
For example, the solving algorithm is entirely based on the ‘content’ of the piece, which is the shapes and corners in the image. This approach proved more fruitful than analyzing the physical shape/contour of the piece.
For the lessons I learned on coding in general, see my other article:
Next Steps
While I achieved all of my initial goals, there’s a few other directions I could take this in the future.
Improve speed even more
As built now, the algorithm that says where each piece should go only works about 50% of the time. The other 50% I have to pin it by hand, which obviously slows me down.
So changes to the algorithm or perhaps a combination of two or more algorithms could more accurately specify the location of every piece and speed up the process even more.
Test on more puzzles
The ice cream truck puzzle, while a nice MVP, is still only 300 pieces. I have a few more 1000 piece puzzles where the computer assistance would really benefit. For example, this one of Boston. Each new puzzle would introduce new edge cases and UX changes that would make the solver more robust.
Turn into a robot
As it is now, it’s not really a robot but just a software program. It would be nice to integrate a robotic arm that can physically pick, place, and connect pieces together. The goal would be a lot less human interaction, so more like a “start it and walk away” experience.
Build mobile robots
While I loved this project, it doesn’t really qualify as a robot at least to me. Even with the pick and place hardware, it is ultimately a manipulator robot.
What I really want to build next is an autonomous mobile robot. So a robot that can sense, evaluate, act, communicate, and move through its environment like a droid from Star Wars. It probably would not be related to puzzles at all.
I’m not sure exactly what kind of robot I’ll build next, but I have several ideas. Stay tuned!
Did you enjoy this article? If yes, then please clap, comment and follow. Thanks for your support!
