16
\$\begingroup\$

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 .

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 <= (a + b) <= 1
  • 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

Code

This code can also be found on github:

AnalyzeFactory.java: (153 lines, 4400 bytes)

/**
 * Class for creating {@link AnalyzeResult}s
 * 
 * @author Simon Forsberg
 *
 * @param <T> The type of field to do analyze on
 */
public class AnalyzeFactory<T> {
    private final List<RuleConstraint<T>> rules = new ArrayList<RuleConstraint<T>>();

    AnalyzeFactory(Solution<T> known, List<RuleConstraint<T>> rules) {
        for (Entry<FieldGroup<T>, Integer> sol : known.getSetGroupValues().entrySet()) {
            this.rules.add(new FieldRule<T>(null, sol.getKey(), sol.getValue()));
        }
        this.rules.addAll(rules);
    }

    /**
     * Create a new, empty analyze factory
     */
    public AnalyzeFactory() {
    }

    /**
     * Solve this analyze
     * 
     * @return An {@link AnalyzeResult} object for the result of the analyze.
     */
    public AnalyzeResult<T> solve() {
        List<RuleConstraint<T>> original = new ArrayList<RuleConstraint<T>>(this.rules.size());
        for (RuleConstraint<T> rule : this.rules) {
            original.add(rule.copy());
        }

        List<RuleConstraint<T>> inProgress = new ArrayList<RuleConstraint<T>>(this.rules.size());
        for (RuleConstraint<T> rule : this.rules) {
            inProgress.add(rule.copy());
        }

        final List<Solution<T>> solutions = new ArrayList<Solution<T>>();

        this.splitFieldRules(inProgress);

        double total = new GameAnalyze<T>(null, inProgress, null).solve(solutions);

        for (Solution<T> solution : solutions) {
            solution.setTotal(total);
        }

        List<FieldGroup<T>> groups = new ArrayList<FieldGroup<T>>();
        if (!solutions.isEmpty()) {
            for (FieldGroup<T> group : solutions.get(0).getSetGroupValues().keySet()) {
                // All solutions should contain the same fieldgroups.
                groups.add(group);
            }
        }
        AnalyzeResultsImpl<T> result = new AnalyzeResultsImpl<T>(original, inProgress, groups, solutions, total);
        return result;
    }

    /**
     * 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()}
     * @param rules List of rules to split
     */
    public void splitFieldRules(List<RuleConstraint<T>> rules) {
        if (rules.size() <= 1) {
            return;
        }

        boolean splitPerformed = true;
        while (splitPerformed) {
            splitPerformed = false;
            for (RuleConstraint<T> a : rules) {
                for (RuleConstraint<T> b : rules) {
                    splitPerformed |= checkIntersection(a, b);
                }
            }
        }
    }

    private boolean checkIntersection(RuleConstraint<T> ruleA, RuleConstraint<T> ruleB) {
        if (ruleA == ruleB) {
            return false;
        }

        List<FieldGroup<T>> fieldsA = ruleA.fieldGroups();
        List<FieldGroup<T>> fieldsB = ruleB.fieldGroups();
        List<FieldGroup<T>> fieldsCopy = new ArrayList<FieldGroup<T>>(ruleA.fieldGroups());
        List<FieldGroup<T>> ruleFieldsCopy = new ArrayList<FieldGroup<T>>(ruleB.fieldGroups());

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

                fieldsA.remove(groupA);
                fieldsA.add(both);
                if (!onlyA.isEmpty()) { 
                    fieldsA.add(onlyA);
                }

                fieldsB.remove(groupB);
                fieldsB.add(both);
                if (!onlyB.isEmpty()) { 
                    fieldsB.add(onlyB);
                }
                return true;
            }
        }
        return false;
    }

    /**
     * Split the current field rules that has been added to this object
     */
    public void splitFieldRules() {
        this.splitFieldRules(rules);
    }

    /**
     * Add a new rule constraint that needs to be respected in all solutions
     * 
     * @param rule {@link FieldRule} to add
     */
    public void addRule(RuleConstraint<T> rule) {
        this.rules.add(rule);
    }

    /**
     * Get the rules that has been added to this analyze
     * 
     * @return List of {@link FieldRule}s that has been added
     */
    public List<RuleConstraint<T>> getRules() {
        return new ArrayList<RuleConstraint<T>>(this.rules);
    }
}

