T-93.540 Logic Programming

Martti Meri
25.10.2004

Handson exercises part 2, Eclipse

 Check the course home-page for instuctions on
 where and how eclipse is operational for you.
 In general you start it by calling:

 eclipse

 programs you have edited can be loaded by call:

 [myprog].

 and predicates are called in the same way
 as in Prolog (see swi-prolog instructions.


 You can exit eclipse by calling:

 halt.
  

1. Propositional SAT to Eclipse encoding

 Use Eclipse and the final domain library of Eclipse for
 finding the models of the propositional satisfiability 
 problem. The formula is in conjunctive normal form, and
 is expressed here using a syntacs directly applicable in Eclipse.
       A #\/ #\+ B #\/      C,
   #\+ A #\/     E #\/  #\+ F,
       C #\/ #\+ D #\/      F,
   #\+ A #\/ #\+ D #\/      F,
       B #\/     D #\/  #\+ F,
       B #\/     E #\/      C,
       A #\/ #\+ C #\/      F,
   #\+ B #\/ #\+ C #\/      F,
       A #\/ #\+ D #\/  #\+ F,
   #\+ A #\/ #\+ B #\/  #\+ F,
 
 operators:
 #\+ +E1       E1 is false, i.e. the logical negation of the 
               constraint is expression is imposed
 +E1 #\/ +E2   At least one of the constraint expressions
               E1 and E2 is true. 

 Advice: 
 a. You need to indicate that you use the fd library
 b. Define the truth distribution as a list of the boolean
    variables in the formula.  Bind the list to a variable
    (for instance named TruthDistr)
 c. Manually encode the sat problem (cut and paste from above) 
 d. Call labeling -predicate with the TruthDistr as an
    argument.

 Parts b-d are within a body of a predicate , to get
 the results out let the predicate have the TruthDistr
 as an argument.
 For of the library usage declaration write the line 
 :- use_module(library(fd)).
 in the beginning of you program file.

2. Very simple scheduling

 You need to wake up 1 hour before taking a bus to work,
 The bus trip takes at least 1 hour.  You leave work not 
 earlier than after 8 hours,
 after which it takes you more than 1 hour on a bus before being 
 able to turn on the TV at home.  You always watch TV more than
 3 ours after which you go to bed.
 Use variables WakeUp,TakeBus1,StartWork,TakeBus2,TurnTVOn,FallASleep
 and make a scheduler for you day.  Let the variables be in 
 range 1..24.
 Predicate #< can be used to create constraints.

 Test 1 :
 schedule(Day).   --> gives you so intervals

 Test 2 :
 WU::6..8,FAS::19..20,schedule([WU,TB1,SW,TB2,TV,FAS]).  --> a thighter schedule

3. N-Queens

 Solve the N-Queens problem.  Below a call with N = 4.

 Test:  nqueens(4,C).
 C = [2, 4, 1, 3]     More? (;) 
 C = [3, 1, 4, 2]     More? (;) 
 no (more) solution.

 An answer is from the Eclipse Library Manual (v. 5 p. 15).
 There the problem of homomorphic answers to the problem
 is also attacked elecantly.
 Uses also min_max predicate that is usefull in optimization.

4. Planning in Politics

 You are secretary of a political party and try to get
 some eager voters.  You have three methods of acting
 in this filed.
 1. get individual voters, This takes 2 units of time and
    causes 1 unit of pain to you.
 2. get groups of voters,  This gets you 3 voters, takes 5
    units of time and causes 4 units of pain.

 But there is also an unofficial method,  
 3. you just play some dirty trick on some of the voters, you
    loose 10 voters put also loose 11 units of pain,
    which just makes you feel great ( the pain of the
    voters is not counted in this game).  Besides, this
    is fast relief, it just takes 1 unit of time.
 You know that you need 5 to 6 voters and that you are not
 interested in plans that take more than 10 units of time 
 or cause more than 10 units of pain.
 What kinds of plans can you apply to reach these objectives?

The bottom level facts could be coded in the following way:

task(1,2,1,1).
task(2,5,4,3).
task(3,1,-11,-10).

    labeling1(Rest).

And the topmost be:

plan(N,Plan) :-
    make_plan(N,Plan),
    Plan :: 1..4,
    evaluate_plan(Plan,0,0,0,Du,Pa,Pe),
    Pe #>= 5,
    Pe #<= 6,
    Du #<= 10,
    Pa #<= 10,
    make_cost(0,Plan,C),
    min_max(labeling1(Plan),C).

(The extra constraints of for the people and, duraition and pain
are a bit  inelegant in the body of the predicate, sorry.  The
idea was to limit the search by force here.)

 Tests: (The first argument is the length of the plan
         being searched in that call).

 plan(5,P).
 Found a solution with cost 5
 P = [1, 1, 1, 1, 1]     More? (;) 
 no (more) solution.

 plan(4,P).
 no (more) solution.

 plan(3,P).
 Found a solution with cost 6
 P = [1, 1, 2]     More? (;) 
 Found a solution with cost 6
 P = [1, 2, 1]     More? (;) 
 Found a solution with cost 6
 P = [2, 1, 1]     More? (;) 
 no (more) solution.

It is recommended that you try to solve the problems yourself, the Eclipse User Manual and The Library Reference Manual provide valuable insight to constraint logic programmin. For these problems the finite domains library part in the Library Reference manual is sufficient. Answers to problems