高级和详细的扫雷概率

Field Groups     Probability Groups
  aaaaaaaa           abbbbbba
  aaaaaaaa           bcdefghb
  aabccdaa           bijklmnb
  aab13daa           bop13qrb
  aabccdaa           bijklmnb
  aaaaaaaa           bcdefghb
  aaaaaaaa           abbbbbba

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();
    }

    @Override
    public int hashCode() {
        if (bufferedHash != 0) {
            return this.bufferedHash;
        }

        int result = super.hashCode();
        this.bufferedHash = result;
        return result;
    }

    public int calculateHash() {
        this.bufferedHash = 0;
        return this.hashCode();
    }

}

/**
 * Creator of {@link DetailedResults} given an {@link AnalyzeResult} and a {@link NeighborFind} strategy
 * 
 * @author Simon Forsberg
 */
public class DetailAnalyze {
    public static <T> DetailedResults<T> solveDetailed(AnalyzeResult<T> analyze, NeighborFind<T> neighborStrategy) {
        // Initialize FieldProxies
        final Map<T, FieldProxy<T>> proxies = new HashMap<T, FieldProxy<T>>();
        for (FieldGroup<T> group : analyze.getGroups()) {
            for (T field : group) {
                FieldProxy<T> proxy = new FieldProxy<T>(group, field);
                proxies.put(field, proxy);
            }
        }

        // Setup proxy provider
        ProxyProvider<T> provider = new ProxyProvider<T>() {
            @Override
            public FieldProxy<T> getProxyFor(T field) {
                return proxies.get(field);
            }
        };

        // Setup neighbors for proxies
        for (FieldProxy<T> fieldProxy : proxies.values()) {
            fieldProxy.fixNeighbors(neighborStrategy, provider);
        }

        double totalCombinations = analyze.getTotal();
        Map<GroupValues<T>, FieldProxy<T>> bufferedValues = new HashMap<GroupValues<T>, FieldProxy<T>>();
        for (FieldProxy<T> proxy : proxies.values()) {
            // Check if it is possible to re-use a previous value
            FieldProxy<T> bufferedValue = bufferedValues.get(proxy.getNeighbors());
            if (bufferedValue != null && bufferedValue.getFieldGroup() == proxy.getFieldGroup()) {
                proxy.copyFromOther(bufferedValue, totalCombinations);
                continue;
            }

            // Setup the probabilities for this field proxy
            for (Solution<T> solution : analyze.getSolutionIteration()) {
                proxy.addSolution(solution);
            }
            proxy.finalCalculation(totalCombinations);
            bufferedValues.put(proxy.getNeighbors(), proxy);
        }

        int proxyCount = bufferedValues.size();

        return new DetailedResultsImpl<T>(analyze, proxies, proxyCount);
    }
}

/**
 * Interface for retreiving more detailed probabilities, for example 'What is the probability for a 4 on field x?'
 * 
 * @author Simon Forsberg
 *
 * @param <T> The field type
 */
public interface DetailedResults<T> {

    Collection<ProbabilityKnowledge<T>> getProxies();

    /**
     * Get the number of unique proxies that was required for the calculation. As some can be re-used, this will always be lesser than or equal to <code>getProxyMap().size()</code>
     * 
     * @return The number of unique proxies
     */
    int getProxyCount();

    /**
     * Get a specific proxy for a field
     * 
     * @param field
     * @return
     */
    ProbabilityKnowledge<T> getProxyFor(T field);

    /**
     * Get the underlying analyze that these detailed results was based on
     * 
     * @return {@link AnalyzeResult} object that is the source of this analyze
     */
    AnalyzeResult<T> getAnalyze();

    /**
     * @return The map of all probability datas
     */
    Map<T, ProbabilityKnowledge<T>> getProxyMap();

}

public class DetailedResultsImpl<T> implements DetailedResults<T> {

    private final AnalyzeResult<T> analyze;
    private final Map<T, ProbabilityKnowledge<T>> proxies;
    private final int proxyCount;

