This is a Scala-based port of the CSP solver csp-solver-java. It is a tiny framework for solving constraint
satisfaction problems (CSP) that have both discrete and finite domains. Although this framework is fully
functional, it is not meant to be production-ready, as it is primarily a small exercise for myself on
how to do functional programming with Scala.
The implementation is largely inspired from the splendid introductory text "Artificial Intelligence - A Modern Approach" by Stuart Russell and Peter Norvig.
csp-core: Contains a functional approach on CSP-framework design for CSPs that are both discrete and finite.csp-queens: Contains an example application which expresses the N-Queens problem as a CSP.csp-sudoku: Contains an example application which expresses Sudoku as a CSP.
The framework builds upon a set of a few abstractions. Trait CSP is the basis for all domain-specific
CSPs. It provides the means to construct the initial assignment, which is comprised of all the Variables of the CSP
and their initial state. A variable can be either assigned or unassigned. In the first case, its domain has been
reduced to a single fixed value, while in the latter case it has no assigned value, but a - possibly reduced - set
of admissible domain values. Trait CSP also provides the means to construct the full set of Constraints for
the CSP. A Variable of the CSP takes part in one or multiple Constraints. A Constraint involves some subset
of the variables of a CSP and specifies the allowable combinations of values for that subset. The Constraint
trait provides the means to determine whether a constraint is consistent and satisfied given the set of
dependent variables.
The current state of a CSP is represented using an Assignment. An assignment always contains the full set of
variables of the CSP. An Assignment is partial, if it still contains Variables that are unassigned. An assignment
that does not violate any constraints is called consistent or legal. A complete assignment is one in which
every variable is assigned. A solution to the CSP is a complete assignment which does not violate any constraints.
Class Assignment implements forward checking. This is a technique that eliminates the value assigned to a variable
from all other variables that participate in the same Constraints, thus further decreasing the search space of CSP.
Class DFSSolver provides a generic way to operate on instances of CSP using depth-first search. It is able to apply
heuristics for both variable ordering and value ordering that can dramatically reduce the search space. By default, it
uses an uninformed approach that simply selects the next unassigned variable and the preserves the original ordering of
domain values for that variable. The DFSSolver progresses from Assignment to its successor until a complete
assignment has been found or the search space is exhausted.
The framework currently only provides the AllDiff constraint. This constraint is satisfied if each of its variables is
assigned to a different value.
The DFSSolver uses an uninformed approach by default which simply selects the next unassigned variable. However,
it is also possible to use the MinimumRemainingValue heuristic, which selects the variable that is most constrained
given the current state of the CSP. Thus, the variable that has the fewest choices for domain values left will be
chosen. Using this heuristic can dramatically reduce the runtime of the solver, since the search space is pruned
efficiently.
The DFSSolver uses an uninformed approach by default which simply preserves the original ordering of domain values
for a given unassigned Variable. Currently, there is no informed implementation of ValueOrdering.
The experience of rewriting a Java-based framework that makes heavy use of functional concepts into an equivalent Scala solution was quite interesting. I have to say that I was and still am pretty happy on how the Java-based solution turned out. Using the Stream API and concepts from functional programming like immutability and combinator functions significantly improved the quality of the code.
Still, the Java version has some shortcomings which the Scala-based solution solves much more elegantly. First,
there is the need to do an excessive amount of defensive copying in order to implement immutable classes. Second,
the Stream API lacks combinator functions like foldLeft, which greatly simplify multiple state mutations in the
presence of immutable data structures.
While the Scala version resembles the Java version in almost every detail, these aspects improved the readability of the code even more. The next couple of sections highlight some of the aspects that contribute to the Java vs. Scala discussion in greater detail, but also provide general things about this port that may be of interest.
The Java version uses the immutable class VariableIdentity to represent the identity of a variable using a specific
type rather than String. But the extra class increases the amount of code and is at its core just a wrapper around a
String. The Scala version makes use of type aliases which eliminates the need for a separate class while enabling us
to use a specific type.
So, in Scala we simply write
object Variable {
type Identity = String
}
instead of providing our own class for this, like in the Java version.
public class VariableIdentity {
private final String identity;
private VariableIdentity(final String identity) {
this.identity = identity;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
VariableIdentity that = (VariableIdentity) o;
return !(identity != null ? !identity.equals(that.identity) : that.identity != null);
}
@Override
public int hashCode() {
return identity != null ? identity.hashCode() : 0;
}
@Override
public String toString() {
return identity;
}
public static VariableIdentity id(final String identity) {
return new VariableIdentity(identity);
}
}
A Variable is represented using a case class to leverage its immutability constraints and copy constructors.
However, since a variable also has a concept of identity the auto-generated methods for equals and hashCode
are no longer suitable, since they are evaluated against the whole set of attributes that are declared with the
first parameter list of the case class. Splitting the set of attributes into two parameter lists allows us
to implement case classes that have an identity, while retaining their immutability constraints. Have a look at
the implementation of Variable.
case class Variable[+A](id: Identity)(val value: Option[A] = None, val domain: List[A]) {
def restrict[B >: A](disallowedValue: B): Variable[B] =
copy()(value = value, domain = domain.filterNot(items => items == disallowedValue))
def assign[B >: A](value: B): Variable[B] =
copy()(value = Some(value), domain = List.empty)
def isAssigned(): Boolean =
value.isDefined
}
This comes at the price of a slightly higher level of verbosity. Attributes of the case class that go into the second
parameter have to be explicitly marked as vals. Otherwise, accessing the attribute like Variable.value would not
work. Also, copy constructors get a bit more complicated, since the whole set of attributes that went into the second
parameter list (in this case value and domain) need to be explicitly named.
When restricting the domains of dependent variables, we are forced to use a for-loop in the Java version in order
to successively mutate the intermediary Assignments since the Java Stream API does not provide a function that acts
as a reducer and combiner.
for (VariableIdentity variableIdentity : dependentVariables(variable, constraints)) {
assignment = assignment.restrict(variableIdentity, value);
}
Scala does provide such a function: foldLeft. So instead of mixing imperative and functional programming like in the
Java version, we can simply write
dependentVariables(variableIdentity, constraints)
.foldLeft(baseAssignment)((assignment, dependentVariableIdentity) => assignment.restrict(dependentVariableIdentity, value))
and stay functional all the way through.
The immutable Set that comes with Scala is invariant in its parametric type. Thus, I switched from the immutable
Set to an immutable List whenever appropriate. I'd be glad on feedback if there is a better way of doing this.
Package com.mgu.csp.sudoku formulates Sudoku as a constraint satisfaction problem. The current implementation is able to parse
a Sudoku puzzle as line-delimited string like the one shown underneath.
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
Each cell of the Sudoku puzzle is represented as a variable of the CSP, where
0 denotes an unassigned variable with domain values ranging from 1 to 9 and where every other number represents an
assigned variable. There are three kinds of constraints, which are all represented using AllDiff on their dependent
variables:
- Row constraints: The assigned values to every variable in a row of the puzzle must be all different.
- Column constraints: The assigned values to every variable in a column of the puzzle must be all different.
- Grid constraints: The assigned values to every variable within a grid must be all different.
In total there are 27 constraints and 81 variables.
Package com.mgu.csp.queens represents the N-Queens problem as a constraint satisfaction problem. The input for the
CSP is the size of the board (defaults to 8) that starts off with an Assignment that contains only unassigned
variables. A Variable represents a single row of the board, while its domain represents possible column assignments.
The Queens CSP uses the AllDiff constraint on each pair of rows. This enables us to filter all solutions in which
two rows use the same column for their queen placement. To also filter out diagonally conflicting queens, we make us
of the so called NonMatchingDifference constraint. This constraint works only if both dependent variables are already
assigned a value. If not, it cannot decide whether to discard the assignment. As this property holds for all
constraints of that type, it is not able to prune a partial assignment. This limits the efficiency of our CSP
representation as it is only able to prune a partial assignment if the AllDiff constraint takes action.
The output for a solution of the CSP looks like this (N=8):
...Q.... [4]
.Q...... [2]
.......Q [8]
.....Q.. [6]
Q....... [1]
..Q..... [3]
....Q... [5]
......Q. [7]
Feedback and pull requests are always welcome!
Contributors:
This software is released under the terms of the MIT license.