From: Minghui Jiang [jiang@cs.montana.edu]
Sent: Thursday, February 12, 2004 2:53 PM
To: Ross, Rocky
Cc: vijay; Anthony; tim; mumey@coe.montana.edu
Subject: Minesweeper

Following the pointers in the Tetris paper, I found this Minesweeper 
paper. I just read it and was immensely entertained:

Richard Kaye. Minesweeper is NP-complete. Mathematical Intelligencer, 
22(2):9-15, 2000.

MSU has subscription to Mathematical Intelligencer, you can find it by (www.lib.montana.edu, Library Catalog, E-journal finder).

Note that the bent wire in Fig.7(a) has two mislabeled cells (can you find 
it?). The AND gate construction (Fig.13) is devillishly clever ;)

Also, following the link below you can find colored image of the gadgets: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm