Analyzing Minesweeper Probabilities

Question

Calculating probabilities in Minesweeper might sound like an easy task, but I've seen so many probability calculators that's either incorrect, horribly slow, or with ugly code (or all of them) so I have to share my code for this.

This code is used within my Minesweeper Flags online game by the AIs AI_Hard, AI_Extreme3 and AI_Nightmare.

This code is written in Java 6, but don't let that scare you away. It would not be too difficult to update to more modern Java versions.

So, how does it work?

Small Minesweeper Board

Let's say this board has 6 mines. A simple approach would be to recursively place all 6 mines and count the number of combinations where each field has a mine. Although that would work for a small board like this, for a bigger board with the same pattern and 51 mines, that's not optimal.

So, what if you just place the mines around the 1 and the 3 and use combinatorics for the rest of the board where we don't have any clues? That would help with the bigger board with the same pattern, but what if you have plenty of clues distributed around the board like this, that's where things are starting to get too complex and too slow for most algorithms.

###My approach

I will explain my approach by guiding you through a manual calculation of the 4x4 example board above.

Board representation. This board can be represented like:

abcd
e13f
ghij
klmn

---

Rules. So we have a 1 and a 3 and we know there are 6 mines in total on the board. This can be represented as:

a+b+c+e+g+h+i = 1
b+c+h+i+d+f+j = 3
a+b+c+d+e+f+g+h+i+j+k+l+m+n = 6

This is what I call rules (the FieldRule class in my code)

---

Field Groups. By grouping fields into which rules they are in, it can be refactored into:

(a+e+g) + (b+c+h+i) = 1
(b+c+h+i) + (d+f+j) = 3
(a+e+g) + (b+c+h+i) + (d+f+j) + (k+l+m+n) = 6

These groups I call Field Groups (The FieldGroup class in the code)

---

The RootAnalyzeImpl class stores a collection of rules, and when it is getting solved it begins by splitting the fields into groups, then creates a GameAnalyze object to do the rest of the work.

GameAnalyze. It starts by trying to simplify things (we'll come to that later), when it can't do so any more it picks a group and assign values to it. Here I pick the (a+e+g) group. I find that it's best to start with a small group.

---

(a+e+g) = 0 is chosen and a new instance of GameAnalyze is created, which adds (a+e+g) = 0 to its knownValues.

Simplify (FieldRule.simplify method). Now we remove groups with a known value and try to deduce new known values for groups.

(a+e+g) + (b+c+h+i) = 1

(a+e+g) is known, so (b+c+h+i) = 1 remains which makes the rule solved. (b+c+h+i) = 1 is added to knownValues. Next rule:

(b+c+h+i) + (d+f+j) = 3

(b+c+h+i) = 1 is known so we have left (d+f+j) = 2, making also this rule solved and another FieldGroup known. Last rule:

(a+e+g) + (b+c+h+i) + (d+f+j) + (k+l+m+n) = 6

The only unknown remaining here is (k+l+m+n) which after removing the other groups has to have the value 3, because (a+e+g) + (b+c+h+i) + (d+f+j) = 0 + 1 + 2.

---

Solution So what we know is:

(a+e+g) = 0
(b+c+h+i) = 1
(d+f+j) = 2
(k+l+m+n) = 3

As all rules have been solved and all groups have a value, this is known as a solution (Solution class).

---

Doing the same for (a+e+g) = 1 leads, after simplification to another solution:

(a+e+g) = 1
(b+c+h+i) = 0
(d+f+j) = 3
(k+l+m+n) = 6 - 3 - 1 = 2

---

Solution combinations. Now we have two solutions where all the groups have values. When a solution is created, it calculates the combinations possible for that rule. This is done by using nCr (Binomial coefficient).

For the first solution we have:

(a+e+g) = 0 --> 3 nCr 0 = 1 combination
(b+c+h+i) = 1 --> 4 nCr 1 = 4 combinations
(d+f+j) = 2 --> 3 nCr 2 = 3 combinations
(k+l+m+n) = 3 --> 4 nCr 3 = 4 combinations

Multiplying these combinations we get 143*4 = 48 combinations for this solution.

As for the other solution:

(a+e+g) = 1 --> 3 nCr 1 = 3
(b+c+h+i) = 0 --> 4 nCr 0 = 1
(d+f+j) = 3 --> 3 nCr 3 = 1
(k+l+m+n) = 2 --> 4 nCr 2 = 6

311*6 = 18 combinations.

So a total of 48 + 18 = 66 combinations.

---

Probabilities The total combinations where a field in the (k+l+m+n) group is a mine is:

In first solution: 3 mines, 4 fields, 48 combinations for the solution.
In second solution: 2 mines, 4 fields, 18 combinations in solution.

\3ドル/4 * 48 + 2/4 * 18 = 45\$

To calculate the probability we take this value divided by the total combinations of the entire board and we get: \45ドル / 66 = 0.681818181818\$

Common problems in other algorithms:

• They treat the "global rule" in a special way, instead of treating it just like another rule
• They treat fields individually instead of bunching them up into FieldGroups

This leads to most algorithms being unable to solve The Super board of death in reasonable time. My approach? About four seconds. (I'm not kidding!)

###Class Summary

Not included here, some of them will be posted for review separately

• Combinatorics.java: Contains methods for combinatorics.
• FieldGroupSplit.java: A static method and a class to store the result for separating field groups.
• RuntimeTimeoutException.java: An exception extending RuntimeException
• RootAnalyze.java: Just an interface that RootAnalyzeImpl implements.
• SimplifyResult.java: Enum for the result of FieldRule.simplify
• SolvedCallback.java: Interface for letting GameAnalyze inform whenever it has found a solution

Included below

• FieldGroup.java: A collection of fields. As fields is a generic type, it can be MinesweeperField, String, or whatever.
• FieldRule.java: A rule, consisting of a number of FieldGroups that equals a number
• GroupValues.java: For assigning values to FieldGroups. Map<FieldGroup, Integer>
• RootAnalyzeImpl.java: Where it all begins. Contains a set of rules that should be solved. Also used to access the results when solve is completed.
• GameAnalyze.java: For branching and recursively solving and trying values to groups.
• Solution.java: Stores a way of assigning all the groups.

All the code can be found at http://github.com/Zomis/Minesweeper-Analyze

#Code

FieldGroup.java: (51 lines, 1158 bytes)

/**
 * A group of fields that have common rules
 * 
 * @author Simon Forsberg
 * @param <T> The field type
 */
public class FieldGroup<T> extends ArrayList<T> {
 private static final long serialVersionUID = 4172065050118874050L;
 
 private double probability = 0;
 private int solutionsKnown = 0;
 
 public FieldGroup(Collection<T> fields) {
 super(fields);
 }
 
 public double getProbability() {
 return this.probability;
 }
 
 public int getSolutionsKnown() {
 return this.solutionsKnown;
 }
 void informAboutSolution(int rValue, Solution<T> solution, double total) {
 if (rValue == 0)
 return;
 this.probability = this.probability + solution.nCr() / total * rValue / this.size();
 this.solutionsKnown++;
 }
 
 public String toString() {
 if (this.size() > 8) {
 return "(" + this.size() + " FIELDS)";
 }
 
 StringBuilder str = new StringBuilder();
 for (T field : this) {
 if (str.length() > 0)
 str.append(" + ");
 str.append(field);
 }
 return "(" + str.toString() + ")";
 }
 
}

FieldRule.java: (201 lines, 5326 bytes)

/**
 * A constraint of a number of fields or {@link FieldGroup}s that should have a specific sum
 * 
 * @author Simon Forsberg
 * @param <T> Field type
 */
public class FieldRule<T> {
 
 private final T cause;
 private final List<FieldGroup<T>> fields;
 private int result = 0;
 
 /**
 * Create a copy of an existing rule.
 * 
 * @param copyFrom Rule to copy
 */
 public FieldRule(FieldRule<T> copyFrom) {
 this.fields = new ArrayList<FieldGroup<T>>(copyFrom.fields); // Deep copy? Probably not. FieldGroup don't change much.
 this.result = copyFrom.result;
 this.cause = copyFrom.cause;
 }
 
 /**
 * Create a rule from a list of fields and a result (create a new FieldGroup for it)
 * 
 * @param cause The reason for why this rule is added (optional, may be null)
 * @param rule Fields that this rule applies to
 * @param result The value that should be forced for the fields
 */
 public FieldRule(T cause, Collection<T> rule, int result) {
 this.fields = new ArrayList<FieldGroup<T>>();
 this.fields.add(new FieldGroup<T>(rule));
 this.result = result;
 this.cause = cause;
 }
 
 FieldRule(T cause, FieldGroup<T> group, int result) {
 this.cause = cause;
 this.fields = new ArrayList<FieldGroup<T>>();
 this.fields.add(group);
 this.result = result;
 }
 
 boolean checkIntersection(FieldRule<T> rule) {
 if (rule == this)
 return false;
 
 List<FieldGroup<T>> fieldsCopy = new ArrayList<FieldGroup<T>>(fields);
 List<FieldGroup<T>> ruleFieldsCopy = new ArrayList<FieldGroup<T>>(rule.fields);
 
 for (FieldGroup<T> groupA : fieldsCopy) {
 for (FieldGroup<T> groupB : ruleFieldsCopy) {
 if (groupA == groupB)
 continue;
 
 FieldGroupSplit<T> splitResult = FieldGroupSplit.split(groupA, groupB);
 if (splitResult == null)
 continue; // nothing to split
 
 FieldGroup<T> both = splitResult.getBoth();
 FieldGroup<T> onlyA = splitResult.getOnlyA();
 FieldGroup<T> onlyB = splitResult.getOnlyB();
 
 this.fields.remove(groupA);
 this.fields.add(both);
 if (!onlyA.isEmpty()) { 
 this.fields.add(onlyA);
 }
 
 rule.fields.remove(groupB);
 rule.fields.add(both);
 if (!onlyB.isEmpty()) { 
 rule.fields.add(onlyB);
 }
 return true;
 }
 }
 return false;
 }
 
 public T getCause() {
 return this.cause;
 }
 public Collection<FieldGroup<T>> getFieldGroups() {
 return new ArrayList<FieldGroup<T>>(this.fields);
 }
 
 public int getFieldsCountInGroups() {
 int fieldsCounter = 0;
 for (FieldGroup<T> group : fields) {
 fieldsCounter += group.size();
 }
 return fieldsCounter;
 }
 
 public int getResult() {
 return this.result;
 }
 
 public FieldGroup<T> getSmallestFieldGroup() {
 if (this.fields.isEmpty())
 return null;
 
 FieldGroup<T> result = this.fields.get(0);
 for (FieldGroup<T> group : this.fields) {
 if (group.size() < result.size()) {
 result = group;
 }
 }
 return result;
 }
 
 public boolean isEmpty () {
 return fields.isEmpty() && result == 0;
 }
 public double nCr() {
 if (this.fields.size() != 1)
 throw new IllegalStateException("Rule has more than one group.");
 return Combinatorics.nCr(this.getFieldsCountInGroups(), this.result);
 }
 public SimplifyResult simplify(Map<FieldGroup<T>, Integer> knownValues) {
 if (this.isEmpty()) {
 return SimplifyResult.NO_EFFECT;
 }
 
 Iterator<FieldGroup<T>> it = fields.iterator();
 int totalCount = 0;
 while (it.hasNext()) {
 FieldGroup<T> group = it.next();
 Integer known = knownValues.get(group);
 if (known != null) {
 it.remove();
 result -= known;
 }
 else totalCount += group.size();
 }
 
 // a + b + c = -2 is not a valid rule.
 if (result < 0) {
 return SimplifyResult.FAILED_NEGATIVE_RESULT;
 }
 
 // a + b = 42 is not a valid rule
 if (result > totalCount) {
 return SimplifyResult.FAILED_TOO_BIG_RESULT;
 }
 
 // (a + b) = 1 or (a + b) = 0 would give a value to the (a + b) group and simplify things.
 if (fields.size() == 1) {
 knownValues.put(fields.get(0), result);
 fields.clear();
 result = 0;
 return SimplifyResult.SIMPLIFIED;
 }
 
 // (a + b) + (c + d) = 0 would give the value 0 to all field groups and simplify things
 if (result == 0) {
 for (FieldGroup<T> field : fields) {
 knownValues.put(field, 0);
 }
 fields.clear();
 result = 0;
 return SimplifyResult.SIMPLIFIED;
 }
 
 // (a + b) + (c + d) = 4 would give the value {Group.SIZE} to all Groups.
 if (totalCount == result) {
 for (FieldGroup<T> field : fields) {
 knownValues.put(field, result * field.size() / totalCount);
 }
 return SimplifyResult.SIMPLIFIED;
 }
 return SimplifyResult.NO_EFFECT;
 }
 @Override
 public String toString() {
 StringBuilder rule = new StringBuilder();
 for (FieldGroup<T> field : this.fields) {
 if (rule.length() > 0) {
 rule.append(" + ");
 }
 rule.append(field.toString());
 }
 rule.append(" = ");
 rule.append(result);
 return rule.toString(); 
 }
}

GameAnalyze.java: (85 lines, 2276 bytes)

public class GameAnalyze<T> {
 private final SolvedCallback<T> callback;
 private final GroupValues<T> knownValues;
 private final List<FieldRule<T>> rules;
 
 GameAnalyze(GroupValues<T> knownValues, List<FieldRule<T>> unsolvedRules, SolvedCallback<T> callback) {
 this.knownValues = knownValues == null ? new GroupValues<T>() : new GroupValues<T>(knownValues);
 this.rules = unsolvedRules;
 this.callback = callback;
 }
 
 private void removeEmptyRules() {
 Iterator<FieldRule<T>> it = rules.iterator();
 while (it.hasNext()) {
 if (it.next().isEmpty())
 it.remove();
 }
 }
 
 private boolean simplifyRules() {
 boolean simplifyPerformed = true;
 while (simplifyPerformed) {
 simplifyPerformed = false;
 for (FieldRule<T> ruleSimplify : rules) {
 SimplifyResult simplifyResult = ruleSimplify.simplify(knownValues);
 if (simplifyResult == SimplifyResult.SIMPLIFIED) {
 simplifyPerformed = true;
 }
 else if (simplifyResult.isFailure()) {
 return false;
 }
 }
 }
 return true;
 }
 
 void solve() {
 if (Thread.interrupted())
 throw new RuntimeTimeoutException();
 
 if (!this.simplifyRules()) {
 return;
 }
 
 this.removeEmptyRules();
 this.solveRules();
 
 if (this.rules.isEmpty()) {
 callback.solved(Solution.createSolution(this.knownValues));
 }
 }
 
 private void solveRules() {
 if (this.rules.isEmpty())
 return;
 
 FieldGroup<T> chosenGroup = this.rules.get(0).getSmallestFieldGroup();
 if (chosenGroup == null) {
 throw new IllegalStateException("Chosen group is null.");
 }
 if (chosenGroup.size() == 0) {
 throw new IllegalStateException("Chosen group is empty. " + chosenGroup);
 }
 
 for (int i = 0; i <= chosenGroup.size(); i++) {
 GroupValues<T> mapCopy = new GroupValues<T>(this.knownValues);
 mapCopy.put(chosenGroup, i);
 
 List<FieldRule<T>> rulesCopy = new ArrayList<FieldRule<T>>(); // deep copy!
 for (FieldRule<T> rule : this.rules) {
 rulesCopy.add(new FieldRule<T>(rule));
 }
 new GameAnalyze<T>(mapCopy, rulesCopy, this.callback).solve();
 }
 }
 
}

GroupValues.java: (32 lines, 687 bytes)

public class GroupValues<T> extends HashMap<FieldGroup<T>, Integer> {
 private static final long serialVersionUID = -107328884258597555L;
 private int bufferedHash = 0;
 
 public GroupValues(GroupValues<T> values) {
 super(values);
 }
 public GroupValues() {
 super();
 }
}

RootAnalyzeImpl.java: (267 lines, 7690 bytes)

public class RootAnalyzeImpl<T> implements SolvedCallback<T>, RootAnalyze<T> {
 private final List<FieldGroup<T>> groups = new ArrayList<FieldGroup<T>>();
 private final List<FieldRule<T>> originalRules = new ArrayList<FieldRule<T>>();
 private final List<FieldRule<T>> rules = new ArrayList<FieldRule<T>>();
 private final List<Solution<T>> solutions = new ArrayList<Solution<T>>();
 
 private double total;
 private boolean solved = false;
 
 @Override
 public double getTotal() {
 return this.total;
 }
 
 private RootAnalyzeImpl(Solution<T> known) {
 for (Entry<FieldGroup<T>, Integer> sol : known.getSetGroupValues().entrySet()) {
 this.rules.add(new FieldRule<T>(null, sol.getKey(), sol.getValue()));
 }
 }
 public RootAnalyzeImpl() {}
 
 public void addRule(FieldRule<T> rule) {
 this.rules.add(rule);
 }
 
 /**
 * Get the list of simplified rules used to perform the analyze
 * 
 * @return List of simplified rules
 */
 @Override
 public List<FieldRule<T>> getRules() {
 return new ArrayList<FieldRule<T>>(this.rules);
 }
 
 @Override
 public FieldGroup<T> getGroupFor(T field) {
 for (FieldGroup<T> group : this.groups) {
 if (group.contains(field)) {
 return group;
 }
 }
 return null;
 }
 
 /**
 * Return a random solution that satisfies all the rules
 * 
 * @param random Random object to perform the randomization
 * @return A list of fields randomly selected that is guaranteed to be a solution to the constraints
 * 
 */
 @Override
 public List<T> randomSolution(Random random) {
 if (random == null) {
 throw new IllegalArgumentException("Random object cannot be null");
 }
 
 List<Solution<T>> solutions = new LinkedList<Solution<T>>(this.solutions);
 if (this.getTotal() == 0) {
 throw new IllegalStateException("Analyze has 0 combinations: " + this);
 }
 
 double rand = random.nextDouble() * this.getTotal();
 Solution<T> theSolution = null;
 
 while (rand > 0) {
 if (solutions.isEmpty()) {
 throw new IllegalStateException("Solutions is suddenly empty. (This should not happen)");
 }
 theSolution = solutions.get(0);
 rand -= theSolution.nCr();
 solutions.remove(0);
 }
 
 return theSolution.getRandomSolution(random);
 }
 
 private RootAnalyzeImpl<T> solutionToNewAnalyze(Solution<T> solution, List<FieldRule<T>> extraRules) {
 Collection<FieldRule<T>> newRules = new ArrayList<FieldRule<T>>();
 for (FieldRule<T> rule : extraRules) { 
 // Create new rules, because the older ones may have been simplified already.
 newRules.add(new FieldRule<T>(rule));
 }
 RootAnalyzeImpl<T> newRoot = new RootAnalyzeImpl<T>(solution);
 newRoot.rules.addAll(newRules);
 return newRoot;
 }
 
 @Override
 public RootAnalyze<T> cloneAddSolve(List<FieldRule<T>> extraRules) {
 List<FieldRule<T>> newRules = this.getOriginalRules();
 newRules.addAll(extraRules);
 RootAnalyzeImpl<T> copy = new RootAnalyzeImpl<T>();
 for (FieldRule<T> rule : newRules) {
 copy.addRule(new FieldRule<T>(rule));
 }
 copy.solve();
 return copy;
 }
 
 /**
 * Get the list of the original, non-simplified, rules
 * 
 * @return The original rule list 
 */
 @Override
 public List<FieldRule<T>> getOriginalRules() {
 return this.originalRules.isEmpty() ? this.getRules() : new ArrayList<FieldRule<T>>(this.originalRules);
 }
 private double getTotalWith(List<FieldRule<T>> extraRules) {
 if (!this.solved)
 throw new IllegalStateException("Analyze is not solved");
 double total = 0;
 
 for (Solution<T> solution : this.getSolutions()) {
 RootAnalyzeImpl<T> root = this.solutionToNewAnalyze(solution, extraRules);
 root.solve();
 total += root.getTotal();
 }
 
 return total;
 }
 
 @Override
 public double getProbabilityOf(List<FieldRule<T>> extraRules) {
 if (!this.solved)
 throw new IllegalStateException("Analyze is not solved");
 return this.getTotalWith(extraRules) / this.getTotal();
 }
 
 @Override
 public List<Solution<T>> getSolutions() {
 if (!this.solved)
 throw new IllegalStateException("Analyze is not solved");
 return new ArrayList<Solution<T>>(this.solutions);
 }
 /**
 * Separate fields into field groups. Example <code>a + b + c = 2</code> and <code>b + c + d = 1</code> becomes <code>(a) + (b + c) = 2</code> and <code>(b + c) + (d) = 1</code>. This method is called automatically when calling {@link #solve()}
 */
 public void splitFieldRules() {
 if (rules.size() <= 1)
 return;
 
 boolean splitPerformed = true;
 while (splitPerformed) {
 splitPerformed = false;
 for (FieldRule<T> a : rules) {
 for (FieldRule<T> b : rules) {
 boolean result = a.checkIntersection(b);
 
 if (result) {
 splitPerformed = true;
 }
 }
 }
 }
 }
 
 
 public void solve() {
 if (this.solved) {
 throw new IllegalStateException("Analyze has already been solved");
 }
 
 List<FieldRule<T>> original = new ArrayList<FieldRule<T>>(this.rules.size());
 for (FieldRule<T> rule : this.rules) {
 original.add(new FieldRule<T>(rule));
 }
 this.originalRules.addAll(original);
 
 this.splitFieldRules();
 
 this.total = 0;
 
 new GameAnalyze<T>(null, rules, this).solve();
 
 for (Solution<T> solution : this.solutions) {
 solution.setTotal(total);
 }
 
 if (!this.solutions.isEmpty()) {
 for (FieldGroup<T> group : this.solutions.get(0).getSetGroupValues().keySet()) {
 // All solutions should contain the same fieldgroups.
 groups.add(group);
 }
 }
 this.solved = true;
 }
 
 @Override
 public List<FieldGroup<T>> getGroups() {
 if (!this.solved) {
 Set<FieldGroup<T>> agroups = new HashSet<FieldGroup<T>>();
 for (FieldRule<T> rule : this.getRules()) {
 agroups.addAll(rule.getFieldGroups());
 }
 return new ArrayList<FieldGroup<T>>(agroups);
 }
 
 List<FieldGroup<T>> grps = new ArrayList<FieldGroup<T>>(this.groups);
 Iterator<FieldGroup<T>> it = grps.iterator();
 while (it.hasNext()) {
 // remove empty fieldgroups
 if (it.next().isEmpty()) {
 it.remove(); 
 }
 }
 return grps;
 }
 @Override
 public List<T> getFields() {
 if (!this.solved) { 
 throw new IllegalStateException("Analyze is not solved");
 }
 
 List<T> allFields = new ArrayList<T>();
 for (FieldGroup<T> group : this.getGroups()) {
 allFields.addAll(group);
 }
 return allFields;
 }
 @Override
 public void solved(Solution<T> solved) {
 this.solutions.add(solved);
 this.total += solved.nCr();
 }
 @Override
 public List<T> getSolution(double solution) {
 if (Math.rint(solution) != solution || solution < 0 || solution >= this.getTotal()) {
 throw new IllegalArgumentException("solution must be an integer between 0 and total (" + this.getTotal() + ")");
 }
 if (solutions.isEmpty()) {
 throw new IllegalStateException("There are no solutions.");
 }
 
 List<Solution<T>> solutions = new ArrayList<Solution<T>>(this.solutions);
 Solution<T> theSolution = solutions.get(0);
 while (solution > theSolution.nCr()) {
 solution -= theSolution.nCr();
 solutions.remove(0);
 theSolution = solutions.get(0);
 }
 return theSolution.getCombination(solution);
 }
 
 @Override
 public Iterable<Solution<T>> getSolutionIteration() {
 return this.solutions;
 }
}

Solution.java: (135 lines, 3778 bytes)

/**
 * Represents a solution for a Minesweeper analyze.
 * 
 * @author Simon Forsberg
 * @param <T>
 */
public class Solution<T> {
 public static <T> Solution<T> createSolution(GroupValues<T> values) {
 return new Solution<T>(values).nCrPerform();
 }
 
 private static <T> double nCr(Entry<FieldGroup<T>, Integer> rule) {
 return Combinatorics.nCr(rule.getKey().size(), rule.getValue());
 }
 
 private double mapTotal;
 
 private double nCrValue;
 private final GroupValues<T> setGroupValues;
 
 private Solution(GroupValues<T> values) {
 this.setGroupValues = values;
 }
 private List<T> combination(List<Entry<FieldGroup<T>, Integer>> grpValues, double combination) {
 if (grpValues.isEmpty()) {
 return new LinkedList<T>();
 }
 
 grpValues = new LinkedList<Entry<FieldGroup<T>, Integer>>(grpValues);
 Entry<FieldGroup<T>, Integer> first = grpValues.remove(0);
 double remaining = 1;
 for (Entry<FieldGroup<T>, Integer> fr : grpValues) {
 remaining = remaining * nCr(fr);
 }
 
 double fncr = nCr(first);
 
 if (combination >= remaining * fncr) {
 throw new IllegalArgumentException("Not enough combinations. " + combination + " max is " + (remaining * fncr));
 }
 
 double combo = combination % fncr;
 List<T> list = Combinatorics.listCombination(combo, first.getValue(), first.getKey());
 if (!grpValues.isEmpty()) {
 List<T> recursive = combination(grpValues, Math.floor(combination / fncr));
 if (recursive == null) {
 return null;
 }
 list.addAll(recursive);
 }
 
 return list; 
 }
 
 public Solution<T> copyWithoutNCRData() {
 return new Solution<T>(this.setGroupValues);
 }
 public List<T> getCombination(double combinationIndex) {
 return combination(new LinkedList<Map.Entry<FieldGroup<T>,Integer>>(this.setGroupValues.entrySet()), combinationIndex);
 }
 
 public double getCombinations() {
 return this.nCrValue;
 }
 
 public double getProbability() {
 if (this.mapTotal == 0)
 throw new IllegalStateException("The total number of solutions on map is unknown");
 return this.nCrValue / this.mapTotal;
 }
 
 public List<T> getRandomSolution(Random random) {
 List<T> result = new ArrayList<T>();
 
 for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
 List<T> group = new ArrayList<T>(ee.getKey());
 Collections.shuffle(group, random);
 
 for (int i = 0; i < ee.getValue(); i++) {
 result.add(group.remove(0));
 }
 }
 
 return result;
 }
 
 public GroupValues<T> getSetGroupValues() {
 return new GroupValues<T>(setGroupValues);
 }
 public double nCr() {
 return this.nCrValue;
 }
 
 private Solution<T> nCrPerform() {
 double result = 1;
 for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
 result = result * Combinatorics.nCr(ee.getKey().size(), ee.getValue());
 }
 this.nCrValue = result;
 return this;
 }
 void setTotal(double total) {
 this.mapTotal = total;
 for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
 ee.getKey().informAboutSolution(ee.getValue(), this, total);
 }
 }
 @Override
 public String toString() {
 StringBuilder str = new StringBuilder();
 for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
 str.append(ee.getKey() + " = " + ee.getValue() + ", ");
 }
 str.append(this.nCrValue + " combinations (" + this.getProbability() + ")");
 return str.toString();
 }
}

#Usage / Test

Tests and usage can be found on GitHub. Especially see General2DTest.

#Questions

1. Even though this code is quite fast already, can it be made even faster? (Polynomial time anyone?)
2. Does another implementation of this exist? Can any libraries be used to calculate this?
3. Besides that, any general comments about this code and/or this approach?

• Marco Acierno: getGroups will call this.getRules which will create a new ArrayList with all rules of List<FieldRule<T>> rules = new ArrayList<FieldRule<T>>(); It's really needed to create a new copy everytime?
• Simon Forsberg: @MarcoAcierno I believe it's best practice to make a "defensive copy" so that it's not possible to call object.getRules().remove(xxx); and then you suddenly modified the original. Although there might be something there that can be simplified / made differently.
• Marco Acierno: What about wrap it inside a Collections.unmodifiableList ?
• Ben Aaronson: I believe minesweeper is NP hard
• Simon Forsberg: @BenAaronson You are correct, it is NP-hard, and NP-complete as well, which is exactly why I asked for a polynomial-time solution with a link to P-vs-NP ;) I believe that complexity-wise, this is as good as it's gonna get.

Answer 1

GroupValues

GroupValues doesn't seem to serve much of a purpose beyond what you get from Map; it adds no functionality beyond an unused field. In practice, all I think it is achieving is obscuring what is actually going on.

FieldGroup

That you are extending ArrayList, rather than composing with it, is a code smell. I find myself looking at informAboutSolution. There's a calculation there that doesn't make any sense if the list is empty. Furthermore, because you are publicly a list, anybody can come along and remove all of your entries, or insert more entries, or do all manner of silliness that would screw up your calculation.

I think you should tease out the running tally aspect of what's going on here. At a minimum....

void informAboutSolution(int rValue, Solution<T> solution, double total) {
 // codestyle: always use braces
 if (rValue == 0) {
 return;
 }
 double probabilityChange = solution.nCr() / total * rValue / fields.size();
 this.runningTally.update(probabilityChange);
}

This really needs better variable names - what are you really doing here? You are computing the probability that any cell in this group has a bomb, given a solution which allocates some number of bombs to the group.

class RunningTally {
 private double probability = 0;
 private int solutionsKnown = 0;
 public double getProbability() {
 return this.probability;
 }
 public int getSolutionsKnown() {
 return this.solutionsKnown;
 }
 public void update(double change) {
 probability += change;
 solutionsKnown++;
 }
}
void informAboutSolution(int bombsAllocated, Solution<T> solution, double total) {
 // codestyle: always use braces
 if (bombsAllocated == 0) {
 return;
 }
 int cellsAvailable = fields.size();
 double probabilityBombed = bombsAllocated / cellsAvailable;
 double solutionPercentage = solution.nCr() / total;
 double probabilityChange = solutionPercentage * probabilityBombed;
 runningTally.update(probabilityChange);
}