    public DetailedResultsImpl(AnalyzeResult<T> analyze, Map<T, FieldProxy<T>> proxies, int proxyCount) {
        this.analyze = analyze;
        this.proxies = Collections.unmodifiableMap(new HashMap<T, ProbabilityKnowledge<T>>(proxies));
        this.proxyCount = proxyCount;
    }

    @Override
    public Collection<ProbabilityKnowledge<T>> getProxies() {
        return Collections.unmodifiableCollection(proxies.values());
    }

    @Override
    public int getProxyCount() {
        return proxyCount;
    }

    @Override
    public ProbabilityKnowledge<T> getProxyFor(T field) {
        return proxies.get(field);
    }

    @Override
    public AnalyzeResult<T> getAnalyze() {
        return analyze;
    }

    @Override
    public Map<T, ProbabilityKnowledge<T>> getProxyMap() {
        return Collections.unmodifiableMap(proxies);
    }
}

public class FieldProxy<T> implements ProbabilityKnowledge<T> {

    private static int minK(int N, int K, int n) {
        // If all fields in group are neighbors to this field then all mines must be neighbors to this field as well
        return (N == K) ? n : 0;
    }

    private double[] detailedCombinations;
    private double[] detailedProbabilities;
    private final T field;
    private int found;
    private final FieldGroup<T> group;
    private final GroupValues<T> neighbors;

    public FieldProxy(FieldGroup<T> group, T field) {
        this.field = field;
        this.neighbors = new GroupValues<T>();
        this.group = group;
        this.found = 0;
    }

    void addSolution(Solution<T> solution) {
        recursiveRemove(solution.copyWithoutNCRData(), 1, 0);
    }

    /**
     * This field has the same values as another field, copy the values.
     * 
     * @param copyFrom {@link FieldProxy} to copy from
     * @param analyzeTotal Total number of combinations
     */
    void copyFromOther(FieldProxy<T> copyFrom, double analyzeTotal) {
        for (int i = 0; i < this.detailedCombinations.length - this.found; i++) {
            if (copyFrom.detailedCombinations.length <= i + copyFrom.found) {
                break;
            }
            this.detailedCombinations[i + this.found] = copyFrom.detailedCombinations[i + copyFrom.found];
        }

        this.finalCalculation(analyzeTotal);
    }

    /**
     * Calculate final probabilities from the combinations information
     * 
     * @param analyzeTotal Total number of combinations
     */
    void finalCalculation(double analyzeTotal) {
        this.detailedProbabilities = new double[this.detailedCombinations.length];
        for (int i = 0; i < this.detailedProbabilities.length; i++) {
            this.detailedProbabilities[i] = this.detailedCombinations[i] / analyzeTotal;
        }
    }

    /**
     * Setup the neighbors for this field
     * 
     * @param neighborStrategy {@link NeighborFind} strategy
     * @param proxyProvider Interface to get the related proxies
     */
    void fixNeighbors(NeighborFind<T> neighborStrategy, ProxyProvider<T> proxyProvider) {
        Collection<T> realNeighbors = neighborStrategy.getNeighborsFor(field);
        this.detailedCombinations = new double[realNeighbors.size() + 1];
        for (T neighbor : realNeighbors) {
            if (neighborStrategy.isFoundAndisMine(neighbor)) {
                this.found++;
                continue; // A found mine is not, and should not be, in a fieldproxy
            }

            FieldProxy<T> proxy = proxyProvider.getProxyFor(neighbor);
            if (proxy == null) {
                continue;
            }

            FieldGroup<T> neighborGroup = proxy.group;
            if (neighborGroup != null) {
                // Ignore zero-probability neighborGroups
                if (neighborGroup.getProbability() == 0) {
                    continue;
                }

                // Increase the number of neighbors
                Integer currentNeighborAmount = neighbors.get(neighborGroup);
                if (currentNeighborAmount == null) {
                    neighbors.put(neighborGroup, 1);
                }
                else neighbors.put(neighborGroup, currentNeighborAmount + 1);
            }
        }
    }

    @Override
    public T getField() {
        return this.field;
    }

