R. Kaye “Minesweeper is NP-complete", Mathematical Intelligencer, vol 22, number 2, pp9-15, 2000.

Reduction from 3COLOR: https://www.youtube.com/watch?v=CBP7OAhyff0

Minesweeper is NP-complete detailed proof: http://simon.bailey.at/random/kaye.minesweeper.pdf

http://simonsoftware.se/xkcdsw/comic.php?id=44