Efficient search for solving a Jigsaw Puzzle?

Question

I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice.

Let's assume the puzzle pieces are encoded as 4-vectors of integers representing the four sides. A negative integer indicates an indentation that must be matched with corresponding positive integer representing an extrusion. Zero represents a smooth edge (i.e., a border piece.) Rotations then correspond to cyclic shift (assuming the indentations/extrusions are rotationally symmetric.)

My heuristic for an efficient solution is to try to tile the puzzle in an inward spiral starting from the borders. What is the best strategy for building a chain of fitting pieces that avoids exhaustively trying all combinations/rotations?

I found some related SE questions that are relevant:

1. https://cs.stackexchange.com/questions/13849/are-zero-one-jigsaw-puzzles-np-complete
2. https://stackoverflow.com/questions/15121903/algorithm-for-solving-tiling-jigsaw-puzzle
3. Partially filled jigsaw puzzle with six types of tiles

Answer 1

Seems like your heuristic needs to incorporate the distribution of the edge types to be optimal. Here's an idea:

Form a matrix the size of the puzzle's dimensions. Each cell indicates the proportion of remaining pieces that can be fit there on the next iteration without conflicting. At the beginning, the corners of the matrix will be $4$ (only four corner pieces), edges $2(w+h-4)$, and interior $wh-2(w+h-4)$. You can indicate filled cells with a large value, like infinity. Select the set of cells with minimum values as candidates for the next piece. Of these cells, select the piece that decreases the adjacent, unassigned cells by the most amount (use "min" of adjacent cells for the score).

This will ensure you explore the paths that have highest probability of conflicting first. If the first piece you place is incorrect, you want to find if it is incorrect as soon as possible. Likewise, you want to select the first piece to be the one with the least number of choices.

When the min value of the matrix is zero, you know there was an incorrect piece lain somewhere. In that case backtrack, decrease the proportion for the backtracked cell (since now we have eliminated one choice), and begin the iteration again. The backtracked cell will have the minimum value still, of course; so you will simply go on to trying the next piece in the candidate list.

Tentatively, I'd say on average the algorithm would propagate out from the four corners in a spiraling fashion, until two of the corner blocks connect. Then I suspect it would favor building off the connecting block. It will factor in the candidate probabilities, so for specific puzzles the paths it takes will vary.

(You'll need a specialized data structure to store the best candidates list. Could experiment with a blacklist instead. Or could try simply keeping a counter for how many conflicting pieces you tried for a cell, and then recreate the sorted list each time you need to backtrack)