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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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