Minesweeper analyze goes to N-Queensland

As @rolfl recently solved the N-Queens problem, I figured that it was time also for me to solve it.

My approach is significantly different from @rolfl's. I quickly realized that the N-Queens problem is just another Constraint Satisfaction Problem (CSP). Earlier, I have written a whole bunch of code for solving Minesweeper, so I figured that I could re-use that code and extend on it to solve N-Queens.

My code is significantly slower than @rolfl's (size 11 takes 3.5 seconds for me, while it takes 9 ms for @rolfl), which I am not very surprised about. My approach feels much more data-oriented and is a lot more flexible. (Who would have thought you could solve N-Queens by analyzing Minesweeper?)

The biggest changes I have done to my previous Minesweeper code are:

• Splitted RootAnalyzeImpl to AnalyzeFactory and AnalyzeResult

• Added BoundedFieldRule class, which the previously existing FieldRule

• Added RuleConstraint interface (implemented by BoundedFieldRule), to support potentially further extensions

• Moved the splitting of FieldGroups to AnalyzeFactory

• Some modifications to GameAnalyze to support the new RuleConstraint interface, nothing major and is therefore not included in this post

I have had the BoundedFieldRule concept in mind for a while, and it can also be used in analyzing good old minesweeper.

Class Summary (576 lines in 6 files, making a total of 15819 bytes)

• RuleConstraint.java: Interface for constraints to apply on the analyze

• BoundedFieldRule.java: A rule with both min and max value, for example 0






• FieldRule.java: A rule where min and max value is the same, so for example (a + b) = 1




-
AnalyzeFactory.java: Class responsible for adding rules and initiating the solving

-
NQueens.java: Contains a method to create an AnalyzeFactory for the N-Queens problem



• IntegerPoints.java: Utility methods for NQueens`

Dependencies

• Java 6

• My Minesweeper analyze code

Code

This code can also be found on g

AnalyzeFactory

The checkIntersection() method is doing more than the name implies. By reading this methodname one (at least me) would assume that neither rulaA nor ruleB would be changed. The direct (also through a method) access of the BoundedFieldRule's fields property smells for me.

Instead of letting these fields be accessed from outside, you should add methods to RuleConstraint for adding to and removing from this List.

FieldRule

public double nCr() {
    if (this.fields.size() != 1) {
        throw new IllegalStateException("Rule has more than one group.");
    }
    return Combinatorics.nCr(this.getFieldsCountInGroups(), this.minResult);
}

here the message of the IllegalStateException is misleading, because the condition is ! = 1. So for the case that there are no fields this exception will be thrown also with the same message.

RuleConstraint

/**
 * Determine whether or not this rule is finished and thus can be removed from the list of rules
 * 
 * @return True if this rule is successfully finished, false otherwise
 */
boolean isEmpty();

Here the name of the method isEmpty() has nothing to do with the documentation which says "Determine whether or not this rule is finished". So better change this to e.g isFinished().

General

The interface RuleConstraint has

List> fieldGroups();

and you add to FieldRule another

public Collection> getFieldGroups() {
    return new ArrayList>(this.fields);
}

method. Also they aren't returning the same thing in the same way it is leading to misunderstandings.

Refactoring

public interface RuleConstraint {  

    SimplifyResult simplify(GroupValues knownValues);
    RuleConstraint copy();  
    boolean isFinished();  //  getSmallestFieldGroup();  
    T getCause();  
    List> fieldGroups(); // still here, but should return a copy of the list
    void addFieldGroup(FieldGroup fieldGroup);  //  fieldGroup);  //  rule);  // <- new
}

and the implementation of the intersects() method

@Override
public boolean intersects(RuleConstraint rule) {

    if (rule == this) {
        return true;
    }

    for (FieldGroup fieldGroup : fields) {
        for (FieldGroup ruleFieldGroup: rule.fieldGroups()) {
            if (fieldGroup == ruleFieldGroup || !Collections.disjoint(fieldGroup, ruleFieldGroup)) {
                return true;
            }
    }

    return false;
}

leads inside AnalyzeFactory (after renaming the former checkIntersection() to performSplit()) to

public void splitFieldRules(List> rules) {
    if (rules.size()  a : rules) {
            for (RuleConstraint b : rules) {
                if (a.intersects(b)) {
                    hasIntersections = true;
                    performSplit(a, b);
                }
            }
        }
    }

Because performSplit() is only executed if ruleA.intersects(ruleB) we can make it void. We also remove the unneccessary check of if (groupA == groupB) because this is done in FieldGroupSplit.split() method also.

private void performSplit(RuleConstraint ruleA, RuleConstraint ruleB) {

    for (FieldGroup groupA : ruleA.fieldGroups()) {
        for (FieldGroup groupB : ruleB.fieldGroups()) {

            FieldGroupSplit splitResult = FieldGroupSplit.split(groupA, groupB);
            if (splitResult == null) {
                continue; // nothing to split
            }

            FieldGroup both = splitResult.getBoth();
            FieldGroup onlyA = splitResult.getOnlyA();
            FieldGroup onlyB = splitResult.getOnlyB();

            ruleA.removeFieldGroup(groupA);
            ruleA.addFieldGroup(both);
            if (!onlyA.isEmpty()) { 
                ruleA.addFieldGroup(onlyA);
            }

            ruleB.removeFieldGroup(groupB);
            ruleB.addFieldGroup(both);
            if (!onlyB.isEmpty()) { 
                ruleB.addFieldGroup(onlyB);
            }
            return;
        }
    }  

}

In BoundedFieldRule class

@Override
public List> fieldGroups() {
    return  new ArrayList>(this.fields);
}

StackExchange Code Review Q#75800, answer score: 4