This is a slight variation of the question Are 'zero-one' jigsaw puzzles NP-complete? asked on cs.stackexchange.com.What is the complexity of the following problem?Input: an $n\times n$ Jigsaw puzzle with the six simple types of tiles shown in the figure below. $k$ tiles are already placed on the board and cannot be moved.Question: can we correctly complete the puzzle placing the remanining $n^2 - k$ tiles on the board (tiles can be rotated).The original question on cs.stackexchange is a particular case in which $k = 4n-4$ and the initial tiles are placed only on the border.
Partially filled jigsaw puzzle with six types of tiles
np hardness;puzzles