CSCE 411 Lecture 40

« previous | "Friday", December 3, 2012 | next »

Review Topics

• Randomized Quicksort
• P, NP, and NP-Completeness
• Undecidability
• Multithreaded Algorithms

How Hard is Minesweeper?

Good player would not take "stupid risks"

• Never make a risky move as long as a safe move is available

Consistency Problem

Given a minesweeper configuration, is it consistent? (i.e. could it have arisen from some pattern of mines?)

A brute-force algorithm exists, but it takes an insane amount of time to search all possible configurations.

Advanced board has over $10^{100}$ possible configurations of 99 mines.

Something in one part of the board can affect the whole board.

Boolean Minesweeper Electronics

Mind = Blown!

wire

carry signals around

splitter

carries and bends wires into different directions

crossover

allows two wires to cross without disturbing signal

gates

AND, OR, NOT, etc.

We just reduced boolean satisfiability into a minesweeper problem!

Conclusion

Therefore the minesweeper consistency problem is NP-Complete