Jigsaw Puzzle Solver in Python with OpenCV (Edge Matching)

A Python + OpenCV jigsaw puzzle solver that takes a photo of pieces on a table and reconstructs the full image — via piece segmentation, tab-vs-blank edge classification, and a greedy graph assembler. It's the project I started thinking "just match colors on the edges, right?" and ended up being one of the most satisfying computer-vision experiments I've done.

TL;DR

• Segmentation: grayscale → blur → adaptive threshold → cv2.findContours.
• Edges: classify each of 4 sides as tab, blank, or flat by checking if the midpoint is inside or outside the corner-to-corner baseline.
• Matching: geometric distance + color-gradient similarity combined.
• Assembly: greedy, corners → edges → interior.

The problem

You give the computer a photo of jigsaw pieces laid out on a table. It figures out the full picture. Simple to explain, painful to implement — which makes it the perfect computer-vision playground.

Live demo: tinyurl.com/PuzzleSolvers.

Step 1: segmenting each piece from the background

I started with basic thresholding and contour detection in OpenCV, which works okay if your background is a single flat color and the pieces have decent contrast. Once you lose either of those assumptions, the pipeline falls apart.

The final preprocessing stack:

gray  = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
blur  = cv2.GaussianBlur(gray, (5, 5), 0)
bin   = cv2.adaptiveThreshold(
    blur, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
    cv2.THRESH_BINARY_INV, 25, 5
)
contours, _ = cv2.findContours(
    bin, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE
)

cv2.RETR_EXTERNAL gives you one contour per piece, no nested holes. Use cv2.CHAIN_APPROX_NONE here because you'll need the dense point sequence for the edge-classification step.

Step 2: characterizing piece shape — the four corners

Each piece has four sides, and each side is either a tab (sticking out), a blank (sticking in), or a flat edge (for border pieces). Classifying which is which was the hardest part.

The routine:

1. Run cv2.approxPolyDP on the contour to reduce it to a polygon.
2. Find the four sharpest turns — those are the corners.
3. Between each adjacent corner pair, sample the midpoint of the contour segment.

Then the classification rule:

| Midpoint position | Classification | |---|---| | Outside the corner-to-corner baseline | Tab | | Inside the corner-to-corner baseline | Blank | | On the baseline | Flat |

That's it — no ML needed. Surprisingly robust on standard puzzles.

Step 3: matching sides

For two pieces to fit, their edge curves need to be near-mirrors of each other. I tried two approaches:

1. Resample each edge into a fixed number of points, then compute a pairwise distance between the two sequences. Gives you a clean geometric match score.
2. Compare color gradients along each edge — the piece of the image on one side should match the piece on the other. This is the content match score.

Approach 1 gives a solid geometric match; Approach 2 disambiguates when multiple candidates have similar shapes. Their combined score worked better than either alone. I also experimented briefly with SIFT descriptors along the edge — cleaner for uniform regions but heavier to compute.

Step 4: assembly as a graph problem

Once you have a scoring function for "how well does edge A fit edge B," the full puzzle is a graph problem: find the arrangement that minimizes total edge-match cost.

I went with a greedy assembler:

1. Place corner pieces first (two flats meeting at a corner).
2. Then edge pieces (one flat, three real edges).
3. Then interior pieces, choosing the minimum-cost unplaced piece at each step.

Good enough for most of my test puzzles. Not good enough for everything — see below.

Where it breaks

• Puzzles with repeating patterns (lots of sky, lots of grass) — the color-gradient signal isn't strong enough and the greedy assembler picks the wrong neighbor early.
• Aggressive cuts — when tabs are unusually large and weird, the corner detector sometimes grabs the wrong sharpest turns, and the whole piece classification derails.
• Pieces flipped over — I hadn't thought about upside-down pieces at all when I started.

Ideas for next time

• Train a small CNN for edge-to-edge compatibility instead of handcrafted features — same approach Jigsolved by Cornell Tech took and it pays off on textured regions.
• Swap the greedy assembler for an energy-minimization solver (belief propagation or simulated annealing) that can back out of early mistakes.
• Handle flipped pieces explicitly by checking both orientations at classification time.

For now though, it assembles most of the puzzles I throw at it, and I'm calling that a win.

Key takeaways

• Preprocessing is most of the work. Clean binarization → clean contours → everything downstream gets simpler.
• Tab-vs-blank classification is elegantly geometric. You don't need ML if you have good corners.
• Greedy assembly is fine for most puzzles; only exotic cuts and repeating-pattern images demand something fancier.

References

• Riccardo Albertazzi — Solving Jigsaw puzzles with Python and OpenCV
• Cornell Tech — Jigsolved: Computer Vision to Solve Jigsaw Puzzles
• Kellin Wood — PuzzleSolver on GitHub
• Demo video — tinyurl.com/PuzzleSolvers
• More projects