Algorithms used in solving minesweeper.
Some definitions.
	A cell is called  Free  or  Unvisited  if we don't know its content. Only neighbours cells can give information about this cell.
	A cell is called  Visited  if we know its content. Either a bomb or the number of neighbours containing a bomb.
	A cell is called  Without_Info  if it is Unvisited and all its neighbours are either Unvisited, or contain a bomb.
	A cell is called  With_Info  if it is Unvisited and has at least one visited neighbour which does not contain a bomb.
	A  Configuration  is a repartition of all the bombs among the all the cells.
	A  State is a repartition of cells, some visited, other Unvisited. Each click on the minesweeper field make the game pass from one  State  to another.

bt	= total number of bombs in the field
Nx	= Number of cells in a line
Ny	= Number of cells in a column
Nt	= Nx * Ny = total number of cells.
k!	= 1 * 2 * 3 * ... * k     (0! = 1! = 1,  2! = 2,  3! = 6,  4! = 24,  5! = 120,  ...)

For a given State :
Nv	= Number of Visited cells
Ni	= Number of Cells With_Info
Nwi	= Number of cells Without_Info
bv	= Number of bombs among the Visited cells.
bi	= Number of bombs among the cells With_Info.
bwi	= Number of bombs among the cells Without_Info

For a given Cell :
Nci	= Number of neighbours cells With_Info of a given cell.
Ncwi	= Number of neighbours cells Without_Info of a given cell.
bcv	= Number of bombs among the neighbours cells Visited of a given cell.
bci	= Number of bombs among the neighbours cells With_Info of a given cell.
bcwi	= Number of bombs among the neighbours cells Without_Info of a given cell.

Each cell can have a value.
Cell=-2 => an Unvisited cell,    Cell=-1 => a cell containing a bomb.
Cell=0..8 => indicate the number of neighbour cells containing a bomb.

We define the functions :
NextState(State, Cell, k) = State where "Cell=k" has been added
NbConfig(State) = Number of configurations compatible with the given "State".
NbConfig(State, Cell, k) = NbConfig(NextState(State, Cell, k))
NbConfigInfo(State) = Number of configurations of the cells "With_Info" compatible with the given "State".
NbConfigInfo(State, bi) = Number of configurations of the cells "With_Info" compatible with the given "State", knowing that there are  "bi"  bombs among them.
NbConfigInfo(State, bi, Cell, k) = Number of configurations of the cells "With_Info" compatible with the given "State", knowing that there are  "bi"  bombs among them and that "Cell=k".
NbConfigWithoutInfo(Nwi, bwi) = Number of configurations of the cells "Without_Info" compatible with the given "State", knowing that there are  "bwi"  bombs among them.

We will make the hypothesis that each configurations has the same probability to occur.

We have some formulas :
For a given State :
Nt = Nv + Ni + Nwi
bt = bv + bi + bwi
                                          Nwi!
NbConfigWithoutInfo(Nwi, bwi) = -------------------
                                  (Nwi - bwi)! * bwi!
At the beginning Nwi = Nt, bwi = bt

NbConfig(State) = Sum for bi=0 to bt-bv
   NbConfigInfo(State, bi) * NbConfigWithoutInfo(Nwi, bwi)
 =Sum over all configurations of cells "With_Info"  of
   NbConfigWithoutInfo(Nwi, bwi)
"bwi = bt-bv-bi "  can vary for each configuration.   This second formula is practicable.

NbConfig(State, Cell, -1) = Sum for bi=0 to bt-bv
   NbConfigInfo(State, bi, Cell, -1) * 
   NbConfigWithoutInfo(Nwi, bwi)
 =Sum over all configurations of cells "With_Info" having "Cell=-1" of
   NbConfigWithoutInfo(Nwi, bwi)
"bwi = bt-bv-bi"  can vary for each configuration.   This second formula is practicable.

For  "k >= 0"  it is a little more complicate :
NbConfig(State, Cell, k) = Sum over all configurations of cells
                           "With_Info" having "Cell=k" of :
                                                     Ncwi!
   NbConfigWithoutInfo(Nwi-Ncwi, bwi-bcwi) * --------------------
                                             (Ncwi-bcwi)! * bcwi!
where  bcwi = k-bcv-bci  = number of bombs among the neighbours Cells Without _Info

Cells "Without_Info" have all the same probability to have a bomb.
Apart from those in the border, they also have all the same probability to contain a given number.
For a Cell Without_Info :
NbConfig(State, Cell, -1) = 
 = Sum over all configurations of cells "With_Info" of
   NbConfigWithoutInfo(Nwi, bwi)