    @Override
    public FieldGroup<T> getFieldGroup() {
        return this.group;
    }

    @Override
    public int getFound() {
        return this.found;
    }

    @Override
    public double getMineProbability() {
        return this.group.getProbability();
    }

    @Override
    public GroupValues<T> getNeighbors() {
        return this.neighbors;
    }

    @Override
    public double[] getProbabilities() {
        return this.detailedProbabilities;
    }

    private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
        if (Thread.interrupted()) {
            throw new RuntimeTimeoutException();
        }

        // Check if there are more field groups with values
        GroupValues<T> remaining = solution.getSetGroupValues();
        if (remaining.isEmpty()) {
            this.detailedCombinations[mines + this.found] += combinations;
            return;
        }

        // Get the first assignment
        Entry<FieldGroup<T>, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
        FieldGroup<T> group = fieldGroupAssignment.getKey();
        remaining.remove(group);
        solution = Solution.createSolution(remaining);

        // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
        int N = group.size();
        int n = fieldGroupAssignment.getValue();
        Integer K = this.neighbors.get(group);
        if (this.group == group) {
            N--; // Always exclude self becuase you can't be neighbor to yourself
        }

        if (K == null) {
            // This field does not have any neighbors to that group.
            recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
            return;
        }

        // Calculate the values and then calculate for the next group
        int maxLoop = Math.min(K, n);
        for (int k = minK(N, K, n); k <= maxLoop; k++) {
            double thisCombinations = Combinatorics.NNKK(N, n, K, k);
            recursiveRemove(solution, combinations * thisCombinations, mines + k);
        }
    }

    @Override
    public String toString() {
        return "Proxy(" + this.field.toString() + ")"
                + "\n neighbors: " + this.neighbors.toString()
                + "\n group: " + this.group.toString()
                + "\n Mine prob " + this.group.getProbability() + " Numbers: " + Arrays.toString(this.detailedProbabilities);
    }
}

/**
 * Interface strategy for performing a {@link DetailAnalyze}
 * 
 * @author Simon Forsberg
 *
 * @param <T> The field type
 */
public interface NeighborFind<T> {
    /**
     * Retrieve the neighbors for a specific field.
     * 
     * @param field Field to retrieve the neighbors for
     * 
     * @return A {@link Collection} of the neighbors that the specified field has
     */
    Collection<T> getNeighborsFor(T field);

    /**
     * Determine if a field is a found mine or not
     * 
     * @param field Field to check
     * 
     * @return True if the field is a found mine, false otherwise
     */
    boolean isFoundAndisMine(T field);
}

public interface ProbabilityKnowledge<T> {

    /**
     * @return The field that this object has stored the probabilities for
     */
    T getField();

    /**
     * @return The {@link FieldGroup} for the field returned by {@link #getField()}
     */
    FieldGroup<T> getFieldGroup();

    /**
     * @return How many mines has already been found for this field
     */
    int getFound();

    /**
     * @return The mine probability for the {@link FieldGroup} returned by {@link #getFieldGroup()}
     */
    double getMineProbability();

    /**
     * @return {@link GroupValues} object for what neighbors the field returned by {@link #getField()} has
     */
    GroupValues<T> getNeighbors();

    /**
     * @return The array of the probabilities for what number this field has. The sum of this array + the value of {@link #getMineProbability()} will be 1.
     */
    double[] getProbabilities();

}

public interface ProxyProvider<T> {

    FieldProxy<T> getProxyFor(T field);

}

@Override
public int hashCode() {
    if (bufferedHash != 0) {
        return this.bufferedHash;
    }

    int result = super.hashCode();
    this.bufferedHash = result;
    return result;
}

@Override
public int hashCode() {
    if (bufferedHash == 0) {
        this.bufferedHash = super.hashCode();
    }

    return this.bufferedHash;
}

Map<GroupValues<T>, FieldProxy<T>> bufferedValues = new HashMap<GroupValues<T>, FieldProxy<T>>();

