# Partially filled jigsaw puzzle with six types of tiles

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.