0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Hi, Thanks for the feedback. Can you (or another moderator) move the question to Stackoverflow? Or should I just delete and repost it there? $\endgroup$ – zzz10n Apr 28 '19 at 17:25
  • $\begingroup$ This is a CS question; it's just not a research-level CS question so it belongs here, rather than on CS Theory. Stack Overflow is for programming related things, which isn't what this seems to be. $\endgroup$ – David Richerby Apr 29 '19 at 17:22
  • $\begingroup$ Well, did you try the approach listed in your first link? (basically, use a SAT solver) Does using a SAT solver meet your needs? I expect it should be sufficient to let you start solving real-world puzzles very rapidly. $\endgroup$ – D.W. Apr 29 '19 at 20:04
0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ You could also look at some minesweeper solving algorithms for more ideas. They are similar to this idea in some ways. Minesweeper is NP-complete. $\endgroup$ – Azmisov Apr 29 '19 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.