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