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 46 Current »

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:

A Groovy Solution

Here is how we could now code the solution.

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:

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:

And has this output when run:

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."

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.

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:

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:

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