You are given a box and a collection of cards as indicated in the following figure. Because of the pegs in the box and the notches in the cards, each card will fit in the box in either of two ways. Each card contains two columns of holes, some of which may not be punched out. The puzzle is solved by placing all the cards in the box so as to completely cover the bottom of the box (i.e., every hole position is blocked by at least one card that has no hole there). Let PUZZLE = {〈c₁, . . . , c_k〉| each c_i represents a card and this collection of cards has a solution}. Show that PUZZLE is NP-complete.

Transcribed Image Text:

card other way box one way notch pegs hole 00000 00 00 00000