BoundedFieldRule.java: (188 lines, 4773 bytes)

/**
 * A constraint of a number of fields or {@link FieldGroup}s that should have a sum within a specific range
 * 
 * @author Simon Forsberg
 * @param <T> Field type
 */
public class BoundedFieldRule<T> implements RuleConstraint<T> {

    private final T cause;
    protected final List<FieldGroup<T>> fields;
    protected int maxResult = 0;
    protected int minResult = 0;

    /**
     * Create a copy of an existing rule.
     * 
     * @param copyFrom Rule to copy
     */
    private BoundedFieldRule(BoundedFieldRule<T> copyFrom) {
        this.cause = copyFrom.cause;
        this.fields = new ArrayList<FieldGroup<T>>(copyFrom.fields);
        this.minResult = copyFrom.minResult;
        this.maxResult = copyFrom.maxResult;
    }

    /**
     * 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 BoundedFieldRule(T cause, Collection<T> rule, int min, int max) {
        this.cause = cause;
        this.fields = new ArrayList<FieldGroup<T>>();
        this.fields.add(new FieldGroup<T>(rule));
        this.minResult = min;
        this.maxResult = max;
    }

    public BoundedFieldRule(T cause, List<FieldGroup<T>> fields, int min, int max) {
        this.cause = cause;
        this.fields = new ArrayList<FieldGroup<T>>(fields);
        this.minResult = min;
        this.maxResult = max;
    }

    @Override
    public boolean isEmpty() {
        return fields.isEmpty() && minResult <= 0 && maxResult >= 0;
    }

    @Override
    public SimplifyResult simplify(GroupValues<T> knownValues) {
        if (this.isEmpty()) {
            return SimplifyResult.NO_EFFECT;
        }

        Iterator<FieldGroup<T>> it = fields.iterator();
        // a + b <= 1 ---- a = 1 ---> b <= 0 ---> b = 0
        int totalCount = 0;
        while (it.hasNext()) {
            FieldGroup<T> group = it.next();
            Integer known = knownValues.get(group);
            if (known != null) {
                it.remove();
                minResult -= known;
                maxResult -= known;
            }
            else totalCount += group.size();
        }

        // a + b < 0 is not a valid rule
        if (maxResult < 0) {
            return SimplifyResult.FAILED_NEGATIVE_RESULT;
        }

        // a + b > 2 is not a valid rule.
        if (minResult > 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 && minResult == maxResult) {
            knownValues.put(fields.get(0), minResult);
            return clearRule();
        }

        // (a + b) + (c + d) <= 0 would give the value 0 to all field groups and simplify things
        if (maxResult == 0) {
            for (FieldGroup<T> field : fields) {
                knownValues.put(field, 0);
            }
            return clearRule();
        }

        // (a + b) + (c + d) = 4 would give the value {Group.SIZE} to all Groups.
        if (totalCount == minResult) {
            for (FieldGroup<T> field : fields) {
                knownValues.put(field, minResult * field.size() / totalCount);
            }
            return clearRule();
        }

        if (minResult <= 0 && maxResult >= totalCount) {
            // Rule is effectively useless
            clearRule();
        }

        return SimplifyResult.NO_EFFECT;
    }

    private SimplifyResult clearRule() {
        SimplifyResult simplifyResult = fields.isEmpty() ? SimplifyResult.NO_EFFECT : SimplifyResult.SIMPLIFIED;
        fields.clear();
        minResult = 0;
        maxResult = 0;
        return simplifyResult;
    }

    @Override
    public String toString() {
        StringBuilder rule = new StringBuilder();
        rule.append(minResult);
        rule.append(" <= ");
        boolean fieldAdded = false;
        for (FieldGroup<T> field : this.fields) {
            if (fieldAdded) {
                rule.append(" + ");
            }
            fieldAdded = true;
            rule.append(field.toString());
        }
        rule.append(" <= ");
        rule.append(maxResult);
        return rule.toString(); 
    }

    @Override
    public BoundedFieldRule<T> copy() {
        return new BoundedFieldRule<T>(this);
    }

    @Override
    public List<FieldGroup<T>> fieldGroups() {
        return this.fields;
    }

    @Override
    public FieldGroup<T> getSmallestFieldGroup() {
        if (this.fields.isEmpty()) {
            return null;
        }

        FieldGroup<T> result = this.fields.get(0);
        for (FieldGroup<T> group : this.fields) {
            int size = group.size();
            if (size == 1) {
                return group;
            }
            if (size < result.size()) {
                result = group;
            }
        }
        return result;
    }

    @Override
    public T getCause() {
        return cause;
    }

    public int getMinResult() {
        return minResult;
    }

    public int getMaxResult() {
        return maxResult;
    }

}

FieldRule.java: (86 lines, 2164 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> extends BoundedFieldRule<T> {

    /**
     * Create a copy of an existing rule.
     * 
     * @param copyFrom Rule to copy
     */
    private FieldRule(FieldRule<T> copyFrom) {
        super(copyFrom.getCause(), copyFrom.fields, copyFrom.getResult(), copyFrom.getResult());
    }

