Session 10: Constraint Logic Programming

So far we have been using SWI prolog. However, SWI cannot handle (some kinds of) constraints, we will use SICStus prolog for this.

Constraint Logic Programming with Reals

We need to tell SICStus to load its special CLP(R) library:
?- use_module(library(clpr)). Now try the following two exercises:

As a first intro to CLPR, try the following simple constraints (just type these queries):
- 3*X-2*Y=6,2*Y=X.
- 3*X-2*Y=6.
- {3*X-2*Y=6,2*Y=X}.
- {Z=<X-2,Z=<6-X,Z+1=2}.
- {Z=<X-2,Z=<6-X,Z+1=2},minimize(X).
This exercise is about mortgages. You are given P, the amount of money lent, T, the number of periodes in the mortgage, I, the interest rate on the mortgage and MP, the amount we pay back each period. We define 'the balance' after a number of periods as follows. After 0 periods the balance is simply P. After T periods (T>0) the balance is B1*(1+I)-MP, where B1 stands for the balance after T-1 periods (so this is a recursive definition).
First, write a predicate to calculate the balance after T periods using pure prolog. Then write this predicate using CLP. Can you calculate the amount of your mortgage given the other arguments with these predicates? Are there any arguments you can't calculate with the CLP version?

Finite Domain Constraint Logic Programming

Often the variables don't range over all real numbers, but over a finite set of elements. SICStus supports finite sets of integers as finite domains. With in/2 or domain/3 we can specify this domain, we can impose constraints with #>/2 #=/2 etc. More constraint expressing predicates can be found in Bratko, p.341-345. To use CLP on a finite domain, first load the necessary libraries (warning: these may interfere with the other clp-libraries, first restart your prolog engine to avoid problems):

:- use_module(library(clpfd)).

Before we start with the actual exercises, note that the predicate exactly/3 is often very handy when solving CLP-problems. This predicate was discussed in the lectures, it checks (using CLP) whether an integer occurs in a list of integers exactly N times.

exactly(_El, [], 0).
exactly(El, [H|List], N) :-
    El #= H #<=> B,
    N #= M+B,
    exactly(El, List, M).

Now try to solve the following exercises:

A poor criminal wants to break into a safe. He needs to find the combination of the safe: 9 digits in total. He knows that all digits are different, that all digits are in the range 1..9 and that the 1st digit is not 1, the 2nd digit is not 2, and so on ... . Moreover, the difference between the 4th and the 6th digit is equal to the 7th digit, and the product of the first three digits is equal to the sum of the last two digits. The sum of the 2nd, 3th and 6th digit is less than the 8th digit, and also the last digit is less than the 8th digit. Please help our criminal break the safe (using CLP).
In a game, exactly six inverted cups stand side by side in a straight line, and each has exactly one ball hidden under it. The cups are numbered consecutively from 1 through 6. Each of the balls is painted in a different color: green, magenta, orange, purple, red, and yellow. Suppose you know that:
- The magenta ball is hidden under cup 1.
- The green ball is hidden under cup 5.
- The purple ball is hidden under a lower-numbered cup than the orange ball.
- The red ball is hidden under a cup immediately adjacent to the cup under which the magenta ball is hidden.
Write a CLP-program to find out which balls are under which cups. Are there multiple possibilities?
You are organizing a large party. There will be N tables in the room, with M chairs around each table. Guests are assigned numbers from 1 to MN. You need to assign each guest a table so that two conditions are satisfied. First, some guests like each other and want to sit together: you are given a set Likes of pairs of guests and for every pair (i,j) in Likes, guests i and j should be assigned the same table. Second, some guests dislike each other and want to sit at different tables: you are given a set DisLikes of pairs of guests and for every pair (i,j) in DisLikes, guests i and j should be assigned different tables. Write a CLP-program that (if possible) finds such a seating arrangement.