AI Labs - Constraint Logic Programming

Lab 13/12/2006

Part 1: SWI-Prolog

On the laboratories PCs it is installed the SWI Prolog version 5.6.20. The Prolog interpreter can be started with the command plwin.exe, more informations can be found in the SWI Prolog documentation or FAQ. Basically the main commands and features are:

• You are presented with the prompt | ?- , you can ask queries or issue commands. Every line should be terminated by a full stop.
  
• To quit the top-level type the end-of-file key sequence (Ctl-D) or its term representation: end_of_file.
• To load a prolog program (a list of clause) you should use the form:
  ?- [test].
  where your program is stored in the file test.pl (note the extension).
• You can directly enter the program from the terminal by specifying user as program file. The program should be terminated by end_of_file. or (Ctl-D).
  
  ?- [user].
|: isEven(0).
|: isEven(s(s(X))) :- isEven(X).
|: % user://1 compiled 0.00 sec, 408 bytes

Yes

  
  
• The predicate listing/0 shows the stored program. E.g.,
  ?- listing.

% Foreign: rl_add_history/1

isEven(0).
isEven(s(s(A))) :-
        isEven(A).

% Foreign: rl_read_init_file/1

Yes

  
• Under the top-level it is possible to interrupt the execution of a query by typing the interruption key (Ctl-C).
• If you want to start again from scratch then exit the interpreter. If you reload a program the predicates with the same name of the loading ones are retracted from the database before the actual loading.
• Undefined predicates raise an error, instead of a failure.
  

Exercise 1.1

Suppose we are working with the following knowledge base:

hasWand(harry).
quidditchPlayer(harry).
wizard(ron).
wizard(X) :- hasBroom(X),hasWand(X).
hasBroom(X) :- quidditchPlayer(X).

How does Prolog respond to the following queries? (use the SWI-Prolog to verify the answers)

1. wizard(ron).


2. wizard(hermione).


3. wizard(harry).


4. wizard(Y).


Exercise 1.2: CSP in Prolog

Find all the colour assignment for the map of Australia using the following Prolog code.

colourable([WA, SA, NT, Q, NSW, V, T]) :-
	        rgb(WA), rgb(SA), rgb(NT), rgb(Q), rgb(NSW), rgb(V), rgb(T),
	        WA \= NT, NT \= Q, Q \= NSW, NSW \= V,
	        SA \= WA, SA \= NT, SA \= Q, SA \= NSW, SA \= V.

rgb(red).
rgb(green).
rgb(blue).

Part 2: Using CLP(FD) solver

Use the CLP(FD) solver of SWI-Prolog to solve the following problems. You can use the example shown during the lecture as a skeleton to write the solution. Examples, together with a description of the predicates available in the CLP(FD) library, can be found here.
Remember to include the line

to import the CLP(FD) library. Note that CLP numeric predicates are prepended with the # symbol.

Exercise 2.1: Cryptarithmetic

Find the solution to the cryptarithmetic puzzle TWO + TWO = FOUR by encoding the problem using the CLP(FD) solver of the SWI-Prolog.

Exercise 2.2: Vertex colouring

Given a graph and a fixed number of colours, the problem consists in assigning a colour to each vertex of the graph. Colouring must be proper, in the sense that no adjacent vertices are assigned the same colour. Use the SWI-Prolog CLP(FD) solver to find the 5-colouring (i.e. using 5 colours) of the following graph:

Exercise 2.3: Scheduling and Constraint Logic Programming

A scheduling problem consists in a given set of tasks with associated duration; in addition, tasks may have precedence constraints among them (e.g. debugging must be performed after the code has been written). The purpose of this exercise is to show how to use a Constraint Logic Program system to devise a scheduling.

In this lab we use the following encoding of the problem into CSP over the integer domain:

• Assume a fixed time limit for the schedule (e.g. each task should be completed within n time units).
• Each task is represented by a different variable which specifies the starting time unit of the task.
• Precedence constraints among the tasks are encoded as inequalities among the corresponding task variables. For example, if task A of duration D_A should precede task B, then we impose A + D_A =< B.
• We introduce a new auxiliary task End which should be performed after any other task. The initial time unit of this task correspond to the whole duration of the schedule.

Consider the following scheduling problem with 7 different tasks:

Task	Duration
t1	16
t2	6
t3	13
t4	7
t5	5
t6	18
t7	4

and the following precedence relation:

• t1 before t4
• t1 before t7
• t3 before t7
• t5 before t6