Calculating every possible answer given a set of formulas

Question

Problem

Given a set of formulas (AKA "Rules"), get a list containing every possible answer that does not break any formula.

Formula variables can have a maximum equal to the number of characters. For example "ABC" can have a maximum value of 3, while "E" a maximum of 1.

Example, given this set of Rules:

{ABC + E} = 3
{ABC + F} = 2
{G + H} = 1

Results should be:

ABC=2, E=1, F=0, G=1 H=0
ABC=2, E=1, F=0, G=0 H=1

Note: negative numbers will never be considered.

**The letters are actually objects. "A" is an object, and "ABC" is an collection of 3 objects (A, B, C). I use "GameSquares" as an object, each given a name which is a letter, such as "A". "Section" is really just a wrapper for a collection of GameSquares.

Note: This is all part of a larger, real project. As such I do care about readability.

The project can be better described here. The program as a whole (Note that only part is being reviewed here), is a solution for calculating the odds of hitting a mine for every square in Minesweeper.

GameSquare - These are the "letters" in the formula. For example "A" or "B" (The name makes more sense as part of the whole project).

import java.util.Comparator;

public class GameSquare {
    private String name;

    public GameSquare(String name) {
        this.name = name;
    }

    public String getName() {
        return this.name;
    }

    @Override
    public boolean equals(Object other) {
        // self check
        if (this == other) {
            return true;
        }

        // null check
        if (other == null) {
            return false;
        }

        // type check and cast
        if (getClass() != other.getClass()) {
            return false;
        }

        GameSquare otherSquare = (GameSquare) other;

        // field comparison
        return this.name.equals(otherSquare.getName());
    }

    // Used for sorting. Just to keep the order consistent across lists
    public int compareTo(GameSquare o2) {
        return Comparator.comparing(GameSquare::getName).compare(this, o2);
    }

    @Override
    public String toString() {
        return this.name;
    }
}

Section - contains a Collection of GameSquare's

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Section {
    private Set<GameSquare> gameSquares = new HashSet<GameSquare>();

    public Section() {
    }

    public Section(Set<GameSquare> gameSquares) {
        this.gameSquares = gameSquares;
    }

    public Section(Collection<GameSquare> gameSquares) {
        this.gameSquares = new HashSet<>(gameSquares);
    }

    public void add(GameSquare gameSquare) {
        gameSquares.add(gameSquare);
    }

    public Set<GameSquare> getGameSquares() {
        return this.gameSquares;
    }

    public void setGameSquares(Set<GameSquare> gameSquares) {
        this.gameSquares = gameSquares;

    }

    public String toString() {
        return this.gameSquares.stream().map(Object::toString).collect(Collectors.joining(""));
    }
}

KeyValue - This class represents a letter in the formula. It's transformed from a GameSquare object. It contains a maxValue and value & most importantly, a pointer to a GameSquare or Section that it's properties represent.

public class KeyValue {
    private int value;
    private int maxValue;
    private Object key;

    public KeyValue(int maxValue, Object key) {
        this(0, maxValue, key);
    }

    public KeyValue(int value, int maxValue, Object key) {
        this.value = value;
        this.maxValue = maxValue;
        this.key = key;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    public int getMaxValue() {
        return maxValue;
    }

    public void setMaxValue(int maxValue) {
        this.maxValue = maxValue;
    }

    @Override
    public boolean equals(Object other) {
        // self check
        if (this == other) {
            return true;
        }

        // null check
        if (other == null) {
            return false;
        }

        // type check and cast
        if (getClass() != other.getClass()) {
            return false;
        }

        KeyValue otherKeyValue = (KeyValue) other;

        return this.value == otherKeyValue.getValue() && this.key == otherKeyValue.getKey();
    }

    @Override
    public String toString() {
        return this.key + " = " + this.value;
    }
}

Rule - represents a 'formula'. Contains a list of 'GameSquares' and an int that the sections must add up to.

public class Rule {
    private final Collection<GameSquare> squares;
    private final int resultsEqual;

    public Rule(Collection<GameSquare> squares, int resultsEqual) {
        this.squares = squares; 
        this.resultsEqual = resultsEqual;
    }

    public Collection<GameSquare> getSquares() {
        return new ArrayList<GameSquare>(squares);
    }

    public int getResultsEqual() {
        return resultsEqual;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int hashCode = 1;

        for (GameSquare square : this.squares) {
            hashCode = hashCode * prime + square.hashCode();
        }

        return hashCode;
    }

