Jay Little - Software Obsessionist
The Minesweeper Algorithim - Explanation
[Prev]  
  [Next]  

Disclaimer

This theory in its current form is not consistent. An updated version may be available in the future. What is written below is simply the theory behind the current algorithim.

The NP solution

The normal P solution for minesweeper runs a bit like this when run on a given configuration:

(1) Determine which parts of the board MAY contain mines. (2) Try filling all possible combination of mines and "no mines" (3) Repeat step two until a good configuration is found or combination possibilities are exhausted.

As you can see its a fairly simple algorithim. However depending upon the number of blank locations - it can take quite a while to run. In order to determine the absolute maximum number of combinations that will be required in order to check whether or not a given configuration is valid - you use the following formula (where n = the number of questionable/blank locations on the board):

2^N

Barring the existance of large amounts of luck - more complex and incomplete configurations could take quite a while to check. Thats where my P solution comes into play.

The P Solution

My algorithim approaches the problem from a different perspective than more NP problems. Instead of attempting to fill the questionable areas of a board - it attempts to satisfy the requirements presented by the incomplete numeric locations on the board.

An incomplete numeric location would look something like this:

???
?4?
???
This location has a value of 4. It is surrounded by eight questionable areas. This means that there MUST be 4 mines within the 8 surrounding squares or the configuration is inconsistent. This above example requires at most 70 different combinations of mines/non mines to check for consistency.

Now you are probably thinking, "This still looks like an NP algorithim to me" - but here is the clencher: How is the algorithim, upon finding a correct combination able to check that combination against other portions of the board without becoming recursive? Well as you may have noticed, in minesweeper configurations almost everything is related. They key here is that almost everything is LOGICALLY related. This means that the effects of any single change to the board can be measured fairly easily. Lets say I had a configuration such as the following:

NMN?1
M4M2?
NMNM1
This configuration is an extension on the one above. I've added two columns of locations to the right side. There are two questionable points. As you can see the 2 is already surrounded by two mines though which means the two questionable spots must NOT have mines.

The lesson here is that changes around certain locations in a configuration can be logically propogated to other parts of the board. Some locations have more "influence" over the board than others. The idea is to use these points to our advantage. I call them KeyPoints.

What makes a keypoint a keypoint?

A keypoint is determined by ranking the numeric locations on the board by the number of combinations of mines they can have. All numeric points which share the high position become keypoints. The combinations and proprogations for each keypoint are then processed. Once a VALID combination for a keypoint (which has been validated through proprogation) has been found - that keypoint is completed processing. It will never be processed again. The combinations of keypoints are not checked recursively against one another because there is simply no need.

If a proprogated keypoint combination presents no inconsistencies - this does not mean the board is consistent - it simply means that portion of the board is. Once al of current the keypoints have been processed, the numeric squares are ranked once again as described before. If the board is consistent there will be no more incomplete numeric points to rank. If not - another set of keypoints is generated.

So how do you know whether or not a board is consistent?

If it is impossible to generate any more keypoints (ie all numeric points on the board have been satisfied) then the board is consistent. If any given keypoint is found not able to support any configuration of mines around - the board is inconsistent.

What is the maxiumum number of combinations you have to check?

Thats easy simply use the following formula (N = the number of numeric locations on the board):

N*70

Obviously this solution can be classified as P. It is possible that every numeric location on the board will be processed as a keypoint - therefore you must use that number. It is also possible that every numeric location on the board will require up to 70 different combinations. However since keypoints do not depend on one another for consistency and each location will only be processed once - you have a P algorithim.

How are you propogating these mines?

I use a Queue. Initially the Queue is filled up with all numeric locations on the board. If a location is found to be solvable due to a change on the board - it is removed from the Queue. The Queue stops when one of the following conditions have been met:

(1) An inconsistency has been detected on the board (2) The Queue has gone a full rotation without processing any changes (3) There Queue has been cleared.

If #1 is true - then the board is inconsistent. Otherwise processing continues. The Queue is the only way to proprogate mines throughout a minesweeper configuration accurately without missing ANY possibilities. While the Q can be processor intensive - it doesnt add to the number of combinations processed and its not recursive in any way.

How do you know the possible number of combinations for a keypoint?

Thats easy - use a simple factorial procedure to determine the maximum number for each different location. It is detailed in the code.

Speaking of the code....

Grab a copy on the download page of this article. Be sure to check out the links for a better understanding of the problem.

J

  [Prev]  
  [Next]  
Search:
  [Rss]   [Email]