January 5th, 2017, 8:37 pm
Standard jigsaws only become NP-complete if the solver cannot reject a prospective solution with bounded M<<N pieces. That is, the solver faces a non-zero chance of placing N-1 pieces in what seems like a valid configuration only to find that the last piece fails to fit.
For most jigsaw puzzles, however, the piece shape and color patterns across the boundary are so unique that it's virtually impossible to incorrectly put even two pieces together.
That said, I have seen puzzles with identically-shaped innie & outie tabs (and large expanses of uniform color) where one can get trapped and have to undo a set of pieces that seemed to go together.
Last edited by
Traden4Alpha on January 11th, 2017, 10:33 pm, edited 1 time in total.