Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 19 Next »

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 just logic programming specific languages. Constraints differ from the common primitives of other programming languages in that they do not specify a step or sequence of 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 create a little helper library to make our Groovy code a little cleaner:




A Groovy Solution

Here is how we could code the solution.





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

Running this code (we used the latest HEAD version of Groovy on Java 6 with the following JVM argument, -Djava.library.path=C:\Geocode\bin) yields:




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

It would be fun to take the 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 a 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:





And has this output:





Going Further

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




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




Also add up to the magic square value:




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




Let's see what solutions we now have:




Which yields the following results:




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.






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.

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





The result is:

  2  7  6
  9  5  1
  4  3  8





Finally, here is a Groovy version of everyone's first Prolog program, which demonstrates the simplest of "relational reasoning":





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













  • No labels