Constraint programming can get some getting used to. In the usual programming frame of mind (whether with functional or imperative languages) you think of the algorithm and specify to the computer, via your code, exactly what steps to go through in order to solve the problem.
With constraint programming, you don’t tell the computer what to do. You describe in detail the nature of the problem and the computer does the rest.
Einstein’s riddle is usually given as an example to be solved with constraint programming, but to be different, I’ll show something a bit trickier. This is the problem (it’s named “Meeting the Challenge”):
Eight married couples meet to lend one another some books. Couples have the same surname, employment and car. Each couple has a favourite colour. Furthermore we know the following facts:
1. Daniella Black and her husband work as Shop-Assistants.
2. The book “The Seadog” was brought by a couple who drive a Fiat and love the colour red.
3. Owen and his wife Victoria like the colour brown.
4. Stan Horricks and his wife Hannah like the colour white.
5. Jenny Smith and her husband work as Warehouse Managers and they drive a Wartburg.
6. Monica and her husband Alexander borrowed the book “Grandfather Joseph”.
7. Mathew and his wife like the colour pink and brought the book “Mulatka Gabriela”.
8. Irene and her husband Oto work as Accountants.
9. The book “We Were Five” was borrowed by a couple driving a Trabant.
10. The Cermaks are both Ticket-Collectors who brought the book “Shed Stoat”.
11. Mr and Mrs Kuril are both Doctors who borrowed the book “Slovacko Judge”.
12. Paul and his wife like the colour green.
13. Veronica Dvorak and her husband like the colour blue.
14. Rick and his wife brought the book “Slovacko Judge” and they drive a Ziguli.
15. One couple brought the book “Dame Commissar” and borrowed the book “Mulatka Gabriela”.
16. The couple who drive a Dacia, love the colour violet.
17. The couple who work as Teachers borrowed the book “Dame Commissar”.
18. The couple who work as Agriculturalists drive a Moskvic.
19. Pamela and her husband drive a Renault and brought the book “Grandfather Joseph”.
20. Pamela and her husband borrowed the book that Mr and Mrs Zajac brought.
21. Robert and his wife like the colour yellow and borrowed the book “The Modern Comedy”.
22. Mr and Mrs Swain work as Shoppers.
23. “The Modern Comedy” was brought by a couple driving a Skoda.
Who likes Violet? And can you find out everything about everyone from this?
A constraint programming solution, using Choco is given below. This should give you some insight into the nature of this type of problem solving.
import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.variables.integer.*;
import choco.kernel.solver.variables.integer.IntDomainVar;
import java.util.HashMap;
public class Meeting
{
public static void main(String[] args)
{
int nElements = 8;
String[] _attr = { "SURNAME", "EMPLOYMENT", "CAR", "COLOR", "MAN", "WIFE", "LENT", "BORROWED" };
int SURNAME = 0; int EMPLOYMENT = 1; int CAR = 2; int COLOR = 3;
int MAN = 4; int WIFE = 5; int LENT = 6; int BORROWED = 7;
String[] Surname = { "Black", "Horricks", "Smith", "Cermaks", "Kuril", "Dvorak", "Swain", "Zajac" };
int BLACK = 0; int HORRICKS = 1; int SMITH = 2; int CERMAKS = 3; int KURIL = 4;
int DVORAK = 5; int SWAIN = 6; int ZAJAC = 7;
String[] Employment = { "Shop-Assistants", "Warehouse Managers", "Accountants", "Ticket-Collectors",
"Doctors", "Teachers", "Agriculturalists", "Shoppers" };
int SHOP_ASSISTANTS = 0; int WAREHOUSE_MANAGERS = 1; int ACCOUNTANTS = 2;
int TICKET_COLLECTORS = 3; int DOCTORS = 4; int TEACHERS = 5; int AGRICULTURALISTS = 6;
int SHOPPERS = 7;
String[] Car = { "Fiat", "Wartburg", "Trabant", "Ziguli", "Dacia", "Moskvic", "Renault", "Skoda" };
int FIAT = 0; int WARTBURG = 1; int TRABANT = 2; int ZIGULI = 3; int DACIA = 4;
int MOSKVIC = 5; int RENAULT = 6; int SKODA = 7;
String[] Color = { "red", "brown", "white", "pink", "green", "blue", "violet", "yellow" };
int RED = 0; int BROWN = 1; int WHITE = 2; int PINK = 3; int GREEN = 4;
int BLUE = 5; int VIOLET = 6; int YELLOW = 7;
String Man[] = { "Owen", "Stan", "Alexander", "Mathew", "Oto", "Paul", "Rick", "Robert" };
int OWEN = 0; int STAN = 1; int ALEXANDER = 2; int MATHEW = 3; int OTO = 4;
int PAUL = 5; int RICK = 6; int ROBERT = 7;
String[] Wife = { "Daniella", "Victoria", "Hannah", "Jenny", "Monica", "Irene", "Veronica", "Pamela" };
int DANIELLA = 0; int VICTORIA = 1; int HANNAH = 2; int JENNY = 3; int MONICA = 4;
int IRENE = 5; int VERONICA = 6; int PAMELA = 7;
String[] Books = { "The Seadog", "Mulatka Gabriela", "Shed Stoat", "Slovacko Judge", "Dame Commissar",
"Grandfather Joseph", "The Modern Comedy", "We Were Five" };
int THE_SEADOG = 0; int MULATKA_GABRIELA = 1; int SHED_STOAT = 2; int SLOVACKO_JUDGE = 3;
int DAME_COMMISSAR = 4; int GRANDFATHER_JOSEPH = 5; int THE_MODERN_COMEDY = 6;
int WE_WERE_FIVE = 7;
String attvals[][] = { Surname, Employment, Car, Color, Man, Wife, Books, Books };
CPModel model = new choco.cp.model.CPModel();
// We'll assume the couples are numbered 0 to 7.
// The value of the variable represents the couple belongs to,
// i.e if x[SURNAME][BLACK] is 6 then couple with surname Black is couple number 6).
IntegerVariable[][] x = new IntegerVariable[nElements][nElements];
for (int i=0; i<nElements; i++)
{
x[i] = choco.Choco.makeIntVarArray( _attr[i], nElements, 0, nElements-1);
// For a given attribute, Each different attribute value belongs to a
// different couple number.
model.addConstraint(allDifferent( x[i] ));
}
//1. Daniella Black and her husband work as Shop-Assistants.
model.addConstraint( eq( x[SURNAME][BLACK],
x[EMPLOYMENT][SHOP_ASSISTANTS] ));
model.addConstraint( eq( x[WIFE][DANIELLA],
x[EMPLOYMENT][SHOP_ASSISTANTS] ));
//2. The book "The Seadog" was brought by a couple who drive a Fiat and love the color red.
model.addConstraint( eq( x[LENT][THE_SEADOG],
x[CAR][FIAT] ));
model.addConstraint( eq( x[LENT][THE_SEADOG],
x[COLOR][RED] ));
//3. Owen and his wife Victoria like the color brown.
model.addConstraint( eq( x[MAN][OWEN],
x[WIFE][VICTORIA] ));
model.addConstraint( eq( x[MAN][OWEN],
x[COLOR][BROWN] ));
//4. Stan Horricks and his wife Hannah like the color white.
model.addConstraint( eq( x[MAN][STAN],
x[WIFE][HANNAH] ));
model.addConstraint( eq( x[MAN][STAN],
x[COLOR][WHITE] ));
//5. Jenny Smith and her husband work as Warehouse Managers and they drive a Wartburg.
model.addConstraint( eq( x[WIFE][JENNY],
x[SURNAME][SMITH] ));
model.addConstraint( eq( x[WIFE][JENNY],
x[EMPLOYMENT][WAREHOUSE_MANAGERS] ));
model.addConstraint( eq( x[WIFE][JENNY],
x[CAR][WARTBURG] ));
//6. Monica and her husband Alexander borrowed the book "Grandfather Joseph".
model.addConstraint( eq( x[WIFE][MONICA],
x[MAN][ALEXANDER] ));
model.addConstraint( eq( x[WIFE][MONICA],
x[BORROWED][GRANDFATHER_JOSEPH] ));
//7. Mathew and his wife like the color pink and brought the book "Mulatka Gabriela".
model.addConstraint( eq( x[MAN][MATHEW],
x[COLOR][PINK] ));
model.addConstraint( eq( x[MAN][MATHEW],
x[LENT][MULATKA_GABRIELA] ));
//8. Irene and her husband Oto work as Accountants.
model.addConstraint( eq( x[MAN][OTO],
x[WIFE][IRENE] ));
model.addConstraint( eq( x[MAN][OTO],
x[EMPLOYMENT][ACCOUNTANTS] ));
//9. The book "We Were Five" was borrowed by a couple driving a Trabant.
model.addConstraint( eq( x[BORROWED][WE_WERE_FIVE],
x[CAR][TRABANT] ));
//10. The Cermaks are both Ticket-Collectors who brought the book "Shed Stoat".
model.addConstraint( eq( x[SURNAME][CERMAKS],
x[EMPLOYMENT][TICKET_COLLECTORS] ));
model.addConstraint( eq( x[SURNAME][CERMAKS],
x[LENT][SHED_STOAT] ));
//11. Mr and Mrs Kuril are both Doctors who borrowed the book "Slovacko Judge".
model.addConstraint( eq( x[SURNAME][KURIL],
x[EMPLOYMENT][DOCTORS] ));
model.addConstraint( eq( x[SURNAME][KURIL],
x[BORROWED][SLOVACKO_JUDGE] ));
//12. Paul and his wife like the color green.
model.addConstraint( eq( x[MAN][PAUL],
x[COLOR][GREEN] ));
//13. Veronica Dvorak and her husband like the color blue.
model.addConstraint( eq( x[SURNAME][DVORAK],
x[WIFE][VERONICA] ));
model.addConstraint( eq( x[SURNAME][DVORAK],
x[COLOR][BLUE] ));
//14. Rick and his wife brought the book "Slovacko Judge" and they drive a Ziguli.
model.addConstraint( eq( x[MAN][RICK],
x[WIFE][VERONICA] ));
model.addConstraint( eq( x[MAN][RICK],
x[LENT][SLOVACKO_JUDGE] ));
model.addConstraint( eq( x[MAN][RICK],
x[CAR][ZIGULI] ));
//15. One couple brought the book "Dame Commissar" and borrowed the book "Mulatka Gabriela".
model.addConstraint( eq( x[LENT][DAME_COMMISSAR],
x[BORROWED][MULATKA_GABRIELA] ));
//16. The couple who drive a Dacia, love the color violet.
model.addConstraint( eq( x[CAR][DACIA],
x[COLOR][VIOLET] ));
//17. The couple who work as Teachers borrowed the book "Dame Commissar".
model.addConstraint( eq( x[EMPLOYMENT][TEACHERS],
x[BORROWED][DAME_COMMISSAR] ));
//18. The couple who work as Agriculturalists drive a Moskvic.
model.addConstraint( eq( x[EMPLOYMENT][AGRICULTURALISTS],
x[CAR][MOSKVIC] ));
//19. Pamela and her husband drive a Renault and brought the book "Grandfather Joseph".
model.addConstraint( eq( x[WIFE][PAMELA],
x[CAR][RENAULT] ));
model.addConstraint( eq( x[WIFE][PAMELA],
x[LENT][GRANDFATHER_JOSEPH] ));
//20. Pamela and her husband borrowed the book that Mr and Mrs Zajac brought.
for (int book = 0; book<nElements; book++)
model.addConstraint( ifOnlyIf( eq( x[WIFE][PAMELA],
x[BORROWED][book] ),
eq( x[SURNAME][ZAJAC],
x[LENT][book])));
//21. Robert and his wife like the color yellow and borrowed the book "The Modern Comedy".
model.addConstraint( eq( x[MAN][ROBERT],
x[COLOR][YELLOW] ));
model.addConstraint( eq( x[MAN][ROBERT],
x[BORROWED][THE_MODERN_COMEDY] ));
//22. Mr and Mrs Swain work as Shoppers.
model.addConstraint( eq( x[SURNAME][SWAIN],
x[EMPLOYMENT][SHOPPERS] ));
//23. "The Modern Comedy" was brought by a couple driving a Skoda.
model.addConstraint( eq( x[LENT][THE_MODERN_COMEDY],
x[CAR][SKODA] ));
// Create the solver
CPSolver solver = new CPSolver();
solver.read( model );
// solver.solve();
solver.solveAll();
if (!solver.isFeasible())
return;
int colWidth[] = calcAttrWidths(_attr, attvals);
do
{
IntDomainVar[][] s = new IntDomainVar[nElements][nElements];
HashMap<Integer, String[]> couples = new HashMap<Integer, String[]>();
System.out.print( " ");
for (int i=0; i<nElements; i++)
{
s[i] = solver.getVar( x[i] );
couples.put( i, new String[ nElements ] );
System.out.print( padRight( _attr[i], colWidth[i]) );
}
System.out.println();
for (int i=0; i<nElements; i++) // iterate over attributes
for (int j=0; j<nElements; j++) // iterate over attribute values
{
// s[i][j].getVal() is the couple number where attribute i
// has an attribute value of j
int coupleNumber = s[i][j].getVal();
String[] attrs = couples.get( coupleNumber );
attrs[i] = attvals[i][j];
}
for (int couple=0; couple<nElements; couple++)
{
System.out.print( "couple " + (couple+1) + ":" );
String[] attrs = couples.get( couple );
for (int attr=0; attr<nElements; attr++)
System.out.print( padRight( attrs[ attr ], colWidth[ attr ] ) );
System.out.println();
}
System.out.println("---------------------");
solver.printRuntimeStatistics();
}
while (solver.nextSolution() == Boolean.TRUE);
}
public static String padRight(String s, int n)
{
return String.format("%1$-" + n + "s", s);
}
public static int[] calcAttrWidths( String[] attrs, String[][] attvals )
{
int nElements = attrs.length;
int[] atmax = new int[ nElements ];
for (int i=0; i<nElements; i++)
atmax[i] = attrs[i].length()+1;
for (int i=0; i<nElements; i++)
{
int max = atmax[i];
for (int j=0; j<nElements; j++)
{
int lenVal = attvals[i][j].length();
if ( max < lenVal )
max = lenVal;
}
atmax[i] = max + 1;
}
return atmax;
}
}
