Constraint programming is a style of programming where relations between variables are stated in the form of constraints. This form of programming was first made popular by logic programming languages such as Prolog but the style is now also used outside logic programming specific languages. Constraints differ from the common primitives of other programming languages in that they do not specify one or more steps to execute but rather the properties of a solution to be found. If you want use a constraint-specific programming language, maybe Prolog is for you. If however you like Groovy, but want to apply a touch of constraint style flavor to your code, read on to learn about Gecode/J, Choco and tuProlog integration possibilities.

Gecode/J

Gecode/J is a Java interface for the Gecode C++ constraint programming library. Let's have a look at making the Money example from the Gecode/J library a bit Groovier. If you haven't seen the example before, it involves solving the following puzzle:

    S E N D
+   M O R E
= M O N E Y

How can I replace the letters in the puzzle with numbers so that the numbers add up in the expected way? See here for further details.

A little helper library

First we can create a little helper library to make our subsequent code a little Groovier:

import static org.gecode.Gecode.*
import static org.gecode.GecodeEnumConstants.*
import org.gecode.*

class GroovySpace extends Space {
  public GroovySpace() {
    super()
  }
  public GroovySpace(Boolean share, GroovySpace space) {
    super(share, space)
  }
  def notEqual(IntVar v, val) {
    rel(this, v, IRT_NQ, val, ICL_BND)
  }
  def distinct(VarArray<IntVar> v) {
    distinct(this, v, ICL_BND)
  }
  def expressionsEqual(Expr e1, Expr e2) {
    post(this, e1, IRT_EQ, e2)
  }
  def branchOverVariables(VarArray<IntVar> v) {
    branch(this, v, BVAR_SIZE_MIN, BVAL_MIN)
  }
  def variableOverRange(v, r) {
      new IntVar(this, v, r.from, r.to)
  }
}

A Groovy Solution

Here is how we could now code the solution.

import org.gecode.*

class Money extends GroovySpace {
  public VarArray<IntVar> letters

  public Money() {
    super()

    // We need 8 variables. Each one gets the name of it's
    // corresponding letter, and an initial domain of [0..9]
    letters = new VarArray<IntVar>(8)
    "SENDMORY".each{ letters.add(variableOverRange(it, 0..9)) }
    def s = letters[0]
    def e = letters[1]
    def n = letters[2]
    def d = letters[3]
    def m = letters[4]
    def o = letters[5]
    def r = letters[6]
    def y = letters[7]

    // set up constraints
    notEqual(s, 0)
    notEqual(m, 0)
    expressionsEqual(
        new Expr()
        .p(1000, s).p(100, e).p(10, n).p(d)
        .p(1000, m).p(100, o).p(10, r).p(e),
        new Expr()
        .p(10000, m).p(1000, o).p(100, n).p(10, e).p(y))
    distinct(letters)

    // start looking for solutions
    branchOverVariables(letters)
  }

  public Money(Boolean share, Money money) {
    super(share, money)
    letters = new VarArray<IntVar>(this, share, money.letters)
  }
}

def opt = new Options("SEND+MORE=MONEY")
opt.gui = true
opt.parse(args)
opt.doSearch(new Money())

It relies on the same Options class used in the original Java example.

Running this code (we used a Java 6 JVM with the following JVM argument, -Djava.library.path=C:\Geocode\bin) yields:

SEND+MORE=MONEY:
letters=[S=9,E=5,N=6,D=7,M=1,O=0,R=8,Y=2]

Summary:
        runtime:      3
        solutions:    1
        propagations: 11
        failures:     1
        clones:       2
        commits:      3
        peak memory:  6KB

Running the program with the -gui command line argument yields the following GUI display:

It would be fun to take this example a little further with a proper DSL to define the constraints.

Choco

Choco is a java library for constraint satisfaction problems (CSP), constraint programming (CP) and explanation-based constraint solving (e-CP). It is built on an event-based propagation mechanism with backtrackable structures. It's a great alternative to Gecode/J especially if you want a Java only solution.

Choco Magic Squares

We'll look at solving the Magic Square problem (though we haven't coded up making the diagonals add up too, just the rows and columns). Converting this example to Groovy yields:

import choco.integer.IntVar
import choco.integer.IntDomainVar
import choco.Problem

int n = 4
int nsq = n * n
println "Magic Square Problem with n = " + n