    @Override
    public boolean equals(Object other) {
        // self check
        if (this == other) {
            return true;
        }

        // null check
        if (other == null) {
            return false;
        }

        // type check and cast
        if (getClass() != other.getClass()) {
            return false;
        }

        Rule otherResultSet = (Rule) other;

        boolean sizesAreEqual = this.squares.size() == otherResultSet.squares.size();

        if (!sizesAreEqual) {
            return false;
        }

        // Don't care about order
        return this.squares.containsAll(otherResultSet.squares) && this.getResultsEqual() == otherResultSet.getResultsEqual();
    }
}

Now onto the actual logic class:

RulesCombinationCalculator Given a Set of Rules and Sections, get every possible combination of Sections that complies to the rules.

This works by first getting a list of every possible combinations for the first rule as a starting point. Then iterate through the other rules, checking if we have any duplicate values from previous rules (And use them if so), to get every combination for that rule. We then merge the lists so we're left with a single list containing all combinations for the rules.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class RulesCombinationCalculator {
    private static final int UNKNOWN_VALUE = 0;

    public static List<List<KeyValue>> getAllVariations(Collection<Section> sections, Collection<Rule> rules) {
        // start by getting the first Rule & sections relating to it
        final Rule ruleToProcess = rules.iterator().next();
        List<Rule> rulesLeftToProcess = rules.stream().filter(e -> e != ruleToProcess).collect(Collectors.toList());
        List<Section> sectionRelatingToRule = getSectionsInRule(sections, ruleToProcess);

        // Get all possible combinations given the rule & sections
        List<List<KeyValue>> allKnownValues = getAllVariationsOfARule(sectionRelatingToRule, ruleToProcess);

        // filter any items that are invalid given all rules
        allKnownValues = getValuesThatDontOverflow(allKnownValues, rules);

        for (Rule nextRule : rulesLeftToProcess) {
            Set<List<KeyValue>> allCombinationsOfRule = new HashSet<>();

            for (List<KeyValue> knownValues : allKnownValues) {
                allCombinationsOfRule.addAll(getAllCombinationsForRule(sections, rules, knownValues, nextRule));
            }
            allKnownValues = new ArrayList<>(allCombinationsOfRule);
        }

        // filter items with broken rules
        allKnownValues = allKnownValues.stream().filter(e -> !anyRulesBroken(rules, e)).collect(Collectors.toList());

        return allKnownValues;
    }

    private static Collection<List<KeyValue>> getAllCombinationsForRule(Collection<Section> allSections, Collection<Rule> allRules, Collection<KeyValue> knownValues, Rule rule) {
        List<Section> sectionRelatingToRule = getSectionsInRule(allSections, rule);
        List<KeyValue> sectionsTransformed = transformSectionsToKeyValues(sectionRelatingToRule, UNKNOWN_VALUE);
        populateListWithKnown(sectionsTransformed, knownValues);

        List<List<KeyValue>> allValuesForRule = getAllVariationsOfARuleWithKnownValues(sectionsTransformed, rule);
        allValuesForRule = getValuesThatDontOverflow(allValuesForRule, allRules);

        // Add all known values to the list
        combineLists(knownValues, allValuesForRule);

        return allValuesForRule;
    }

    /**
     * Given a Section and rule, return all possible combinations that do not break the rule
     * 
     * @param sectionsRelatingToRule All sections the rule relates to
     * @param rule Rule which cannot be broken
     * @return All variations of values for the arguments
     */
    public static List<List<KeyValue>> getAllVariationsOfARule(Collection<Section> sectionsRelatingToRule, Rule rule) {
        List<KeyValue> sectionsTransformed = transformSectionsToKeyValues(sectionsRelatingToRule, UNKNOWN_VALUE);
        return getAllVariationsOfARuleWithKnownValues(sectionsTransformed, rule);
    }

    public static List<List<KeyValue>> getAllVariationsOfARuleWithKnownValues(Collection<KeyValue> sectionsRelatingToRule, Rule rule) {
        List<List<KeyValue>> results = new ArrayList<>();

        // No need to proces values we already know the values of
        List<KeyValue> valuesWithKnown = sectionsRelatingToRule.stream().filter(e -> e.getValue() != UNKNOWN_VALUE).collect(Collectors.toList());
        sectionsRelatingToRule.removeAll(valuesWithKnown);

        // populate results with all variations of rule
        getAllVariationsOfARule(sectionsRelatingToRule, rule, results, valuesWithKnown);

        return results;
    }

    private static void getAllVariationsOfARule(Collection<KeyValue> sections, Rule rule, Collection<List<KeyValue>> results, List<KeyValue> knownValues) {
        if (sections.isEmpty()) {
            if (isRuleFollowed(rule, knownValues)) {
                results.add(knownValues);
            }
        }
        else
        {
            // Get a section from the list
            KeyValue section = sections.iterator().next();

            // We know the value cannot be higher than the max for the Section or the rule
            final int maxValue = Math.min(section.getMaxValue(), rule.getResultsEqual());

            // Add a list for every value from 0-max
            for (int i=0; i<=maxValue; i++) {
                // instantiate a new list. Doesn't matter that the list has the same object pointers we just need a new List object.
                List<KeyValue> newKnownValues = new ArrayList<>(knownValues);

                newKnownValues.add(new KeyValue(i, section.getMaxValue(), section.getKey()));

                // process other sections
                List<KeyValue> otherSections = sections.stream().filter(e -> e != section).collect(Collectors.toList());
                getAllVariationsOfARule(otherSections, rule, results, newKnownValues);
            }
        }
    }