Allocating objects and doing work together is a code smell -- not necessarily wrong, but definitely suspicious. If you are concerned enough with string concatenation to think that a StringBuilder is a good idea, it probably makes sense to allow multiple objects to share the same StringBuilder.

void writeTo(StringBuilder str) {
 final String START_OBJECT = "(";
 final String END_OBJECT = ")";
 final String SEPARATOR = " + ";
 str.append(START_OBJECT);
 if (fields.size() > 8) {
 str.append(fields.size());
 str.append(" FIELDS");
 } else {
 final int cursor = str.length();
 for (T field : fields) {
 // This is really a two state FSM...
 if (str.length() > cursor) {
 str.append(SEPARATOR);
 }
 str.append(field);
 }
 }
 str.append(END_OBJECT);
}

GameAnalyze

Don't care for the name much - class names are usually nouns, so maybe GameAnalyzer or GameAnalysis.

void solve() {
 if (Thread.interrupted())
 throw new RuntimeTimeoutException();
 if (!this.simplifyRules()) {
 return;
 }
 this.removeEmptyRules();
 this.solveRules();
 if (this.rules.isEmpty()) {
 callback.solved(Solution.createSolution(this.knownValues));
 }
}

Major props for checking for interruption. Because it's not obvious that solve() is recursive, it looks as though the interrupt check is in the wrong place. It might make more sense to put that check within solveRules. I don't like cancelling the solve by throwing a runtime exception, and don't understand why you would choose to implement a unique RuntimeException for it at that. If you feel like you cannot throw a checked exception here, perhaps you should have a state object that various bits use to decide if they should continue processing. It's not at all clear to me that Solution.createSolution is in the right place -- it seems more flexible to pass the known values to a callback that knows how to apply the solution.