    /**
     * 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) {
        super(cause, rule, result, result);
    }

    FieldRule(T cause, FieldGroup<T> group, int result) {
        super(cause, new ArrayList<T>(), result, result);
        this.fields.add(group);
    }

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

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

    @Override
    public int getMaxResult() {
        return getMinResult();
    }

    @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(getResult());
        return rule.toString(); 
    }

    @Override
    public FieldRule<T> copy() {
        return new FieldRule<T>(this);
    }

}

IntegerPoints.java: (60 lines, 1592 bytes)

public class IntegerPoints {

    public static FieldRule<Integer> positionValue(int x, int y, int i, int size) {
        return new FieldRule<Integer>(pos(x, y, size), Arrays.asList(pos(x, y, size)), i);
    }

    public static List<Integer> createLine(int x, int y, int size, int offsetX, int offsetY) {
        List<Integer> fields = new ArrayList<Integer>();
        while (x < size && y < size && x >= 0 && y >= 0) {
            fields.add(pos(x, y, size));
            y += offsetY;
            x += offsetX;
        }
        return fields;
    }

    public static String map(GroupValues<Integer> values, int size) {
        char[][] fields = new char[size][size];
        for (Entry<FieldGroup<Integer>, Integer> group : values.entrySet()) {
            Integer pos = group.getKey().get(0);
            Integer value = group.getValue();
            char ch = ' ';
            if (value == 1) {
                ch = '1';
            }
            else if (value == 0) {
                ch = '0';
            }
            fields[pos % size][pos / size] = ch;
        }

        StringBuilder str = new StringBuilder();
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (fields[x][y] == 0) {
                    str.append(' ');
                }
                else str.append(fields[x][y]);
            }
            str.append("\n");
        }
        return str.toString();
    }

    public static Integer pos(int x, int y, int size) {
        return y * size + x;
    }

}

NQueens.java: (44 lines, 1575 bytes)

public class NQueens {
    public static AnalyzeFactory<Integer> createQueens(int size) {
        AnalyzeFactory<Integer> analyze = new AnalyzeFactory<Integer>();

        for (int x = 0; x < size; x++) {
            // Diagonal from top to bottom-right
            analyze.addRule(new BoundedFieldRule<Integer>(0, IntegerPoints.createLine(x, 0, size, 1, 1), 0, 1));
            if (x != 0) {
                // Diagonals from left to bottom-right
                analyze.addRule(new BoundedFieldRule<Integer>(0, IntegerPoints.createLine(0, x, size, 1, 1), 0, 1));
            }

            // Diagonals from top to left-bottom
            analyze.addRule(new BoundedFieldRule<Integer>(0, IntegerPoints.createLine(x, 0, size, -1, 1), 0, 1));
            if (x != 0) {
                // Diagonals from right to left-bottom
                analyze.addRule(new BoundedFieldRule<Integer>(0, IntegerPoints.createLine(size - 1, x, size, -1, 1), 0, 1));
            }
        }

        for (int x = 0; x < size; x++) {
            List<Integer> columnFields = new ArrayList<Integer>();
            List<Integer> rowFields = new ArrayList<Integer>();
            for (int y = 0; y < size; y++) {
                columnFields.add(IntegerPoints.pos(x, y, size));
                rowFields.add(IntegerPoints.pos(y, x, size));
            }
            analyze.addRule(new FieldRule<Integer>(0, columnFields, 1));
            analyze.addRule(new FieldRule<Integer>(0, rowFields, 1));
        }

        return analyze;
    }

}

RuleConstraint.java: (45 lines, 1315 bytes)

public interface RuleConstraint<T> {
    /**
     * Apply various values to this rule to potentially simplify it and learn something new
     * 
     * @param knownValues Known values that can be removed and cleaned up from this rule to simplify it
     * @return A {@link SimplifyResult} corresponding to how successful the simplification was
     */
    SimplifyResult simplify(GroupValues<T> knownValues);

