Constraint Logic Programming (CLP) (Bratko, Chapter 7)

Constraint Logic Programming (CLP) (Bratko, Chapter 7)

It is a powerful paradigm for formulating and solving problems that can be naturally defined in terms of constraints among a set of variables. Solving such problems consists of finding such combinations of values of the variables that satisfy the constraints (called constraint satisfaction). CLP combines constraint approach and logic programming.

Additional resources https://en.wikibooks.org/wiki/Prolog/Constraint_Logic_Programming ;

https://www.swi-prolog.org/pldoc/doc/_SWI_/library/clp/clpfd.pl

 

Type the following and save as clp.pl

%Simple Constraints in Prolog

% Hobbies and Person (2 constraints)

%Exercise 1 – find the persons with common hobbies by conjoining two constraints with a comma

 

%Facts

hobby(joan, sewing).

hobby(sam, diving).

hobby(jean, diving).

hobby(jeanne, cooking).

hobby(anne, cooking).

hobby(jan, cooking).

 

Load clp.pl using consult.

Type the following queries:

?- hobby(Person1, Hobby), hobby(Person2, Hobby), dif(Person1, Person2).

 

 

 

Constraint Logic Programming Sudoku

https://www.swi-prolog.org/pldoc/man?section=clpfd-sudoku

Type the following codes and save as sudoku.pl

:- use_module(library(clpfd)).

:- use_module(library(clpr)).

 

sudoku(Rows) :-

length(Rows, 9), maplist(same_length(Rows), Rows),

append(Rows, Vs), Vs ins 1..9,

maplist(all_distinct, Rows),

transpose(Rows, Columns),

maplist(all_distinct, Columns),

Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],

blocks(As, Bs, Cs),

blocks(Ds, Es, Fs),

blocks(Gs, Hs, Is).

 

blocks([], [], []).

blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-

all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),

blocks(Ns1, Ns2, Ns3).

 

problem(1,     [[_,_,_,_,_,_,_,_,_],

[_,_,_,_,_,3,_,8,5],

[_,_,1,_,2,_,_,_,_],

[_,_,_,5,_,7,_,_,_],

[_,_,4,_,_,_,1,_,_],

[_,9,_,_,_,_,_,_,_],

[5,_,_,_,_,_,_,7,3],

[_,_,2,_,1,_,_,_,_],

[_,_,_,_,4,_,_,_,9]]).

 

 

Query

Type the following to run a query

(note: maplist: https://www.swi-prolog.org/pldoc/man?predicate=maplist/2)

?- problem(1, Rows), sudoku(Rows), maplist(portray_clause, Rows).

 

 

Example 3

https://www.swi-prolog.org/man/clpfd.html

As an example of a constraint satisfaction problem, consider the cryptoarithmetic puzzle SEND + MORE = MONEY, where different letters denote distinct integers between 0 and 9. It can be modeled in CLP(FD) as follows:

%https://www.swi-prolog.org/man/clpfd.html

% Semantics of signs – see bratko page 192

% #= equal

% #\= not equal

 

:- use_module(library(clpfd)).

:- use_module(library(clpr)).

 

 

puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-

Vars = [S,E,N,D,M,O,R,Y],

Vars ins 0..9,

all_different(Vars),

S*1000 + E*100 + N*10 + D +

M*1000 + O*100 + R*10 + E #=

M*10000 + O*1000 + N*100 + E*10 + Y,

M #\= 0, S #\= 0.

 

 

Run the query

?- puzzle(As+Bs=Cs).

[note: 5..8 means between 5 and 8; _8320 – a variable, solution is non-deterministic].

To make it deterministic, type the query below. Note label will force an assignment of a value to each variable to the solution above.

?- puzzle(As+Bs=Cs), label(As).

 

 

 

Schedule with and without constraints

Look at Bratko, pages 429-436.

Remember to start your program with these library imports (since it is a CLP problem)

:- use_module(library(clpfd)).

:- use_module(library(clpr)).

 

 

Fitting  in rectangles within a box

Look at Bratko, pages 188-191.

Remember to start your program with these library imports (since it is a CLP problem)

:- use_module(library(clpfd)).

:- use_module(library(clpr)).

 

 

 

Problem Solving

Move boxes (not a CLP problem)

https://www.cpp.edu/~jrfisher/www/prolog_tutorial/2_19.html

 

Move pegs

http://www.cs.toronto.edu/~sheila/384/w11/simple-prolog-examples.html

 

Tower of Hanoi

http://www.aistudy.co.kr/program/prolog/visual_prolog/Towers%20of%20Hanoi.htm

https://www.cl.cam.ac.uk/teaching/1011/Prolog/Prolog10MQuestionsR1.pdf

https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html

 

 

 

Natural Language Processing

https://www.cs.unm.edu/~luger/ai-final2/CH8_Natural%20Language%20Processing%20in%20Prolog.pdf

This content is for IT & Web programming task members only.
Log In Register