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