"bwi = bt-bv-bi"  can vary for each configuration.   This formula is practicable.

                      NbConfig(State, Cell, k)
Pr(Cell=k | State) = ------------------------    Pr = Probability.
                          NbConfig(State)
   = Probability that in this State we have  "Cell=k".

--> It is possible to loop over the "NbConfigInfo(State)" possible configurations of the cells "With_Info" for a given State. Doing this allow to compute the values defined in the previous formulas. There are seldom more than 50'000 such configurations.

For each of these configurations we can count the number of bombs  bi  among the cells "With_Info", and thus deduce the number of bombs  bwi=bt-bv-bi  among the cells "Without_Info".

Usually the State will be such that no Unvisited cell has no bomb for sure.

The Best wining strategy :
Easy to say, impossible to do really :
For each cell, compute the probability to win the game if clicking on it, and then click on one having the highest probability.

Let's define :
PrWin(State) = probability to win from this State and playing optimally.
PrWin(Cell | State) = probability to win if clicking on this Cell and playing optimally.

We have :

PrWin(Cell | State) = Sum k=0..8 of
   Pr(Cell=k | State) * PrWin(NextState(State, Cell, k))

PrWin(State) = Maximum over all cells of PrWin(Cell | State)
PrWin(State without Unvisited cells) = 1.

This Is a highly recursive formula, but could be used in principle. It would just take too much time to be computed practically.
We saw how to compute Pr(Cell=k | State).

If we make the hypothesis that  PrWin(NextState(State, Cell, k)) has the same value for all cells and k=0 to 8, then : PrWin(Cell) = Pr(Cell <> -1) * constant.  Thus clicking on a cell having the lowest probability to contain a bomb is optimal.

In reality, the hypothesis is not right, but by experience, it is very near from the reality.

A first strategy is to click on a cell with minimum probability to contain a bomb. It is already a very good strategy.