    private static boolean isRuleFollowed(Rule rule, Collection<KeyValue> values) {
        int actualResult = getValueForSquaresInRule(values, rule);

        return actualResult == rule.getResultsEqual();
    }

    /**
     * "multiply" a list.
     */
    private static void combineLists(Collection<KeyValue> valueToAddToAllLists, Collection<List<KeyValue>> listToModify) {
        // Add all items to the list that are not already on the list
        listToModify.stream().forEach(l2 -> 
            l2.addAll(valueToAddToAllLists.stream().filter(e -> !l2.stream().anyMatch(e2 -> e2.getKey().equals(e.getKey()))).collect(Collectors.toList()))
        );
    }

    /**
     * If any key in the knownValues list matches a key in the listToPopulate, sets the value of the 'listToPopulate' to the value found 
     * 
     * @param listToPopulate List to modify
     * @param knownValues Get values from here
     */
    private static void populateListWithKnown(Collection<KeyValue> listToPopulate, Collection<KeyValue> knownValues) {
        for (KeyValue value : listToPopulate) {
            for (KeyValue knownValue : knownValues) {
                if (knownValue.getKey().equals(value.getKey())) {
                    value.setValue(knownValue.getValue());
                }
            }
        }
    }

    private static boolean anyValueTooHigh(Collection<Rule> rules, Collection<KeyValue> values) {
        return rules.stream().anyMatch(rule -> getValueForSquaresInRule(values, rule) > rule.getResultsEqual());
    }

    private static boolean anyRulesBroken(Collection<Rule> rules, Collection<KeyValue> values) {
        return rules.stream().anyMatch(rule -> getValueForSquaresInRule(values, rule) != rule.getResultsEqual());
    }

    private static int getValueForSquaresInRule(Collection<KeyValue> values, Rule rule) {
        // Filter the values where the rule contains all the squares, then add the value for each
        return values.stream()
            .filter(e -> rule.getSquares().containsAll(((Section) e.getKey()).getGameSquares()))
            .collect(Collectors.summingInt(e -> e.getValue()));
    }

    private static List<List<KeyValue>> getValuesThatDontOverflow(Collection<List<KeyValue>> valuesToFilter, Collection<Rule> rules) {
        return valuesToFilter.stream().filter(e -> !anyValueTooHigh(rules, e)).collect(Collectors.toList());
    }

    /**
     * Get all sections relating to a rule. For example if the Rule is {A, BC + D} = 3, we will get A, BC and D.
     * 
     * @param sections our HayStack. Find Sections here
     * @param rule our Needle. Contains sections to be found
     * @return Sections in the rule
     */
    private static List<Section> getSectionsInRule(Collection<Section> sections, Rule rule) {
        return sections.stream().filter(e -> rule.getSquares().containsAll(e.getGameSquares())).collect(Collectors.toList());
    }

    private static List<KeyValue> transformSectionsToKeyValues(final Collection<Section> sections, final int defaultValue) {
        return sections.stream().map(e -> new KeyValue(defaultValue, e.getGameSquares().size(), e)).collect(Collectors.toList());
    }
}

Partial TestClass / Test Data:

RulesCombinationCalculatorTest - A few test cases & a test Case given from: this mathstackexchange question

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import org.junit.Test;

public class RulesCombinationCalculatorTest {
    // Sort used for debugging
    private static final Map<String, Integer> sortingMap = new HashMap<>();
    static {
        sortingMap.put("G", 999);
        sortingMap.put("J", 998);
        sortingMap.put("O", 997);
        sortingMap.put("V", 996);
        sortingMap.put("I", 995);
        sortingMap.put("K", 994);
        sortingMap.put("Y", 993);
        sortingMap.put("L", 992);
        sortingMap.put("C", 991);
        sortingMap.put("R", 990);
    }

    private int compare(Object s1, Object s2) {
        return findValue(s2).compareTo(findValue(s1));
    }

    private Integer findValue(Object section) {
        String sectionAsString = section.toString();

        for (int i=0; i<sectionAsString.length(); i++) {
            Integer valueFound = sortingMap.get(String.valueOf(sectionAsString.charAt(i)));
            if (valueFound != null) {
                return valueFound;
            }
        }

        throw new RuntimeException("Cannot find value for: " + section);
    }