def p = new Problem()
// create variables
def vars = new IntDomainVar[nsq]
for (i in 0..<n)
    for (j in 0..<n)
        vars[i * n + j] = p.makeEnumIntVar("C${i}_${j}", 1, nsq)
int sumAllSquares = nsq * (nsq + 1) / 2
def sum = p.makeEnumIntVar("S", 1, sumAllSquares)

// vars should be pairwise distinct
for (i in 0..<nsq)
    for (j in 0..<i)
        p.post(p.neq(vars[i], vars[j]))

int[] coeffs = [1] * n

for (i in 0..<n) {
    // all cols should add to sum
    IntVar[] col = (0..<n).collect{ j -> vars[i * n + j] }
    p.post(p.eq(p.scalar(coeffs, col), sum))
    // all rows should add to sum
    IntVar[] row = (0..<n).collect{ j -> vars[j * n + i] }
    p.post(p.eq(p.scalar(coeffs, row), sum))
}

p.solve() // find first solution
for (i in 0..<n) {
    for (j in 0..<n)
        print vars[i * n + j].val.toString().padLeft(3)
    println()
}

And has this output when run:

Magic Square Problem with n = 4
  1  2 15 16
  6 11 10  7
 13  9  4  8
 14 12  5  3

Going Further

We can have a little more fun with this example. First, let's make the diagonals also add up:

IntVar[] downdiag = (0..<n).collect{ i -> vars[i * n + i] }
IntVar[] updiag = (0..<n).collect{ i -> vars[i * n + n - i - 1] }
p.post(p.eq(p.scalar(coeffs, downdiag), sum))
p.post(p.eq(p.scalar(coeffs, updiag), sum))

Now, let's also make the left kite (defined as below):

-- xx -- --
xx -- xx --
-- -- -- --
-- xx -- --

Also add up to the magic square value:

IntVar[] leftkite = [vars[1], vars[4], vars[6], vars[13]]
p.post(p.eq(p.scalar(coeffs, leftkite), sum))

Finally, let's make the middle columns in the bottom row equal to '1514':

IntVar[] date = [vars[13], vars[14]]
int[] datecoeffs = [100, 1]
p.post(p.eq(p.scalar(datecoeffs, date), 1514))

Let's see what solutions we now have:

def more = p.solve()
while (more) {
    println "Success at move: $p.solver.searchSolver.nodeCount"
    for (i in 0..<n) {
        for (j in 0..<n)
            print vars[i * n + j].val.toString().padLeft(3)
        println()
    }
    more = p.nextSolution()
}

Which yields the following results:

Dürer Magic Square Problem
Success at move: 1231
 16  1  4 13
  7 10 11  6
  9  8  5 12
  2 15 14  3
Success at move: 1236
 16  1  4 13
 11  6  7 10
  5 12  9  8
  2 15 14  3
Success at move: 1299
 16  3  2 13
  5 10 11  8
  9  6  7 12
  4 15 14  1
Success at move: 1300
 16  3  2 13
  9  6  7 12
  5 10 11  8
  4 15 14  1

The third solution in this list matches the famous Albrecht Dürer engraving.

This engraving has the following properties (from wikipedia):

"The order-4 magic square in Albrecht Dürer's engraving Melancholia I is believed to be the first seen in European art. The sum 34 can be found in the rows, columns, diagonals, each of the quadrants, the center four squares, the corner squares, the four outer numbers clockwise from the corners (3+8+14+9) and likewise the four counter-clockwise (the locations of four queens in the two solutions of the 8 queens puzzle), the two sets of four symmetrical numbers (2+8+9+15 and 3+5+12+14) and the sum of the middle two entries of the two outer columns and rows (e.g. 5+9+8+12), as well as several kite-shaped quartets, e.g. 3+5+11+15; the two numbers in the middle of the bottom row give the date of the engraving: 1514."

Choco menu selection example

Inspired by this xkcd cartoon, here is a solution to a little menu selection problem.

This was solved using Choco version 2.1. Choco also supports reals, but to make things easy, I used price in cents.

import static choco.Choco.*
import choco.kernel.model.variables.integer.IntegerVariable

def m = new choco.cp.model.CPModel()
def s = new choco.cp.solver.CPSolver()