A second strategy would be to use the formula and the hypothesis that PrWin(NextState(NextState(State, Cell_1, k_1), Cell_2, k_2) is independent of Cell_1, k_1, Cell_2 and k_2 This would be realisable.
This would lead to the realisable algorithm :

PrWin(Cell_2 | NextState(State, Cell_1, k_1)) = Sum k_2=0..8 of
   Pr(Cell_2=k_2 | NextState(State, Cell_1, k_1)) * constant
  = Pr(Cell_2 >= 0 | NextState(State, Cell_1, k_1)) * constant

PrWin(NextState(State, Cell_1, k_1)) =
   Maximum over all Cell_2 of 
      PrWin(Cell_2 | NextState(State, Cell_1, k_1))

PrWin(Cell_1 | State) = Sum k_1=0..8 of
   Pr(Cell_1=k_1 | State) * PrWin(NextState(State, Cell_1, k_1))

PrWin(State) = Maximum over all Cell_1 of PrWin(Cell_1 | State)

A  Cell_1  which reach the maximum would be chosen.

Another algorithm, which can be used if the number of possible configurations compatible with the actual State is not too high.
NbLostConfig(State) = Number of loosing configurations of the given State, playing an optimal strategy.

We Have :
NbLostConfig(State) = Minimum over all Unvisited cells of the Sum for k=-1 to 8 of
    NbLostConfig(NextState(State, Cell, k))
NbLostConfig(NextState(State, Cell, -1)) = NbConfig(State, Cell, -1)
NbLostConfig(NextState(State, Cell, k)) = 0  If  k>=0  and  NbConfig(State, Cell, k) <= 1

If  NbConfig(State, Cell, -1) = 0  then this Cell reach the minimum, i.e. 
If the Cell has no bomb for every configurations then :
NbLostConfig(State) = Sum for k=-1 to 8 of  NbLostConfig(NextState(State, Cell, k))

Otherwise we can try to restrict to compute the minimum over cells having a lower probability to have a bomb.

In the program, I defined a "function NbLostConfig" which, for a given Cell, makes partitions of the configurations such that the number in the Cell is the same in a partition. Then it computes itself recursively. But no improvement has been noticed. And computation time can increase a lot.

Another try to select the right cell where to click on is minimising the probability to click on a bomb not only in the next click, but in the next two or next three clicks.

The algorithm to minimise clicking on a bomb in two clicks would be :
First compute for each couple of cells (Cell1, Cell2), 
Pr(Cell1=k1) and Pr(Cell1=k1 and Cell2=-1)

Then select the cell Cell1 to click on, which minimises :

Pr(Cell1=-1) + (1 - Pr(Cell1=-1)) * Sum for k1=0 to 8 such that Pr(Cell1=k1) > 0 of
minimum over all Cell2 of  Pr(Cell1=k1 and Cell2=-1) / Pr(Cell1=k1)

The algorithm to minimise clicking on a bomb in three clicks would be :
First compute for each triples of cells (Cell1, Cell2, Cell3), 
Pr(Cell1=k1),  Pr(Cell1=k1 and Cell2=k2)  and  Pr(Cell1=k1 and Cell2=k2 and Cell3=-1)

Then select the cell Cell1 to click on, which minimises :

Pr(Cell1=-1) + (1 - Pr(Cell1=-1)) * Sum for k1=0 to 8 such that Pr(Cell1=k1) > 0 of
minimum over all Cell2 of              Sum for k2=0 to 8 such that Pr(Cell1=k1 and Cell2=k2) > 0 of
Pr(Cell1=k1 and Cell2=k2 and Cell3=-1) / Pr(Cell1=k1 and Cell2=k2)

It is realisable.
If knowing that  Cell1=k1  implies that there exist a cell without bomb, then
minimum over all Cell2 of  Pr(Cell1=k1 and Cell2=-1) / Pr(Cell1=k1) 
would be equal to zero.

Some Results :
In the mode : Beginner, 8x8 with 10 bombs,
Letting the computer play over 100'000 games, I can deduce that the probability to win a game 0.802  with an incertitude of about 0.001 on this number.
Thus there are slightly more than  80%  chances to win a game in the Beginner's mode.

In the mode : Intermediate, 16x16 with 40 bombs,
Letting the computer play over 100'000 games, I can deduce that the probability to win a game 0.761  with an incertitude of about 0.001 on this number.
Thus there are slightly more than  76%  chances to win a game in the Intermediate mode.

In the mode : Expert, 30x16 with 99 bombs,
Letting the computer play over 50'000 games, I can deduce that the probability to win a game 0.370  with an incertitude of about 0.0015 on this number.
Thus there are about  37%  chances to win a game in the Expert mode.

I tried during one week to do some little improvements, corrected some errors, but these number never changed more than 0.005 on runs of over 20'000 games.
 
Idea to let somebody define a starting strategy.
In the file  "ClienEn.msg" could be defined cells on which to click, under some conditions.
Condition => cell to click on.
The condition would be :
Nb_Cells_Visited, (nX nY nValue), (nX nY nValue), ... (nX nY nValue) => (nXClick, nYClick)

Negative values for nX would mean cell starting from the right
Negative values for nY would mean cell starting from the bottom

Example of a starting strategy description.
0 => (1 1)  # first click on the cell (1,1)
1 (1 1 1) => (1 -1)  # if 1 cell  visited and cell(1,1) = 1 then click on the bottom left cell
1 (1 1 2) => (1 -1)  # if 1 cell  visited and cell(1,1) = 2 then click on the bottom left cell
1 (1 1 3) => (1  3)  # if 1 cell  visited and cell(1,1) = 3 then click on cell(1 3)
2 (1 3 1) => (1 -1)  # if 2 cells visited and cell(1,3) = 1 then click on the bottom left cell
2 (1 3 2) => (1 -1)  # if 2 cells visited and cell(1,3) = 2 then click on the bottom left cell
2 (1 -1 1) => (-1 1)  # if 2 cells visited and cell(1,-1) = 1 then click on the top right cell
2 (1 -1 2) => (-1 1)
2 (1 -1 3) => (1 -3)  # if 2 cells visited and cell(1,-1) = 3 then click on the left 3rd from bottom cell
3 (1 -1 1) => (-1 1)
4 (1 1 0), (1 2 1), (2 1 1), (2 2 2) => (3 3) # here we know that cell(3 3) has no bombs
4 (1 1 0), (2 1 2), (2 2 2) => (1 3), (2 3), (3 3) # here we know that they have no bombs
   # we know that Cell(1 2) = 0
5 (1 1 0), (1 2 1), (2 1 1), (2 2 2), (3 3 1) => (4 4)

etc.

Here are some initial states : (* => has no bomb for sure,  b=has a bomb for sure)
1     2     3b     
            bb

01    01    01    01b    01
12    12    12    12**   23
  1     2     3   b*0*   bb
                   ***     
                           
02b   02b   02b   02b    00*
02b   13b   14b   25b    22*
***     *     b   bbb    bb*

Written by Bernard Gisin the 26th of March 2002