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).

enter image description here

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.


Your Answer

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

Browse other questions tagged or ask your own question.