1
$\begingroup$

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.

$\endgroup$

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.