    @Test
    public void testGetAllVariationsOfRules() {
        List<Rule> testRules = TestData.TEST_SCENARIO_SPECIAL_02.getExpectedOrigResults();
        List<Section> testSections = TestData.TEST_SCENARIO_SPECIAL_02.getExpectedContents()
                .values()
                .stream()
                .map(e -> new Section(e))
                .sorted((e1, e2) -> compare(e1, e2))
                .collect(Collectors.toList());

        // Note: Order matters, see SectionTestScenarios.SCENARIO_SPECIAL_02
        // G, J, ONM, VTP, IBFA, K, YUS, LHED, C, XWRQ
        List<KeyValue> excpectedResultA11B11 = getExpectedResult(new int[]{0, 1, 0, 1, 1, 0, 0, 0, 1, 1}, testSections);
        List<KeyValue> excpectedResultA11B21 = getExpectedResult(new int[]{0, 1, 0, 2, 1, 0, 1, 0, 1, 0}, testSections);

        List<KeyValue> excpectedResultA12B11 = getExpectedResult(new int[]{0, 0, 1, 1, 2, 0, 0, 0, 1, 1}, testSections);
        List<KeyValue> excpectedResultA12B21 = getExpectedResult(new int[]{0, 0, 1, 2, 2, 0, 1, 0, 1, 0}, testSections);

        List<KeyValue> excpectedResultA21B11 = getExpectedResult(new int[]{1, 0, 0, 1, 2, 0, 0, 0, 0, 1}, testSections);
        List<KeyValue> excpectedResultA21B21 = getExpectedResult(new int[]{1, 0, 0, 2, 2, 0, 1, 0, 0, 0}, testSections);

        List<KeyValue> excpectedResultA22B11 = getExpectedResult(new int[]{0, 1, 0, 1, 2, 0, 0, 1, 0, 1}, testSections);
        List<KeyValue> excpectedResultA22B21 = getExpectedResult(new int[]{0, 1, 0, 2, 2, 0, 1, 1, 0, 0}, testSections);

        List<KeyValue> excpectedResultA23B11 = getExpectedResult(new int[]{0, 0, 0, 1, 3, 1, 0, 0, 0, 1}, testSections);
        List<KeyValue> excpectedResultA23B21 = getExpectedResult(new int[]{0, 0, 0, 2, 3, 1, 1, 0, 0, 0}, testSections);

        List<KeyValue> excpectedResultA24B11 = getExpectedResult(new int[]{0, 0, 1, 1, 3, 0, 0, 1, 0, 1}, testSections);
        List<KeyValue> excpectedResultA24B21 = getExpectedResult(new int[]{0, 0, 1, 2, 3, 0, 1, 1, 0, 0}, testSections);

        List<List<KeyValue>> results = RulesCombinationCalculator.getAllVariations(testSections, testRules);

        for (List<KeyValue> g : results) {
            for (KeyValue x : g) {
                // Set all maxValues to 0 so we can assert properly (expected all contain a maxValue of 0)
                x.setMaxValue(0);
            }

            g.sort((e1, e2) -> compare(e1, e2));
        }

        assertTrue(results.contains(excpectedResultA11B11));
        assertTrue(results.contains(excpectedResultA11B21));
        assertTrue(results.contains(excpectedResultA12B11));
        assertTrue(results.contains(excpectedResultA12B21));
        assertTrue(results.contains(excpectedResultA21B11));
        assertTrue(results.contains(excpectedResultA21B21));
        assertTrue(results.contains(excpectedResultA22B11));
        assertTrue(results.contains(excpectedResultA22B21));
        assertTrue(results.contains(excpectedResultA23B11));
        assertTrue(results.contains(excpectedResultA23B21));
        assertTrue(results.contains(excpectedResultA24B11));
        assertTrue(results.contains(excpectedResultA24B21));

        assertEquals(12, results.size());
    }

    @Test
    public void testGetAllVariationsOfARule() {
        GameSquare squareA = new GameSquare("A");
        GameSquare squareB = new GameSquare("B");
        GameSquare squareF = new GameSquare("F");
        GameSquare squareI = new GameSquare("I");
        GameSquare squareC = new GameSquare("C");
        GameSquare squareG = new GameSquare("G");
        GameSquare squareJ = new GameSquare("J");

        List<GameSquare> allSquares = Arrays.asList(squareA, squareB, squareC, squareF, squareI, squareG, squareJ);

        Section section1 = new Section();
        Section section2 = new Section();
        Section section3 = new Section();
        Section section4 = new Section();
        section1.setGameSquares(new HashSet<>(Arrays.asList(squareA, squareB, squareF, squareI)));
        section2.setGameSquares(new HashSet<>(Arrays.asList(squareC)));
        section3.setGameSquares(new HashSet<>(Arrays.asList(squareG)));
        section4.setGameSquares(new HashSet<>(Arrays.asList(squareJ)));

        List<Section> allSections = Arrays.asList(section1, section2, section3, section4);

        List<KeyValue> expectedResult1 = getExpectedResult(new int[]{1, 1, 1, 0}, allSections);
        List<KeyValue> expectedResult2 = getExpectedResult(new int[]{1, 1, 0, 1}, allSections);
        List<KeyValue> expectedResult3 = getExpectedResult(new int[]{1, 0, 1, 1}, allSections);
        List<KeyValue> expectedResult4 = getExpectedResult(new int[]{0, 1, 1, 1}, allSections);
        List<KeyValue> expectedResult5 = getExpectedResult(new int[]{2, 1, 0, 0}, allSections);
        List<KeyValue> expectedResult6 = getExpectedResult(new int[]{2, 0, 1, 0}, allSections);
        List<KeyValue> expectedResult7 = getExpectedResult(new int[]{2, 0, 0, 1}, allSections);
        List<KeyValue> expectedResult8 = getExpectedResult(new int[]{3, 0, 0, 0}, allSections);

        Rule rule = new Rule(allSquares, 3);
        List<List<KeyValue>> results = RulesCombinationCalculator.getAllVariationsOfARule(allSections,  rule);

        assertTrue(results.contains(expectedResult1));
        assertTrue(results.contains(expectedResult2));
        assertTrue(results.contains(expectedResult3));
        assertTrue(results.contains(expectedResult4));
        assertTrue(results.contains(expectedResult5));
        assertTrue(results.contains(expectedResult6));
        assertTrue(results.contains(expectedResult7));
        assertTrue(results.contains(expectedResult8));
        assertEquals(8, results.size());
    }

