From kubo@jacobi.math.brown.edu Thu Apr 23 10:56:44 CDT 1998
Article: 190788 of sci.math
Path: gannett.math.niu.edu!corn.cso.niu.edu!vixen.cso.uiuc.edu!cdc2.cdc.net!nntp.giganews.com!news.maxwell.syr.edu!news-peer.sprintlink.net!news.sprintlink.net!cpk-news-hub1.bbnplanet.com!cam-news-feed1.bbnplanet.com!news.bbnplanet.com!cocoa.brown.edu!kubo
From: kubo@jacobi.math.brown.edu (Tal Kubo)
Newsgroups: sci.math
Subject: Re: Minesweeper
Date: 23 Apr 1998 02:51:27 GMT
Organization: Math Department, Brown University
Lines: 12
Message-ID: <6hmabf$s9a@cocoa.brown.edu>
References: <353e01af.724384@news.mindspring.com>
NNTP-Posting-Host: jacobi.math.brown.edu
Xref: gannett.math.niu.edu sci.math:190788


Minesweeper is NP-complete, in the sense that determining whether
a given screen display is consistent with a placement of mines is
NP-complete.  (See http://for.mat.bham.ac.uk/R.W.Kaye/publ/minesw.ps
for the proof, based on programming Boolean circuits as Minesweeper
configurations). 

Related folklore: evaluating positions in Robots is NP-complete. 
IIRC the idea was to reduce SAT instances to starting positions 
where the robots are inside a strip of width 2 or 3, and the player 
is on one side of the same strip.