One aspect of the recursive approach that I really don't like is you are missing the opportunity to solve positions in parallel. At a minimum, I would want to consider using a different core to create Solutions than to decompose the problem. Without profiling, it's difficult to say if this would make a difference, but your current approach doesn't support that refactoring. For example, consider a listener that takes knownValues; you could have one version that publishes solutions in line, and an alternative that puts the knownValues into a queue, where another thread will pick them up to convert them.

Solution

Solution is trying to be two different things at once - it's the calculator, and the solution. Those two bits should be teased apart, which will make everything that is going on in there much clearer.

The use of Random in Solution seems really strange; you might look to squashed encoding, which would essentially give you a deterministic ordering of the possible "random" solutions available.

RootAnalyzeImpl

There are an awful lot of functions in here that are throwing IllegalStateExceptions. That suggests to me that you have one ore more classes in here, one which composes the solved state, and another the unsolved state, which have different verbs associated with them.

This is diseased:

if (Math.rint(solution) != solution || solution < 0 || solution >= this.getTotal()) {
 throw new IllegalArgumentException("solution must be an integer between 0 and total (" + this.getTotal() + ")");
}

IF solution must be an integer, why on earth does it have type double? You seem to be using a combinatorics library that produces non integer values; and then letting that decision contaminate everything else. Surely it makes more sense to treat your combinatorics problems as integer (or long) based, and firewall away any libraries that don't agree?

