Mathematical Recreations: Million-Dollar Minesweeper; October 2000; Scientific American Magazine; by Ian Stewart; 2 Page(s)

Who wants to be a millionaire? The Clay Mathematics Institute, a nonprofit educational foundation in Cambridge, Mass., is offering milliondollar prizes for the solutions to seven infamous unsolved problems. One is the notorious P vs. NP question. Although it is a fiendishly difficult puzzle, a clever amateur may be able to solve it with the help of Minesweeper, the popular game that runs on most personal computers.

Richard Kaye of the University of Birmingham in England pointed out the connection between the game and the P vs. NP question in a recent article entitled "Minesweeper Is NP-Complete" (Mathematical Intelligencer, Vol. 22, No. 2, Spring 2000) . First, let's review how Minesweeper is played. The computer starts the game by showing you a grid of blank squares, some of which conceal explosive mines. Your task is to figure out where the mines are without detonating any of them. In your first move, you choose to uncover any square in the grid. If there's a mine underneath it, you're out of luck: the mine is detonated and you lose the game. If there's no mine, however, the computer writes a number in that square, telling you how many mines there are in the eight adjacent squares.