This is a follow-up to the question: Calculating odds of Minesweeper is this correct?
I was given good advice & answers pointed out some flaws in my calculation. However editing the original post would make the answers outdated.
I've only modified the board slightly, adding another number so that simplifying a section is not possible. I did this because I'd like to ensure my calculation can apply to any board & makes sense in doing so.
N = number of mines = 25
T = number of unidentified squares = 123
As you can see I've broken up the board into colored groups based on having identical odds so that It isn't necessary to calculate each square individually. For example, 'A', 'B', 'F' & 'I' are all touching a '3'. There is no reason 'A' would have different odds than 'B' 'F' or 'I'.
I will split the squares into 2 sections:
Section1 – Left marked section (ABFI, MNO, K…)
Section2 – Right marked section (PTV,QRWX,SUY)
Seciton3 – All the unknown squares. These are all the blank grey squares
Based on the numbers we know that:
Section1 + Section2 must have a sum of: 5, 6, 7 or 8 mines.
Section3 must have the rest, being: 20, 19, 18, or 17 mines.
I'll refer to what we know as 'Rules'. We know the total number of mines surrounding a '1' must equal '1'.
Rules:
ColorGroups # of bombs in ColorGroups
----------- ----------------------------
(A+B+F+I) + (C) + (G) + (J) = 3
(D+E+H+L) (C) + (G) + (K) = 1
(M+N+O) + (J) + (K) + (G) = 1
(P+T+V) + (RXWQ) = 2
(S+U+Y) + (RXWQ) = 1
Now, for the left side (Section1), we can get all the solutions by making assumptions. For example, if we assume ABFI = 3 than C, G & J must all be 0 since we have a rule: ABFI + C + G + J = 3. We will do the same for the right side (Section2) afterwards.
Assume (C) has 1 bomb. In other words, the 'C' square is a bomb. (C is chosen at random, but I prefer to start with a small section). I'll call the first solution 'S1-01-01':
Keep in mind a square can have a 1 or a 0. So (A+B+F+I) could have a max of 4 (ignoring the '3') & (C) can have a max of 1
Solutions
(S1-01-01)
Grouping # of bombs
-------- -----------
(C) = 1
(D+E+H+L) = 0
(K) = 0
(G) = 0
(J) = 1
(M+N+O) = 0
(A+F+I+B) = 1
(S1-01-02)
Grouping # of bombs
---- ----------
(C) = 1
(D+E+H+L) = 0
(K) = 0
(G) = 0
(J) = 0
(M+N+O) = 1
(A+F+I+B) = 2
That's all for C = 1, so next we assume G=1:
S1-02-01 # of bombs
-------- ----------
(C) = 0
(G) = 1
(D+E+H+L) = 0
(K) = 0
(M+N+O) = 0
(J) = 0
(A+F+I+B) = 2
S1-02-02
--------
(C) = 0
(G) = 0
(J) = 1
(A+F+I+B) = 2
(M+N+O) = 0
(D+E+H+L) = 1
(K) = 0
S1-02-03
--------
(C) = 0
(G) = 0
(J) = 0
(K) = 1
(D+E+H+L) = 0
(A+F+I+B) = 3
(M+N+O) = 0
S1-02-04
--------
(C) = 0
(G) = 0
(J) = 0
(K) = 0
(D+E+H+L) = 1
(A+F+I+B) = 3
(M+N+O) = 1
Doing the same for the right Section:
S2-01-01:
---------
(R+X+W+Q) = 1
(S+U+Y) = 0
(P+T+V) = 1
S2-02-01:
---------
(RXWQ) = 0
(S+U+Y) = 1
(P+T+V) = 2
Now we list the number of bombs in every solution:
Section1
#: S1-11 S1-12 S1-21 S1-12 S1-23 S1-24
----- ----- ----- ----- ----- ----- ------
ABFI: 1 2 2 2 3 3
C: 1 1 0 0 0 0
DEHL: 0 0 0 1 0 1
G: 0 0 1 0 0 0
J: 1 0 0 1 0 0
K: 0 0 0 0 1 0
MNO: 0 1 0 0 0 1
TOTALS: 3 4 3 4 4 5
Section2
#: S2-11 S2-21
----- ----- -----
RXWQ: 1 0
SUY: 0 1
PTV: 1 2
TOTALS: 2 3
Now we calculate the number of cases possible for every solution. This is done by using nCr (Binomial coefficient).
Where N = Number of Squares and B = numberOfBombs.
Combinations = N NCR B.
For the first solution (S1-1) these are the cases:
(ABFI) = 4 NCR 1 = 4
(C) = 1 NCR 1 = 1
(DEHL) = 4 NCR 0 = 1
(G) = 1 NCR 0 = 1
(J) = 1 NCR 1 = 1
(K) = 0 NCR 1 = 1
(MNO) = 3 NCR 0 = 1
Multiplying these combinations we get: 4*1*1*1*1*1*1 = 4 cases for this solution (S1-1).
Doing the same for all solutions in the left section we get:
#: S1-11 S1-12 S1-21 S1-22 S1-23 S1-24
ABFI: 4 6 6 6 4 4
C: 1 1 1 1 1 1
DEHL: 1 1 1 4 1 4
G: 1 1 1 1 1 1
J: 1 1 1 1 1 1
K: 1 1 1 1 1 1
MNO: 1 3 1 1 1 3
TOTALS: 4 18 6 24 4 48
Total cases = 104
Note: In the above table, to get 'TOTALS' we multiply all combinations to get the total combinations for that solution.
Now for the right section:
#: S2-11 S2-21
RXWQ: 4 1
SUY: 1 3
PTV: 3 3
TOTALS: 12 9
Total cases = 21
To get the total cases we need to multiply these: 21 * 104 = 2184 total cases.
For clarification, here is an example of a complete solution (S1-11+S2-11):
ABFI: 1
C: 1
DEHL: 0
G: 0
J: 1
K: 0
MNO: 0
RXWQ: 1
SUY: 0
PTV: 1
TOTAL MINES: 5
TOTAL CASES: 16
Total cases is calculated by multiplying the binomial distribution for each group as we've done before
Notice that I've taken the first case for S1 and added the first case for S2. If I were to continue, I'd write the first case for S1 + the second for S2, then the second case for S1 + the first for S2.
These 2184 total cases do not hold equal weight. We know that there are 25 mines in the total & 123 unidentified squares. 25/123 = 0.20 mines per square. This means a case with 5 mines (the minimum) will have a different weight than a case with 8 mines (the maximum).
Credit to Joriki in this answer for the formula
$\binom{t-s}{m-n}\;.$
t = remaining unidentified squares (123)
m = remaining mines (25)
s = unidentified squares in case
n = mines assigned to case
Knowing that (Section1+Section) has 25 unidentified squares and may contain 5, 6, 7 or 8 mines we assign the weights:
W1 (5 mines): $\binom{123-25}{25-5}\;$ = $\binom{98}{20}\;$
W2 (6 mines): $\binom{123-25}{25-6}\;$ = $\binom{98}{19}\;$
W3 (7 mines): $\binom{123-25}{25-7}\;$ = $\binom{98}{18}\;$
W4 (8 mines): $\binom{123-25}{25-8}\;$ = $\binom{98}{17}\;$
Before we carry on lets put our 2 sections into 1 "FullSection". We do this by "Multiplying" section2 & section1. By that I mean, for every solution in Section1, add every solution in Section2.
Section1 has 6 solutions with total mines of: 3, 4, 3, 4, 4, 5.
Section2 has 5 solutions with total mines of: 2, 3
'Full Solutions Table' (The section # isn't really important)
Full Section # # of mines # of cases
-------------- ---------- ----------
1 6 36
2 6 216
3 7 576
4 5 72
5 7 36
6 6 48
7 6 54
8 5 48
9 6 288
10 7 162
11 7 216
12 8 432
Total cases: 2184
For every solution, we will tally up how many times 5, 6, 7 & 9 mines are the sum:
Cases with 5 mines: 120
Cases with 6 mines: 642
Cases with 7 mines: 990
Cases with 8 mines: 432
The sum of the weights (Using W1 – W4 depending on number of mines):
(120 * $\binom{123-25}{25-5}\;$) + (642 * $\binom{123-25}{25-6}\;$) + (990 * $\binom{123-25}{25-7}\;$) + (432 * $\binom{123-25}{25-8}\;$)
Sum of weights = 1.190143e+23
So given any case, say one with 5 mines in it, the probability will be:
$\binom{123-25}{25-5}\;$ / 1.190143e+23 = 0.00287497486
Doing the same with 5, 6, 7, 8
5 = 0.00287497486
6 = 0.00072784173
7 = 0.00017286241
8 = 0.00003841386
Since there are 120 cases with 5 mines:
120 * 0.00287497486 = 0.3449969832
Again doing the same with 5, 6, 7, 8:
5 = 0.345
6 = 0.467
7 = 0.171
8 = 0.017
Sum: 1
We will be applying the single weight to every case, but I just wanted to ensure the sum is = 1
Applying these weights, we can create a table where the weight is based on the W for number of mines, multiplied by the number of cases and the value under each coloured group for the section represents the odds per square.
E.G: for S1, the number of mines is 6 and there are 36 cases. The green section is 4 squares in length and contains 1 mine so:
0.00072784173 * 36 = 0.02620230228
(1/4) * 0.02620230228 = 0.02620230228
Results:
S# Mine Count # of cases weight (C) (DEHL) (K) (G) (J) (MNO) (AFIB) (RXWQ) (SUY) (PTV)
--- ---------- ---------- ------------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
1 6 36 0.02620230228 0.02620230 0.00000000 0.00000000 0.00000000 0.02620230 0.00000000 0.00655058 0.00000000 0.00873410 0.01746820
2 6 216 0.15721381368 0.15721381 0.00000000 0.00000000 0.00000000 0.00000000 0.05240460 0.07860691 0.03930345 0.00000000 0.05240460
3 7 576 0.09956874816 0.00000000 0.02489219 0.00000000 0.00000000 0.00000000 0.03318958 0.07467656 0.02489219 0.00000000 0.03318958
4 5 72 0.20699818992 0.00000000 0.00000000 0.00000000 0.20699819 0.00000000 0.00000000 0.10349909 0.05174955 0.00000000 0.06899940
5 7 36 0.00622304676 0.00000000 0.00000000 0.00622305 0.00000000 0.00000000 0.00000000 0.00466729 0.00000000 0.00207435 0.00414870
6 6 48 0.03493640304 0.00000000 0.00000000 0.03493640 0.00000000 0.00000000 0.00000000 0.02620230 0.00873410 0.00000000 0.01164547
7 6 54 0.03930345342 0.00000000 0.00000000 0.00000000 0.03930345 0.00000000 0.00000000 0.01965173 0.00000000 0.01310115 0.02620230
8 5 48 0.13799879328 0.13799879 0.00000000 0.00000000 0.00000000 0.13799879 0.00000000 0.03449970 0.03449970 0.00000000 0.04599960
9 6 288 0.20961841824 0.00000000 0.05240460 0.00000000 0.00000000 0.20961842 0.00000000 0.10480921 0.05240460 0.00000000 0.06987281
10 7 162 0.02800371042 0.02800371 0.00000000 0.00000000 0.00000000 0.00000000 0.00933457 0.01400186 0.00000000 0.00933457 0.01866914
11 7 216 0.03733828056 0.00000000 0.00933457 0.00000000 0.00000000 0.03733828 0.00000000 0.01866914 0.00000000 0.01244609 0.02489219
12 8 432 0.01659478752 0.00000000 0.00414870 0.00000000 0.00000000 0.00000000 0.00553160 0.01244609 0.00000000 0.00553160 0.01106319
Totals: 0.99999995 0.34941862 0.09078006 0.04115945 0.24630164 0.41115779 0.10046035 0.49828045 0.21158359 0.05122186 0.38455518
Looking at the result table we can see that any blue square (MNO) has the least chances of being a mine and any green square (AFIB) has the greatest chances of having a mine.
The results seems reasonable, but is it correct?
Best Answer
Everything seems basically OK now; the final result table seems to be correct. There are some minor isolated errors that don't seem to have affected anything else:
In your "example of a complete solution (S1-11+S2-11)", it should be $12\cdot4=48$ total cases, not $12+4=16$.
In the calculation immediately above "Results:", $(1/4)\cdot0.02620230228=0.02620230228$, the right-hand side isn't divided by $4$.
And in your summary of the results, I don't see why you say that MNO have the lowest marginal probability of containing a mine; from the table it's K with about $0.04$, and DEHL and SUY also have lower marginal mine probabilities than MNO with about $0.1$.
By the way, a good check for the results (that checks out) is to compute the expected total number of mines once by adding the marginal mine probabilities for all squares and once from the marginal probabilities of the total mine counts $5$ through $8$. The expected total mine count in the $25$ coloured squares is about $5.86$.