Minesweeper is NP-complete!

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

http://www.hermann-uwe.de/blog/minesweeper-is-np-complete

http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/page4.html