def menu = [
    'Mixed fruit'       : 215,
    'French fries'      : 275,
    'Side salad'        : 335,
    'Hot wings'         : 355,
    'Mozzarella sticks' : 420,
    'Sampler plate'     : 580
]
def numOrdered = new IntegerVariable[menu.size()]
def priceEach = new int[menu.size()]
def sum = 1505
menu.eachWithIndex { name, price, i ->
    // number ordered >= 0
    // number ordered * price <= sum
    numOrdered[i] = makeIntVar(name, 0, sum.intdiv(price))
    priceEach[i] = price
}
m.addConstraint(eq(scalar(numOrdered, priceEach), sum))
s.read(m)

def more = s.solve()
while (more) {
    println "Found a solution:"
    numOrdered.each {
        def v = s.getVar(it)
        if (v.val) println "  $v.val * $v.name"
    }
    more = s.nextSolution()
}

It produces this output:

Found a solution:
  7 * Mixed fruit
Found a solution:
  1 * Mixed fruit
  2 * Hot wings
  1 * Sampler plate

tuProlog

tuProlog is a Java-based light-weight Prolog for Internet applications and infrastructures. It offers numerous integration options: allowing Prolog syntax to be used in the form of theories; programatic theory construction using a Java-based API; and mechanisms to call back into Groovy and Java from Prolog.

Magic Squares

We can code up an order 3 Magic square problem as follows:

// require(url:'http://www.alice.unibo.it/tuProlog/', jar:'tuprolog.jar', version:'2.1')
import alice.tuprolog.*

def engine = new Prolog()
def digits = (1..9).collect{ "d($it)." }.join('\n')
def vars = ('A'..'I')
def combos = []
('A'..'H').each { outer ->
    (outer.next()..'I').each{ inner ->
        combos << /$outer=\=$inner/
    }
}
def all = vars.join(',')
engine.theory = new Theory("""
$digits
sum(X,Y,Z):-d(X),d(Y),d(Z),(X+Y+Z)=:=15.
rows($all):-sum(A,B,C),sum(D,E,F),sum(G,H,I).
cols($all):-sum(A,D,G),sum(B,E,H),sum(C,F,I).
diags($all):-sum(A,E,I),sum(G,E,C).
distinct($all):-${combos.join(',')}.
""")
def answer = engine.solve("rows($all),cols($all),diags($all),distinct($all).")
def squares = ('A'..'I').collect{ answer.getTerm(it).toString().padLeft(3) }
for (row in 0..2) {
    for (col in 0..2)
        print squares[row * 3 + col]
    println()
}

The result is:

  2  7  6
  9  5  1
  4  3  8

Family Trees

Finally, here is a Groovy version of the typical first Prolog program, which demonstrates the simplest of relational reasoning:

// require(url:'http://www.alice.unibo.it/tuProlog/', jar:'tuprolog.jar', version:'2.1')
import alice.tuprolog.*

/** Pretty Printing */
def pprint(soln) {
    println soln.isSuccess() ? "$soln.query = $soln.solution" : 'no solution found'
}

/** Prolog clauses */
def getTheory() {
new Theory("""

parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

female(pam).
male(tom).
male(bob).
female(liz).
female(pat).
female(ann).
male(jim).

offspring(X,Y) :- parent(Y,X).

mother(X,Y) :-
    parent(X,Y),
    female(X).
father(X,Y) :-
    parent(X,Y),
    male(X).

grandparent(X,Z) :-
    parent(X,Y),
    parent(Y,Z).
grandmother(X,Y) :-
    grandparent(X,Y),
    female(X).
grandfather(X,Y) :-
    grandparent(X,Y),
    male(X).

sister(X,Y) :-
/*  different(X,Y), */
    parent(Z,X),
    parent(Z,Y),
    female(X).
brother(X,Y) :-
/*  different(X,Y), */
    parent(Z,X),
    parent(Z,Y),
    male(X).

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Z) :-
    parent(X,Y),
    ancestor(Y,Z).

""")
}

def engine = new Prolog()
engine.theory = theory
pprint engine.solve('ancestor(tom,X).')
while(engine.hasOpenAlternatives()) {
    pprint engine.solveNext()
}

The Prolog engine will determine that Tom's ancestors are: bob, liz, ann, pat & jim.

ancestor(tom,X) = ancestor(tom,bob)
ancestor(tom,X) = ancestor(tom,liz)
ancestor(tom,X) = ancestor(tom,ann)
ancestor(tom,X) = ancestor(tom,pat)
ancestor(tom,X) = ancestor(tom,jim)
no solution found