Summary

I intend to create a robot that can solve jigsaw puzzles. Ideally the robot can solve puzzles entirely on its own, but for an MVP I am considering a situation where a human and a robot work together to solve the puzzle. My goal is to reduce the total time to solve a puzzle by 90% as well as develop my passion and skills in computer vision and robotics. This project is intended entirely as a hobby.

Goals & Personal Background

Project Management

Milestone	Description
Status Quo	A human solves a puzzle on its own.
Milestone 1 (MVP, Project Complete)	A human and a computer work together to solve a puzzle.
Milestone 2 (Long Term Vision)	A robot can fully and autonomously solve a puzzle.
Not doing	Specialty puzzles not normally found at retail.

Background Research

Prioritization

Why do this project and not another robotics or computer vision project.

Robot Ideas

Evaluation is based on the RICE prioritization method.

RICE Scoring Model

Assumptions

Credit: Unsplash

In general, I am assuming a very typical jigsaw puzzle. See the image to the left for an example. This covers almost every puzzle that you can buy at a retail department store such as Target.

For the simplicity of an MVP, other special kinds of puzzles are not covered by this project. For example:

The Clearly Impossible Puzzle - 500 Piece Clear Puzzle Difficult Jigsaw Puzzles Hard Puzzles for Adults - Walmart.com

See subpage for more details.

Assumptions & Failure Points

Similar Examples Elsewhere

Most of the other people who have done a similar project have been college students in computer vision or robotics, or as demonstrations for industrial robots. I intend to replicate this functionality (a substantial goal on its own), but with the target of more off-the-shelf puzzle that you can buy at a retail department store.

Jigsaw Puzzle Building Robot - Yellow Truck Puzzle

Robot Solving Jigsaw Puzzle - Macau Science Center

Robotic Jigsaw Puzzle Solver - Only Solution

Adept Robot has been running in Tech Museum of Innovation for 20 years!

Some similar robots exist in industry. They are called ‘pickers’ and ‘placers’ that pick up objects and place them as desired. Scales range from large objects (such as building a pallet), small hand-held consumer goods, or even very small items such as to assemble a printed circuit board.

Pick and place robot - Smart Robotics

Picking Robots | Remtec | Robotics & Automation

Pick-and-place machine - Wikipedia

Status Quo: The Human Approach

How do humans solve a puzzle now? Generally we use a combination of two factors:

Image content — The lines, shapes, and colors of the image content inside the piece and how it relates to the goal image.
Shape — The shape of the perimeter of the puzzle piece, such as whether it is concave, convex, or straight. Specifically how it fits with neighboring pieces.

The connection algorithm is also typically recursive in fashion, as humans typically split pieces up into groups and then recombine them into a larger whole. This is similar to the merge sort algorithm.

Rough difficulty

Pieces	Difficulty	Time to Solve
< 50	Most people can solve in one sitting	< 30 minutes
51 to 100	Patient people can solve in one sitting	1 hour
101 to 1000	A few sittings, a friend, and patience	Hours to days
> 1000	Lots of sittings, several people, lots of patience	Days to weeks

Typical puzzle solving steps

Empty all the pieces on the board.
Flip them so the image content is on top and the solid color back is on the bottom.
Group by shape.
1. Interior pieces (0 straight edges)
2. Edges (1 straight edge)
3. Corners (2 straight edges)
Subgroup by color or estimated region in the final result image. Subgroup further as needed.
Connect pieces based on image content that overlaps several pieces, as well as by perimeter shape so that two pieces fit flush.
Combine subgroups together into larger groups. Add individual pieces as necessary until the goal image is complete.

Problems with this approach

Grouping is time consuming.
Difficult to mentally link a small piece of image content (zoomed in) to a portion of the goal image (zoomed out).
Misconnections — A piece may match neighboring pieces in color and fit in terms of shape with high accuracy, but the connection won’t be 100% flush.
- These are rare, but are extremely infuriating as previous connections are assumed to be done and are thus reliable enough to be restrictions on future connections.
“Mid game slog”

General Approach

Milestones

| --- | --- | --- | --- | --- | --- |

Software Strategies

There are different two strategies, and two methods in each strategy, to approach the problem of how to decide exactly where each puzzle piece should go.