    // No known values
    @Test
    public void testGetAllVariationsOfARuleWithKnownValues01() {
        GameSquare squareA = new GameSquare("A");
        GameSquare squareB = new GameSquare("B");
        GameSquare squareF = new GameSquare("F");
        GameSquare squareI = new GameSquare("I");
        GameSquare squareC = new GameSquare("C");
        GameSquare squareG = new GameSquare("G");
        GameSquare squareJ = new GameSquare("J");

        List<GameSquare> allSquares = Arrays.asList(squareA, squareB, squareC, squareF, squareI, squareG, squareJ);

        Section section1 = new Section();
        Section section2 = new Section();
        Section section3 = new Section();
        Section section4 = new Section();
        section1.setGameSquares(new HashSet<>(Arrays.asList(squareA, squareB, squareF, squareI)));
        section2.setGameSquares(new HashSet<>(Arrays.asList(squareC)));
        section3.setGameSquares(new HashSet<>(Arrays.asList(squareG)));
        section4.setGameSquares(new HashSet<>(Arrays.asList(squareJ)));

        List<Section> allSections = Arrays.asList(section1, section2, section3, section4);
        List<KeyValue> allSectionsWithKnown = transformSectionsToKeyValues(allSections, 0);

        List<KeyValue> expectedResult1 = getExpectedResult(new int[]{1, 1, 1, 0}, allSections);
        List<KeyValue> expectedResult2 = getExpectedResult(new int[]{1, 1, 0, 1}, allSections);
        List<KeyValue> expectedResult3 = getExpectedResult(new int[]{1, 0, 1, 1}, allSections);
        List<KeyValue> expectedResult4 = getExpectedResult(new int[]{0, 1, 1, 1}, allSections);
        List<KeyValue> expectedResult5 = getExpectedResult(new int[]{2, 1, 0, 0}, allSections);
        List<KeyValue> expectedResult6 = getExpectedResult(new int[]{2, 0, 1, 0}, allSections);
        List<KeyValue> expectedResult7 = getExpectedResult(new int[]{2, 0, 0, 1}, allSections);
        List<KeyValue> expectedResult8 = getExpectedResult(new int[]{3, 0, 0, 0}, allSections);

        Rule rule = new Rule(allSquares, 3);
        List<List<KeyValue>> results = RulesCombinationCalculator.getAllVariationsOfARuleWithKnownValues(allSectionsWithKnown, rule);

        assertTrue(results.contains(expectedResult1));
        assertTrue(results.contains(expectedResult2));
        assertTrue(results.contains(expectedResult3));
        assertTrue(results.contains(expectedResult4));
        assertTrue(results.contains(expectedResult5));
        assertTrue(results.contains(expectedResult6));
        assertTrue(results.contains(expectedResult7));
        assertTrue(results.contains(expectedResult8));
        assertEquals(8, results.size());
    }

