What is the efficient Algorithm for Solving Jigsaw Puzzle?

Question

Yesterday I was just playing Jigsaw Puzzle and somehow wondered what would be algorithm for solving it.

As human, steps which I followed where:

1. Separate all pieces in 3 parts, single flat edge, double flat edge and no edge at all.
2. Separate flat edge pieces as they would be corners of image
3. Separate single edge pieces as they would form 4 end edges of images
4. Lastly, pieces with no edges would form internal of the image.
5. Match the color and image pieces to put pieces together.

I was wondering what would be the efficient algorithm to solve this puzzle efficiently and what datastructure would provide optimum efficient solution.

Thanks.

Answer 1

Solving problems like this can be deceptively complicated, especially if no constraints are placed on the size and complexity of the puzzle.

Here's my thoughts on an approach to writing a program to solve such a puzzle.

There are four key pieces of information that you can use individually and together as clues to solving a jigsaw puzzle:

1. The shape information of each of the pieces (how their edges appear)
2. The color information of each of the pieces (adjacent pieces will generally have smooth transitions)
3. The orientation information of each piece (where flat and corner edges may lie)
4. The overall size and number of pieces provide the general dimensions of the puzzle

So what kind of information will the program will be supplied - let's assume that each puzzle piece is an small rectangular image with transparency information used to identify the portion of the puzzle piece that represent non-rectangular edges.

From this, it is relatively easy to identify the four corner pieces (in a typical jigsaw). These would have exactly two edges that have flat contours (see contour map below).

Next, I would build information about the shape of each of the four edges of a puzzle piece. This information can be used to build an adjacency matrix indicating which pieces fit together.

Now we can prune this adjacency matrix to identify just those pieces that have smooth color transitions in their adjacent configuration. This is somewhat tricky because it requires a level of fuzzy matching - since not every pixel-to-pixel boundary will necessarily have a smooth color transition.

Using the four corner pieces originally identified, we should now be able to reconstruct the dimensions and positions of all of the pieces in the puzzle.

A convenient data structure for representing edge shapes may be a contour map - essentially a set of integers representing the incremental deltas in distance from the opposing side of the image to the last non-transparent pixel in each of the four sides of the puzzle piece. Pieces that match should have mirror-image contour maps.