Mathematical games

[vvvexation]

No doubt at least a few of y'all will find this interesting: Apparently Minesweeper is NP-complete. Not only that, but you can use it to build logic gates.

Comments

[flwyd.livejournal.com]

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(n²) 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.

[vvvexation.livejournal.com]

Once again, you tease me into asking for details--this time about the lecture with the spaghetti.

[flwyd.livejournal.com]

The lecture was about analog computation. The spaghetti demonstrates sorting. The prof broke noodles into various lengths and then announced he would sort them by length. He gathered them all in his hand, stamped them on the table so their bottoms all had the same position, and then moved his hand down from above until encountering a noodle, pulled it out, and laid it on the table as the largest one.

The rope represented a graph with nodes at knots and string as edges. To find the shortest path between two nodes, take one in each hand and pull -- the shortest path is the taut straight line.

He then drilled a bunch of screws into the board. The algorithm for convex hull is as follows: tie a rope to the bottom-most screw. Then hold the rope to the side and take it around the board widdershins. It will wrap on each point on the edge of the convex hull.

The Trivial Pursuit (or maybe it was some other game) was to illustrate an error some students were making in homework answers. He demonstrated an exponential-time sorting algorithm by scattering them all on the table and then looking through each card for each other that gets picked up. He told us not to take notes on that part, because we'd look back and see a statement like "Sorting takes exponential time."