    // two known values
    @Test
    public void testGetAllVariationsOfARuleWithKnownValues02() {
        GameSquare squareA = new GameSquare("A");
        GameSquare squareB = new GameSquare("B");
        GameSquare squareF = new GameSquare("F");
        GameSquare squareI = new GameSquare("I");
        GameSquare squareC = new GameSquare("C");
        GameSquare squareG = new GameSquare("G");
        GameSquare squareJ = new GameSquare("J");

        List<GameSquare> allSquares = Arrays.asList(squareA, squareB, squareC, squareF, squareI, squareG, squareJ);

        Section section1 = new Section();
        Section section2 = new Section();
        Section section3 = new Section();
        Section section4 = new Section();
        section1.setGameSquares(new HashSet<>(Arrays.asList(squareA, squareB, squareF, squareI)));
        section2.setGameSquares(new HashSet<>(Arrays.asList(squareC)));
        section3.setGameSquares(new HashSet<>(Arrays.asList(squareG)));
        section4.setGameSquares(new HashSet<>(Arrays.asList(squareJ)));

        List<Section> allSections = Arrays.asList(section1, section2, section3, section4);
        List<KeyValue> allSectionsWithKnown = transformSectionsToKeyValues(allSections, 0);
        // set two known values
        allSectionsWithKnown.get(0).setValue(2);
        allSectionsWithKnown.get(1).setValue(1);

        List<KeyValue> expectedResult1 = getExpectedResult(new int[]{2, 1, 0, 0}, allSections);

        Rule rule = new Rule(allSquares, 3);
        List<List<KeyValue>> results = RulesCombinationCalculator.getAllVariationsOfARuleWithKnownValues(allSectionsWithKnown, rule);

        assertTrue(results.contains(expectedResult1));
        assertEquals(1, results.size());
    }

    private List<KeyValue> getExpectedResult(int[] values, List<Section> sections) {
        List<KeyValue> list = new ArrayList<>();

        for (int i=0; i<values.length; i++) {
            list.add(new KeyValue(values[i], 0, sections.get(i)));
        }

        return list;
    }

    private static List<KeyValue> transformSectionsToKeyValues(final Collection<Section> sections, final int defaultValue) {
        return sections.stream().map(e -> new KeyValue(defaultValue, e.getGameSquares().size(), e)).collect(Collectors.toList());
    }
}

