Create puzzle piece shapes which represent AND, OR, and NOT gates and positive and negative wires. Provide an unlimited number of each. Present the problem in the form of a logic circuit (much as Minesweeper does) by pre-filling the puzzle with pieces which leave room only for positive- or negative- valued gates of one type or another. To complete the jigsaw puzzle, you must find a piece (which is either positively- or negatively-valued) for each open hole. This is equivalent to satisfying constraints on a logic circuit, and is therefore NP-complete.
The reason O(n2) is an acceptable answer because the number of pieces is usually fixed (and equal to the number of positions), so you can just try each piece in each position.
Theory of Computation was perhaps my favorite undergrad course. One day the lecture materials were
a packet of spaghetti
a bunch of Trivial Pursuit cards
a knotted web of string
a piece of wood
a power drill
several screws
It was also interesting because it was a Computer Science course all about the things computers can't do. We therefore wrote no code.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2004-04-30 06:36 am (UTC)The reason O(n2) is an acceptable answer because the number of pieces is usually fixed (and equal to the number of positions), so you can just try each piece in each position.
Theory of Computation was perhaps my favorite undergrad course. One day the lecture materials were
- a packet of spaghetti
- a bunch of Trivial Pursuit cards
- a knotted web of string
- a piece of wood
- a power drill
- several screws
It was also interesting because it was a Computer Science course all about the things computers can't do. We therefore wrote no code.