for (int i = 0; i < this.detailedCombinations.length - this.found; i++) {
    if (copyFrom.detailedCombinations.length <= i + copyFrom.found) {
        break;

for (int i = 0; i < a - b; i++) {
    if (a2 <= i + b2) {
        break;

final int iMax = Math.min(this.detailedCombinations.length - this.found, copyFrom.detailedCombinations.length - copyFrom.found);
for (int i = 0; i < iMax; i++) {

final int iMax = Math.min(this.detailedCombinations.length - this.found, copyFrom.detailedCombinations.length - copyFrom.found);
for (int i = 0; i < iMax; i++) {
    this.detailedCombinations[i + this.found] = copyFrom.detailedCombinations[i + copyFrom.found];
}

System.arrayCopy(copyFrom.detailedCombinations, copyFrom.found, this.detailedCombinations, this.found, Math.min(this.detailedCombinations.length - this.found, copyFrom.detailedCombinations.length - copyFrom.found));

private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

    // Check if there are more field groups with values
    GroupValues<T> remaining = solution.getSetGroupValues();
    if (remaining.isEmpty()) {
        this.detailedCombinations[mines + this.found] += combinations;
        return;
    }

    // Get the first assignment
    Entry<FieldGroup<T>, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
    FieldGroup<T> group = fieldGroupAssignment.getKey();
    remaining.remove(group);
    solution = Solution.createSolution(remaining);

    // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
    int N = group.size();
    int n = fieldGroupAssignment.getValue();
    Integer K = this.neighbors.get(group);
    if (this.group == group) {
        N--; // Always exclude self becuase you can't be neighbor to yourself
    }

    if (K == null) {
        // This field does not have any neighbors to that group.
        recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
        return;
    }

    // Calculate the values and then calculate for the next group
    int maxLoop = Math.min(K, n);
    for (int k = minK(N, K, n); k <= maxLoop; k++) {
        double thisCombinations = Combinatorics.NNKK(N, n, K, k);
        recursiveRemove(solution, combinations * thisCombinations, mines + k);
    }
}

1. private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
2. GroupValues<T> remaining = solution.getSetGroupValues();
3. solution = Solution.createSolution(remaining);
4. recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
5. recursiveRemove(solution, combinations * thisCombinations, mines + k);

public static <T> Solution<T> createSolution(GroupValues<T> values) {
    return new Solution<T>(values).nCrPerform();
}

private Solution(GroupValues<T> values) {
    this.setGroupValues = values;
}

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;
}

public static double nCr(int n, int r) {
    if (r > n || r < 0) {
        return 0;
    }
    if (r == 0 || r == n) {
        return 1;
    }

    double value = 1;

    for (int i = 0; i < r; i++) {
        value = value * (n - i) / (r - i);
    }

    return value;
}

private void recursiveRemove(List<Entry<FieldGroup<T>, Integer>> solution, double combinations, int mines, int listIndex) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

    // Check if there are more field groups with values
    if (listIndex >= solution.size()) {
        // TODO: or if combinations equals zero ?
        this.detailedCombinations[mines + this.found] += combinations;
        return;
    }

    // Get the assignment
    Entry<FieldGroup<T>, Integer> fieldGroupAssignment = solution.get(listIndex);
    FieldGroup<T> group = fieldGroupAssignment.getKey();

    // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
    int N = group.size();
    int n = fieldGroupAssignment.getValue();
    Integer K = this.neighbors.get(group);
    if (this.group == group) {
        N--; // Always exclude self becuase you can't be neighbor to yourself
    }

    if (K == null) {
        // This field does not have any neighbors to that group.
        recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines, listIndex + 1);
        return;
    }

    // Calculate the values and then calculate for the next group
    int maxLoop = Math.min(K, n);
    for (int k = minK(N, K, n); k <= maxLoop; k++) {
        double thisCombinations = Combinatorics.NNKK(N, n, K, k);
        recursiveRemove(solution, combinations * thisCombinations, mines + k, listIndex + 1);
    }
}

recursiveRemove(new ArrayList<Entry<FieldGroup<T>, Integer>>(solution.copyWithoutNCRData().getSetGroupValues().entrySet()), 1, 0, 0);