TestData - This is used in the above test. I have other classes & tests that use these test cases, which is why it's separated

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestData {
    public static final TestScenario TEST_SCENARIO_SPECIAL_02 = getScenarioSpecial02();

    // Here: https://math.stackexchange.com/questions/3466402/calculating-minesweeper-odds-is-this-calculation-correct
    private static TestScenario getScenarioSpecial02() {
        // Green
        final GameSquare A = new GameSquare("A");
        final GameSquare B = new GameSquare("B");
        final GameSquare F = new GameSquare("F");
        final GameSquare I = new GameSquare("I");

        // Pink
        final GameSquare C = new GameSquare("C");

        // Yellow
        final GameSquare J = new GameSquare("J");

        // Brown
        final GameSquare G = new GameSquare("G");

        // Orange
        final GameSquare D = new GameSquare("D");
        final GameSquare E = new GameSquare("E");
        final GameSquare H = new GameSquare("H");
        final GameSquare L = new GameSquare("L");

        // Purple
        final GameSquare K = new GameSquare("K");

        // Light blue
        final GameSquare M = new GameSquare("M");
        final GameSquare N = new GameSquare("N");
        final GameSquare O = new GameSquare("O");


        // Dark blue
        final GameSquare P = new GameSquare("P");
        final GameSquare T = new GameSquare("T");
        final GameSquare V = new GameSquare("V");

        // Beige
        final GameSquare R = new GameSquare("R");
        final GameSquare X = new GameSquare("X");
        final GameSquare W = new GameSquare("W");
        final GameSquare Q = new GameSquare("Q");

        // Red
        final GameSquare S = new GameSquare("S");
        final GameSquare U = new GameSquare("U");
        final GameSquare Y = new GameSquare("Y");

        // (A+B+F+I) + (C) + (G) + (J) = 3
        List<GameSquare> gameSquareResults1 = new ArrayList<GameSquare>();
        gameSquareResults1.add(A);
        gameSquareResults1.add(B);
        gameSquareResults1.add(F);
        gameSquareResults1.add(I);
        gameSquareResults1.add(C);
        gameSquareResults1.add(J);
        gameSquareResults1.add(G);

        // (D+E+H+L) (C) + (G) + (K) = 1
        List<GameSquare> gameSquareResults2 = new ArrayList<GameSquare>();
        gameSquareResults2.add(D);
        gameSquareResults2.add(E);
        gameSquareResults2.add(H);
        gameSquareResults2.add(L);
        gameSquareResults2.add(C);
        gameSquareResults2.add(G);
        gameSquareResults2.add(K);

        // (M+N+O) + (J) + (K) + (G)         =        1
        List<GameSquare> gameSquareResults3 = new ArrayList<GameSquare>();
        gameSquareResults3.add(M);
        gameSquareResults3.add(N);
        gameSquareResults3.add(O);
        gameSquareResults3.add(J);
        gameSquareResults3.add(K);
        gameSquareResults3.add(G);

        // (P+T+V) + (RXWQ)                  =        2
        List<GameSquare> gameSquareResults4 = new ArrayList<GameSquare>();
        gameSquareResults4.add(P);
        gameSquareResults4.add(T);
        gameSquareResults4.add(V);
        gameSquareResults4.add(R);
        gameSquareResults4.add(X);
        gameSquareResults4.add(W);
        gameSquareResults4.add(Q);

        // (S+U+Y) + (RXWQ)                  =        1
        List<GameSquare> gameSquareResults5 = new ArrayList<GameSquare>();
        gameSquareResults5.add(S);
        gameSquareResults5.add(U);
        gameSquareResults5.add(Y);
        gameSquareResults5.add(R);
        gameSquareResults5.add(X);
        gameSquareResults5.add(W);
        gameSquareResults5.add(Q);

        Rule rule1 = new Rule(gameSquareResults1, 3);
        Rule rule2 = new Rule(gameSquareResults2, 1);
        Rule rule3 = new Rule(gameSquareResults3, 1);
        Rule rule4 = new Rule(gameSquareResults4, 2);
        Rule rule5 = new Rule(gameSquareResults5, 1);

        List<Rule> expectedResults = Arrays.asList(
                rule1,
                rule2,
                rule3,
                rule4,
                rule5
                );

        // Green
        List<GameSquare> resultSet1 = Arrays.asList(A,B,F,I);
        List<Section> parentSet1 = Arrays.asList(new Section(rule1.getSquares()));

        // Yellow
        List<GameSquare> resultSet2 = Arrays.asList(J);
        List<Section> parentSet2 = Arrays.asList(new Section(rule1.getSquares()),
                new Section(rule3.getSquares()));

        // Light-blue
        List<GameSquare> resultSet3 = Arrays.asList(M,N,O);
        List<Section> parentSet3 = Arrays.asList(new Section(rule3.getSquares()));

        // Pink
        List<GameSquare> resultSet4 = Arrays.asList(C);
        List<Section> parentSet4 = Arrays.asList(new Section(rule2.getSquares()),
                new Section(rule1.getSquares()));

        // Brown
        List<GameSquare> resultSet5 = Arrays.asList(G);
        List<Section> parentSet5 = Arrays.asList(new Section(rule2.getSquares()),
                new Section(rule1.getSquares()),
                new Section(rule3.getSquares()));

        // Purple
        List<GameSquare> resultSet6 = Arrays.asList(K);
        List<Section> parentSet6 = Arrays.asList(new Section(rule2.getSquares()),
                new Section(rule3.getSquares()));

        // Orange
        List<GameSquare> resultSet7 = Arrays.asList(D,E,H,L);
        List<Section> parentSet7 = Arrays.asList(new Section(rule2.getSquares()));

        // Dark-blue
        List<GameSquare> resultSet8 = Arrays.asList(P,T,V);
        List<Section> parentSet8 = Arrays.asList(new Section(rule4.getSquares()));

        // Beige
        List<GameSquare> resultSet9 = Arrays.asList(Q, R, W, X);
        List<Section> parentSet9 = Arrays.asList(new Section(rule4.getSquares()), new Section(rule5.getSquares()));

        // Red
        List<GameSquare> resultSet10 = Arrays.asList(S,U,Y);
        List<Section> parentSet10 = Arrays.asList(new Section(rule5.getSquares()));

        Map<List<Section>, List<GameSquare>> expectedContents = new HashMap<>();

        expectedContents.put(parentSet1, resultSet1);
        expectedContents.put(parentSet2, resultSet2);
        expectedContents.put(parentSet3, resultSet3);
        expectedContents.put(parentSet4, resultSet4);
        expectedContents.put(parentSet5, resultSet5);
        expectedContents.put(parentSet6, resultSet6);
        expectedContents.put(parentSet7, resultSet7);
        expectedContents.put(parentSet8, resultSet8);
        expectedContents.put(parentSet9, resultSet9);
        expectedContents.put(parentSet10, resultSet10);

        return new TestScenario(expectedContents, expectedResults);
    }
}

Answer 1

Note: I started analyzing Minesweeper probabilities in 2008 and have over the years refined my stragegy for this and now have a powerful and fast way to calculate every possible Minesweeper-related probability that you would want to know.

All the credit for this answer goes to myself and my 10+ years of experience with Minesweeper. Especially all my hours spent back in the days to analyze the mathematics in Minesweeper. Since 2009 I run my own website to play Minesweeper Flags which is a multiplayer version of Minesweeper where the objective is to take the mines instead of avoiding them.

KeyValue

One of your KeyValue constructors is never used

KeyValue could use generics, or always use Sections (sometimes with just one GameSquare)

KeyValue seems to always use either Section or section.getKey() for its object. Might as well always use section then.

I also think that it's more than just a Key and a Value, it's maybe an AssignedValue ?

GameSquare

Besides just having an optional specific name, or some way to recognize it for debugging purposes, this does not really fill a purpose. I don't think this class is necessary and can instead be replaced by using a generic type in your other classes. For example, using Section<XYPosition>, Section<String>.

Section

I like that you group fields that has the same probability together with each other. This is a common mistake that other people do not take into consideration and it greatly helps with improving the speed of the algorithm.

