Copy Page

You are not logged in. Any changes you make will be marked as anonymous. You may want to Log In if you already have an account. You can also Sign Up for a new account.

<p><a href="http://en.wikipedia.org/wiki/Constraint_programming">Constraint programming</a> 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 <a href="http://en.wikipedia.org/wiki/Prolog">Prolog</a> 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.</p>

<h2>Gecode/J</h2>

<p>Gecode/J is a Java interface for the Gecode C++ constraint programming library. Let's have a look at making the <a href="http://www.gecode.org/gecodej/doc/Money_8java-source.html">Money example</a> from the Gecode/J library a bit Groovier. If you haven't seen the example before, it involves solving the following puzzle:</p>

<p>How can I replace the letters in the puzzle with numbers so that the numbers add up in the expected way? See <a href="http://en.wikipedia.org/wiki/Send%2Bmore%3Dmoney">here</a> for further details.</p>

<h3>A little helper library</h3>

<p>First we can create a little helper library to make our subsequent code a little Groovier:</p>

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&lt;IntVar> v) {
    distinct(this, v, ICL_BND)
  }
  def expressionsEqual(Expr e1, Expr e2) {
    post(this, e1, IRT_EQ, e2)
  }
  def branchOverVariables(VarArray&lt;IntVar> v) {
    branch(this, v, BVAR_SIZE_MIN, BVAL_MIN)
  }
  def variableOverRange(v, r) {
      new IntVar(this, v, r.from, r.to)
  }
}
</pre></td></tr></table>

<h3>A Groovy Solution</h3>

<p>Here is how we could now code the solution.</p>

class Money extends GroovySpace {
  public VarArray&lt;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&lt;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&lt;IntVar>(this, share, money.letters)
  }
}

def opt = new Options("SEND+MORE=MONEY")
opt.gui = true
opt.parse(args)
opt.doSearch(new Money())
</pre></td></tr></table>

<p>It relies on the same <code>Options</code> class used in the original Java example.</p>

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

Summary:
        runtime:      3
        solutions:    1
        propagations: 11
        failures:     1
        clones:       2
        commits:      3
        peak memory:  6KB
</pre></td></tr></table>

<p>Running the program with the <code>-gui</code> command line argument yields the following GUI display:</p>

<p><img class="confluence-embedded-image" src="/download/attachments/231080191/GeoCode.gif?version=1&amp;modificationDate=1369477889819" data-image-src="/download/attachments/231080191/GeoCode.gif?version=1&amp;modificationDate=1369477889819" data-linked-resource-id="231376046" data-linked-resource-type="attachment" data-linked-resource-default-alias="GeoCode.gif" data-base-url="http://docs.codehaus.org" data-linked-resource-container-id="231080191" title="null > GeoCode.gif"></p>

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

<h2>Choco</h2>

<p><a href="http://choco-solver.net/">Choco</a> 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.</p>

<h3>Choco Magic Squares</h3>

<p>We'll look at solving the <a href="http://en.wikipedia.org/wiki/Magic_square">Magic Square</a> problem (though we haven't coded up making the diagonals add up too, just the rows and columns). Converting <a href="http://choco-solver.net/index.php?title=Magic_square">this example</a> to Groovy yields:</p>

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..&lt;n)
    for (j in 0..&lt;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..&lt;nsq)
    for (j in 0..&lt;i)
        p.post(p.neq(vars[i], vars[j]))

int[] coeffs = [1] * n

for (i in 0..&lt;n) {
    // all cols should add to sum
    IntVar[] col = (0..&lt;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..&lt;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..&lt;n) {
    for (j in 0..&lt;n)
        print vars[i * n + j].val.toString().padLeft(3)
    println()
}
</pre></td></tr></table>

<p>And has this output when run:</p>

<h3>Going Further</h3>

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

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
IntVar[] downdiag = (0..&lt;n).collect{ i -> vars[i * n + i] }
IntVar[] updiag = (0..&lt;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))
</pre></td></tr></table>

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

<p>Also add up to the magic square value:</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
IntVar[] leftkite = [vars[1], vars[4], vars[6], vars[13]]
p.post(p.eq(p.scalar(coeffs, leftkite), sum))
</pre></td></tr></table>

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

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
IntVar[] date = [vars[13], vars[14]]
int[] datecoeffs = [100, 1]
p.post(p.eq(p.scalar(datecoeffs, date), 1514))
</pre></td></tr></table>

<p>Let's see what solutions we now have:</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
def more = p.solve()
while (more) {
    println "Success at move: $p.solver.searchSolver.nodeCount"
    for (i in 0..&lt;n) {
        for (j in 0..&lt;n)
            print vars[i * n + j].val.toString().padLeft(3)
        println()
    }
    more = p.nextSolution()
}
</pre></td></tr></table>

<p>Which yields the following results:</p>

<table class="wysiwyg-macro" data-macro-name="code" data-macro-default-parameter="none" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGU6bm9uZX0&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
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
</pre></td></tr></table>

<p><img class="confluence-embedded-image image-right" src="/download/attachments/231080191/Melencolia_I.jpg?version=1&amp;modificationDate=1369477889791" data-image-src="/download/attachments/231080191/Melencolia_I.jpg?version=1&amp;modificationDate=1369477889791" data-linked-resource-id="231376045" data-linked-resource-type="attachment" data-linked-resource-default-alias="Melencolia_I.jpg" data-base-url="http://docs.codehaus.org" data-linked-resource-container-id="231080191" title="null > Melencolia_I.jpg"></p>

<p>The third solution in this list matches the famous Albrecht Dürer engraving.</p>

<p>This engraving has the following properties (from wikipedia):</p>

<blockquote>
<p><em>&quot;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.&quot;</em></p></blockquote>

<h3>Choco menu selection example</h3>

<p>Inspired by this <a href="http://xkcd.com/287/">xkcd cartoon</a>, here is a solution to a little menu selection problem.</p>

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

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 &lt;= 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()
}
</pre></td></tr></table>

<p>It produces this output:</p>

<table class="wysiwyg-macro" data-macro-name="noformat" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e25vZm9ybWF0fQ&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
Found a solution:
  7 * Mixed fruit
Found a solution:
  1 * Mixed fruit
  2 * Hot wings
  1 * Sampler plate
</pre></td></tr></table>

<h2>tuProlog</h2>

<p><a href="http://www.alice.unibo.it/tuProlog/">tuProlog</a> 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 <em>theories</em>; programatic theory construction using a Java-based API; and mechanisms to call back into Groovy and Java from Prolog.</p>

<h3>Magic Squares</h3>

<p>We can code up an order 3 Magic square problem as follows:</p>

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 &lt;&lt; /$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()
}
</pre></td></tr></table>

<p>The result is:</p>

<h3>Family Trees</h3>

<p>Finally, here is a Groovy version of the typical first Prolog program, which demonstrates the simplest of <em>relational reasoning</em>:</p>

/** 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()
}
</pre></td></tr></table>

<p>The Prolog engine will determine that Tom's ancestors are: <code>bob, liz, ann, pat &amp; jim</code>.</p>

<table class="wysiwyg-macro" data-macro-name="noformat" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e25vZm9ybWF0fQ&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
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
</pre></td></tr></table>