    /**
     * Create a copy of this rule, for trial-and-error purposes
     * 
     * @return A copy of this rule in its current state
     */
    RuleConstraint<T> copy();

    /**
     * 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();

    /**
     * Find the best field group to branch on
     * 
     * @return The best {@link FieldGroup} to branch on, or null if this rule does not have a preference about how to branch
     */
    FieldGroup<T> getSmallestFieldGroup();

    /**
     * @return An indication on what caused this rule to be created
     */
    T getCause();

    /**
     * @return Direct access to the {@link FieldGroup}s in this rule, in order to split them
     */
    List<FieldGroup<T>> fieldGroups(); 
}

Usage / Test

JUnit test is available on github:

Questions

  • It feels a bit icky to have the fieldGroups method in the interface and directly return the internal list. I have been a lot back-and-forth about this. Is there a better way to organize the splitting of field groups?
  • Is the inheritance between FieldRule and BoundedFieldRule done in a good way?
  • Is it somehow possible to use some of @rolfl's ideas to make my approach faster and have both the flexibility of my approach and the performance of rolfl's?
  • Any other comments appreciated
\$\endgroup\$
4
\$\begingroup\$

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<T>'s fields property smells for me.

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

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<T> has

List<FieldGroup<T>> fieldGroups(); 

and you add to FieldRule<T> another

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

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

Refactoring

public interface RuleConstraint<T> {  

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

and the implementation of the intersects() method

@Override
public boolean intersects(RuleConstraint<T> rule) {

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

    for (FieldGroup<T> fieldGroup : fields) {
        for (FieldGroup<T> 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<RuleConstraint<T>> rules) {
    if (rules.size() <= 1) {
        return;
    }

    boolean hasIntersections = true;
    while (hasIntersections) {
        hasIntersections= false;
        for (RuleConstraint<T> a : rules) {
            for (RuleConstraint<T> 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<T> ruleA, RuleConstraint<T> ruleB) {

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

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

            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<T> class

@Override
public List<FieldGroup<T>> fieldGroups() {
    return  new ArrayList<FieldGroup<T>>(this.fields);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.