Home page

Image: Minesweeper
Versions of Minesweeper are often found as free add-ons for personal computer operating systems. The player tries to uncover numbers while avoiding concealed "mines."
Game may help
solve math mysteries
Minesweeper used in research
on decades-old 'P versus NP' problem;
solution could earn a $1 million prize

By Lisa Lipman
BOSTON, Nov. 2  Minesweeper, a seemingly simple game included on most personal computers, could help mathematicians crack one of the field's most intriguing problems.

Advertising on MSNBC  
MSNBC Shopping Space News

'If there was a way of playing Minesweeper efficiently, then there would also be a way of cracking codes efficiently.'
University of Birmingham
       WHILE SOME people may pass hours mindlessly playing Minesweeper, mathematicians are toiling over a larger version of the game, hoping to solve a problem so confounding that an institute offered $1 million to anyone who could crack it.
       The buzz began after Richard Kaye, a mathematics professor at the University of Birmingham in England, started playing Minesweeper.
       'I'm always interested in games with math elements. Math and games go together brilliantly,' Kaye said. 'I realized there was probably some nice mathematics behind it. But I didn't know what I was looking for.'
       Minesweeper is a game in which players try to figure out which squares of a grid contain computerized mines. A number in each square indicates how many mines are in the squares around it. The game is generally included in the Microsoft Windows operating system. (MSNBC is a Microsoft-NBC joint venture.)
       After playing the game steadily for a few weeks, Kaye realized that Minesweeper, if played on a much larger grid, has the same mathematical characteristics as other problems deemed insolvable.
       In fact, he said, Minesweeper could help in the quest for one of mathematics' white whales: the solution to what is known as the 'P versus NP' problem. The problem has been around for about 30 years.
       The problem attempts to determine whether questions that seem to be unsolvable within a reasonable period of time might actually have a relatively simple way of being solved, possibly by computer.
       Kaye said that if someone were to figure out an algorithm for determining all combinations of mine placement in a large-scale version of Minesweeper, that person will have solved the P versus NP problem
       The Clay Mathematics Institute in Cambridge, Mass., has offered $1 million to anyone who can solve it.
       The discovery could have a wider impact.
Click Here!

       'If there was a way of playing Minesweeper efficiently, then there would also be a way of cracking codes efficiently,' Kaye said.
       Ian Stewart, a research mathematician who teaches at the University of Warwick in England, said: 'It's surprising that such a simple game would put us at such a frontier of mathematics. But the big questions in math are not very far below the surface of everyday life.'
       Arthur Jaffe, president of the Clay Mathematics Institute, said he was already a fan of Minesweeper before he heard about Kaye's research. He plays the game on nights when he has trouble falling asleep.
       'I told my 14-year-old daughter about it,' he said. 'She was just amazed it was educational.'
       Copyright 2000 Associated Press. All rights reserved. This material may not be published, broadcast, rewritten or redistributed.
Special Report Science news from MSNBC
Bulletin Boards Discuss discoveries on the Science BBS

Internet Sites Clay Mathematics Institute
Internet Sites Ivar Peterson's Math Trek: Minesweeper Logic
MSNBC News A last look back at a cosmic quest
MSNBC News 'Astounding' ancient ship found
MSNBC News The not-so-random science of polling


Would you recommend this story to other viewers?
not at all   1  -   2  -   3  -   4  -   5  -  6  -  7  highly

  MSNBC is optimized for
Microsoft Internet Explorer
Windows Media Player
MSNBC Terms,
  Conditions and Privacy 2000
  Cover | Headlines | News | Business | Sports | Local | Technology | Living & Travel | Health
TV News | Opinions | Weather | Shop@MSNBC | MSN | Comics | Find | About MSNBC | Help | Index
News Tools | Jobs | Write Us | Advertising on MSNBC | Terms, Conditions, and Privacy