I think this can be improved a little bit though, you have three constructors at the moment - out of which one seems to be only used in your tests (the one that takes a Collection), so one constructor could be removed. Ideally I think it would be best to have only one constructor for this class.

The constructor that takes a Set does not take a defensive copy of the Set, which can cause issues if the user of the class is not careful.

Rule

Your Rule class does not care about the order of the squares, which is good, but why is it then not using a Set?

I also think that it would be better if your rules would work with Sections instead of GameSquares. Knowing that {ABCD + EF + G} = 4 is more interesting than knowing that {A+B+C+D+E+F+G} = 4

The main logic

Why is UNKNOWN_VALUE = 0 in RulesCombinationCalculator ? Zero is a perfectly well-suited known value in Minesweeper.

Your RulesCombinationCalculator.getAllVariations method returns a List<List<KeyValue>>. Then what? For someone who is not very familiar with your code, it's very unclear what to do with that. How do I get the probabilities for all the fields? And how do I know what I should pass this method to make it work properly?

What you could do is to provide a single method that does all the work of splitting squares into sections, creating rules, finding valid rule combinations, and calculate the probabilities. (The closest to this I could find in the rest of your code was OddsCalculatorTest.getResultsComplete which did everything except calculating the probabilities from the List<List<KeyValue>> )

Another thing to consider is to, in some method, instead of returning what you are currently returning encapsulate that result into another object and add a method of how to continue forward, so that you for example could write the following:

GameBoardAnalyzer.analyze(gameBoard)
    .createRules()
    .splitIntoSections()
    .calculateAllVariations()
    .calculateOdds()

Although I imagine that in many causes you will want just the odds, or some more of these results, so encapsulating all of the above in a result object and simply doing GameBoardAnalyzer.analyze(gameBoard) might be a good idea.

Either way, there's great potential to make usage simpler here.

Speaking of usage, it was not clear from the start to me how to set the number of available mines on the whole board, and once I found that out (pass it to the calculateOdds that exists in other parts of your code) I found another parameter: totalUnidentifiedSquares. It would be good if the GameBoard could keep track of how many mines are left and how many totalUnidentifiedSquares there are.

Tests

Some of your tests (not mainly the ones in your post, but in other parts of your code) contain many test-cases that look almost identical, just using a few different values. Those would be ideal for parameterized tests.

What if...

Let's say that you have this board: ('_' indicating an unclicked field)

0000
0122
02__
02__

This board has three mines left.

At the moment your code will believe that one of the mines here has the lowest probability (100%), because you don't take into consideration the lower-right square which is the only 0% square here. As the board has to have only three mines left, all those mines need to be placed on the regular sections that you do consider already. Leaving us with only one field that doesn't have a rule connected to it, and never getting its probabilities calculated.

Which can be solved by...

Do not handle the total number of mines seperately

The total number of mines on a Minesweeper board is not a special case. It is just another constraint and can be expressed as a regular rule.

Given these rules:

{ABC + E} = 3
{ABC + F} = 2
{G + H} = 1

You can add this rule for the total number of mines:

{ABC + E + F + G + H} = 4

Rule simplifications

Currently you are adding a lot of solutions at first, only to remove them later because they end up either overflowing a rule or elsewhere breaking a rule. You have three different checks for if a rule is not satisfied correctly: anyValueTooHigh, anyRulesBroken, and isRuleFollowed. If you would instead use some previous knowledge that you have learned, you could identify more quickly if something is not right. Basically, if a rule has 0 possible combinations, then something is wrong and some previously set value is not correct. In my code to analyze Minesweeper, I use the following process whenever I have set a value to a section:

If ABC has been assigned the value '2' in the example above. You don't need to loop the section for E from 0 to 1 and also assign it a value.

{ABC + E} = 3

With the knowledge that ABC = 2, the above becomes

{2 + E} = 3

Which means

{E} = 1

So when you have assigned the value to the section ABC, you can create a new rule, {E} = 1, which only has one solution and therefore resolves itself and giving you more information.

This is especially effective in the case of these rules:

{AEG + BCHI} = 1
{BCHI + DFJ} = 3

Which can be solved quickly by setting a value to any of the three current sections, AEG, BCHI, or DFJ. Of course, if you would set one value incorrectly you might one day find yourself in this situation:

{} = -1

Which indicates that some of the previously set values is incorrect, so the facts so far can be disregarded. In this way, I believe these situations will be found much earlier instead of in your current code where you set a lot of values at first and then in the end check if anything went wrong.

Overall

It took me a while to figure it out, but your code does indeed calculate probabilities correctly. And faster than many other pieces of code written for this purpose, I believe. That's a job well done.

Try to simplify the usage of the code. If I would want to use your code, I shouldn't need to know all about the inner workings of it to be able to use it.

And focus on performance (although I might have been slightly evil to throw situations at it which never happen in regular Minesweeper)