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
RootAnalyzeImpltoAnalyzeFactoryandAnalyzeResult - Added
BoundedFieldRuleclass, which the previously existingFieldRule - Added
RuleConstraintinterface (implemented byBoundedFieldRule), to support potentially further extensions - Moved the splitting of
FieldGroups toAnalyzeFactory - Some modifications to
GameAnalyzeto support the newRuleConstraintinterface, 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 <= (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
AnalyzeFactoryfor 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 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
fieldGroupsmethod 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
FieldRuleandBoundedFieldRuledone 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
