What is the efficient Algorithm for Solving Jigshaw Puzzle ?

Question

Hi,

Yesterday I was just playing Jigshaw 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

Assuming you're not going to get into any computer vision stuff, it would be very small variations on a search of the entire problem space, i.e. trying every piece until one fits, and repeating. The major optimization would be not trying the same piece in the same place if you know it doesn't fit. Side/corner pieces make up relatively few of the pieces and probably couldn't be considered in any major optimization.

The data structure would probably be something like a hash matrix, where you could quickly check if you're already tried a piece in a position.

An easy optimization that includes computer vision would be to try pieces at each position after sorting pieces by how close their average color matches adjacent positions.

This just off the top of my head of course.

Answer 2

Make sure to scan for male/female portions of a piece--this will cut the search in half.

Answer 3

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.

Answer 4

I don't think that the human way would be that helpful for an implementation - a computer can look at all pieces many times a second and I see no (big) win by categorizing the pieces into corner, edge, and inner pieces, especially because there are only three categories and they have very different sizes.

Given a set of images of all pieces I would try to derive a simple descriptor for every piece or edge. The descriptor must contain information about the rough shape and the color of the piece respectively the four edges. Given a puzzle with 1000 pieces, there are 4000 edges and always two must be equal (ignoring the border of the puzzle). In consequence the descriptor must be able to distinguish 2000 edges requiring at least 11 bits.

Dividing one piece into a 3 x 3 check board pattern with nine fields will give three colors per edge - with eight bits per channel we already have 72 bits. I first tended to suggest to reduce the color resolution, but this seems not to be a good idea - for example a blue sky might really benefit from a high color resolution. Note that calculating the colors probably requires separating the piece from the background and trying to align the edges to the horizontal and vertical axises.

In very uniform areas like blue skies the color information will probably not be enough to find good matches and additional geometric information will be required. I would try to describe the shape of the edge by its curvature or a derived measure. Maybe sampled at ten to twenty points per edge. This probably again relies on background separation and edge alignment.

Finally the computer can do the easy part - compare all pairs of edge descriptors and find the best matches. This process should probably be controlled to become more local instead of simple best match first because when ever you have found a corner (Correct English word? I mean three pieces in a L-shape.) you have two edges constraining the piece to find and one can track back early if no good match can be found (indicating an error made before or a hard puzzle).