• Simon Forsberg: The reason for why I'm using double instead of int/long is that, when dealing with combinatorics of this scale, it gets really big really fast. The only other option would be a BigInteger, which perhaps would work for grabbing solutions once everything is solved, but would affect performance negatively while performing the actual solving.
• Simon Forsberg: The reason for GroupValues<T> is that I think it would be less readable with Map<FieldGroup<T>, Integer> everywhere. Although I could perhaps use composition over inheritance there as well, just as in FieldGroup (which is a good suggestion, had a feeling that would come). I like your multi-thread suggestion, not sure exactly how that should be implemented but I'll look into it, I guess making it multi-threaded is the only possible significant performance improvement right now.

Answer 2

One of the first rule I try to always follow is to be consistent. You're not always following the same pattern in your code for brackets.

 if (recursive == null) {
 return null;
 }

vs

 if (groupA == groupB)
 continue;

For someone who didn't read your explanation first and see this little guy public double nCr() { it really isn't clear at first what it means. I don't recommend commenting normally, but in this case javadoc for the method or a comment would be good.

This is really minor, but I had to point it out.

---

I would challenge your choice for this class : public class FieldGroup<T> extends ArrayList<T>. Is it really necessary to extend ArrayList ? Is your FieldGroup directly related to an ArrayList? Would it have worked with LinkedList ?

