A Prolog Tutorial for CS3243

Recall the midterm question:

Variables: A, B, C, D.
DA: {1,2,3,4,5}
DB: {3,6}
DC: {2,4,6}
DD: {1,2,3,5}

Constraints:
1. All variables must have different values.
2. A < B
3. C < A

Let's now solve it using Prolog. How do you do it? You have to create a knowledge base of facts about solving the puzzle. In your homework, we can divide the knowledge needed to solve the problem into two parts: a part about the generic problem (the rules and strategies) and a part about the specific problem instance. In your homework you should separate these two classes of knowledge where possible, but for this sample case, we're going to keep them together.

A key thing to remember is that in Prolog you cannot bind (assign) values to variables in your knowledge base. You can assert facts about constants. So we cannot directly say that variable can take on a certain domain. Instead we do something like:

domainA(1).
domainA(2).
domainA(3).
...
domainD(3).
domainD(5).

This asserts a set of facts that describe the domains of our four variables. The first one can be interpreted as "1 is a valid domain value for A."

Let's try a first pass at solving the problem. We then can write a rule (not a fact) to assign values to variables. Think about this first, write down your rule and check it. This could be written as:

solve(A,B,C,D):-domainA(A),domainB(B),domainC(C),domainD(D).

This defines a solution of four variables (incidentally named A, B, C and D) to have to satisfy the four clauses on the right of the right. Each of the four will be satisfied, in turn. Note that this is a rule, not a query. Go ahead and enter the 14 facts and 1 rule into a text file called facts.pl and save your file.

Run prolog, and you should see the ?- prompt. Type consult('facts.pl'). (no spaces, with the period) to load the knowledge base into prolog. Afterwards, you can verify what's there by typing listing. to see what prolog knows about.

To actually solve the CSP (well, we don't have constraints yet), during run of prolog we can type a query. We can write solve(A,B,C,D). to have prolog go off and find a possible binding of values to variables. Try it. Prolog will print the first assignment it finds and wait for you. If you type a return, it will stop, or if you type a semicolon (';'), it will give the next alternative.

Ok, great. How do you quit prolog? Well, just type halt.. This will exit prolog.

How about the rest of the constraints? Try them adding them incrementally. How do you add the inequalities? Well these are easy, we add two additional clauses to the solve/4 rule in the knowledge base. Change it to:

solve(A,B,C,D):-domainA(A),domainB(B),domainC(C),domainD(D),
A<B,C<A.
and save the file, invoke prolog and try the query again. You'll see that the answers come up nicely. What about the all different constraint? We can encode that as binary, not-equal constraints. Not equal is written as =/= in prolog. So the final version is:
solve(A,B,C,D):-domainA(A),domainB(B),domainC(C),domainD(D),
A<B,C<A,
A=\=B,A=\=C,A=\=D,B=\=C,B=\=D,C=\=D.

We also have shortcuts to writing the big mess of 14 facts in the beginning. We can use the member/2 predicate that takes a variable and a list. Look in the SWI Prolog if you need help with it. Our final program is:

domainA(X):-member(X,[1,2,3,4,5]).
domainB(X):-member(X,[3,6]).
domainC(X):-member(X,[2,4,6]).
domainD(X):-member(X,[1,2,3,5]).

solve(A,B,C,D):-domainA(A),domainB(B),domainC(C),domainD(D),
A<B,C<A,
A=\=B,A=\=C,A=\=D,B=\=C,B=\=D,C=\=D.

Remember that for separate rules, variables don't refer to the same variable ("standardizing apart" as referred to in lecture). 'X' can be any variable, it's just a placeholder.

Output time

Great, so you can run a prolog program and code a knowledge base. How do you output the bound variables so that they can be accessed? There are special predicates for this in 3.17 in the prolog documentation. Learn the write() and the nl special rules. You can add these to the solve() query in the above examples to get the output on standard output.

Wrapping it together

Your submission needs to run without having to invoke prolog and manually type in the consult() and query commands. You can save these to a file to serve as standard input (just as we did for assignment #1). Once the commands are saved in a file, you can redirect standard input to the prolog command. Here's a sample file which I called run.pl which can be sent to prolog.

consult('facts.pl').
solve(A,B,C,D),
    write('A = '),write(A),nl,
    write('B = '),write(B),nl,
    write('C = '),write(C),nl,
    write('D = '),write(D),nl.
halt.

You then run this on the command line by pl < run.pl.

Tracing and Debugging

Tracing and debugging you'll have to follow in Prolog on your own. Look at the SWI documentation, in section 3.37, at the trace/0 and trace/1 rules. Use these facilities to help you optimize how you place the clauses and subgoals in your knowledge base.


Min-Yen Kan <kanmy@comp.nus.edu.sg>
Created on: Fri Mar 17 15:56:13 2006 | Version: 1.0 | Last modified: Fri Mar 17 15:57:34 2006