A difficult board to analyze, showing the result for one cell.
Welcome to the home page for MindSweeper, yet another incarnation of minesweeper --- everybody's favourite waste of CPU cycles! My implementation's claim to fame is that it includes a game solver so that at each move it can tell you whether or not you need to guess and/or what the mine probabilities are. Or just let the computer play for you!
MindSweeper can be downloaded from the SourceForge project page. There are both source and pre-compiled binary packages available. Requires a GNU/Linux-like system with GTK2, POSIX threads, etc., etc..
Current features:
A recent copy of the TODO list:
Everybody loves screenshots.
The solver in this game uses a "brute force" approach. It begins by identifying all of the unmarked cells for which information is available and then systematically tests each possible arrangement of flags in those cells searching for flag arrangements that are consistent with all available information. As the search procedes, for each cell a count is kept of the number of valid arrangements in which it was flagged. When the search terminates, the ratio of this number to the total number of valid arrangements gives the probability of finding a mine in that cell. If this ratio is 0 then the cell can be cleared with certainty, if the ratio is 1.0 then it can be flagged with certainty.
Some tricks are used in order to speed up the analysis process. First of all, it is often the case that a cell can be cleared or flagged based solely on the information available in its immediate neighbours; for example a corner square with a 1 diagonally adjacent to it.
A special algorithm is included in the solver for handling these cases and it is only when this algorithm fails to identify a move that the full brute-force search is begun. Another trick that is used is the separation of the border cells into independant groups: groups of cells whose flag placements do not influence each other. A full solution to the problem of identifying logically independant cell groups is as complex as actually solving the game. The test that is used here is simply to check if two cells share the same information and if they don't then they are said to be independant. In this sense, it is more accurate to say the cells are divided into "geographically distinct" sets. This separation greatly reduces the number of flag permutations that need to be searched.
The final trick that is used, although it is not much of trick, is to search the permutations for valid flag arrangements using an in-order tree traversal algorithm. This allows entire brances of the tree to be ruled out early on without having to actually test each possible permutation one-by-one. Consider, for example, that the border region in the screenshot above contains 78 unmarked cells. Given that there are 50 flags remaining to be placed on the board there are, in principle, 3*1023 permutations available. On a 1.3 GHz Pentium 3, the solver takes approximately 87 seconds to decide that the information available does not identify any moves with certainty --- an effective analysis rate of 3.4*1021 permutations per second or 2.7*1012 permutations per CPU clock cycle. This is clearly way beyond the processing capabilities of the computer and so illustrates the efficiency with which permutations are analyzed.
At the same time, the solver also takes into account the fact that it is playing on a finite field with a known total number of mines. This information is used to rule out flag permutations that would excede the number of mines and this additional restriction sometimes allows boards to be played to completion that could not be completed otherwise. The limit on the number of mines can also sometimes allow cells outside of the border region to be played. By knowing, for example, that the border cells must use all remaining flags then all other cells can be cleared. Alternatively, knowing that the border cells must not use more than some number of flags it may be necessary to flag all other cells.
Overall, on modern personal computers the solver is capable of playing the game much faster than a human which allows it to play along with the user in real time. In practice, "Advanced" level boards rarely take more than 2 seconds to play to completion on the system described above and are most often completed with 0 still showing on the clock.
For some information on the minesweeper problem, check out Richard Kaye's Minesweeper Pages. For another solver-equipped minefield game, check out Truffle-Swine Keeper.