In reviews, I always suggest to use the interface and not the implementation. In your case I can't since you need those new method that you added. I really find it odd to have a List that you can't use like one without losing what you were creating the class for.

I don't really know what the best solution could be. I would probably simply have an instance of a collection and add the relevant method to it. You could also implements List directly, add an instance of an ArrayList and implements the methods by redirecting to the list.

Answer 3

You have quite a few object instantiations that seems redundant and could be removed. consider rewritting solveRules to something similar to:

private void solveRules() {
 if (this.rules.isEmpty())
 return;
 FieldGroup<T> chosenGroup = this.rules.get(0).getSmallestFieldGroup();
 if (chosenGroup == null) {
 throw new IllegalStateException("Chosen group is null.");
 }
 int groupSize = chosenGroup.size();
 if (groupSize == 0) {
 throw new IllegalStateException("Chosen group is empty. " + chosenGroup);
 }
 GroupValues<T> mapCopy = new GroupValues<T>();
 List<FieldRule<T>> rulesCopy = new ArrayList<FieldRule<T>>();
 int rulesCount = this.rules.size();
 for (FieldRule<T> rule : this.rules) {
 rulesCopy.add(new FieldRule<T>(rule));
 }
 for (int i = 0; i <= groupSize; i++) {
 mapCopy.copyFrom(this.knownValues);
 mapCopy.put(chosenGroup, i);
 for (int j = 0; j<rulesCount;j++) {
 rulesCopy.get(j).copyFrom(this.rules.get(j));
 }
 this.solve(mapCopy, rulesCopy, this.callback);
 }
}

every copyFrom is meant as a method that essentially does the same as your copy constructors but instead of allocating yet another object it reinitializes an existing one. Since your GameAnalyze is essentially a function with curried arguments you could skip the instantiation of all the analyzers and instead pass the constructor arguments to solve and let them drip down the call chain. I haven't checked all the proposed changes through, they are meant to give you the general idea.

• Simon Forsberg: I honestly doubt that this will improve the performance, I'm not even sure this approach will produce the correct results.
• Rune FS: I'm one 100% sure that memmory allocation and garbage collection is time consuming and produces nothing of value. So if there's memory allocation that's not required then removing that will always improve performance. AS I wrote I haven't checked all the proposed changes through, they are meant to give you the general idea. so yeah the example implementation might have flaws but it's definitely doable to rewrite it on the basis of the idea
• Rune FS: as an example from my work life. We were creating a grid to be rendered in html. I originally instantiated an object for each row. We had a few 1000s rows. We used upwards to 1 min for therendering which were more than we'd like. I changed the implementation so that we had a template row. Kind of what I proposed with the copyFrom. the end result of that optimization was that the bottle neck was ToString() and the entire grid rendered in less than 2s