Prolog is eminently suitable for solving

- timetabling
- resource allocation
- planning, i.e., finding suitable orderings of dependent tasks
- scheduling
- etc.

To efficiently solve combinatorial optimization tasks in many cases of practical relevance, Prolog provides a declarative solution called

In principle, constraints can be provided by any programming language. However, they blend in especially seamlessly into

For example, SICStus Prolog ships with:

- CLP(FD) for
**integers** - CLP(B) for
**Boolean**variables - CLP(Q) for
**rational numbers** - CLP(R) for
**floating point numbers**

Here is an example:

A chicken farmer also has some cows for a total
of **30 animals**, and the animals
have **74 legs** in all.

How many chickens does the farmer have?

How many chickens does the farmer have?

Answer:

?- Chickens + Cows #= 30, Chickens*2 + Cows*4 #= 74, Chickens in 0..sup, Cows in 0..sup.Note thatChickens = 23, Cows = 7.

In industrial and academic use, the efficiency of a Prolog system's constraint solvers is often an important factor when choosing a system. This is because many commercial use cases of Prolog also involve combinatorial optimization tasks.

Integers are the most relevant domain in practice, because all

Video: |

We can easily map this task to a combinatorial task over

For concreteness, let us colour the following map:

The following Prolog program describes the task using CLP(FD) constraints:

regions(Rs) :- Rs = [A,B,C,D,E,F], Rs ins 0..3, A #\= B, A #\= C, A #\= D, A #\= F, B #\= C, B #\= D, C #\= D, C #\= E, D #\= E, D #\= F, E #\= F.Disequality constraints (

To obtain more readable solutions, we can relate integers to colours. For example:?- regions(Rs), label(Rs).Rs = [0,1,2,3,0,1] ; Rs = [0,1,2,3,0,2] ; Rs = [0,1,2,3,1,2] ; Rs = [0,1,3,2,0,1] ; ... .

integer_color(0, red). integer_color(1, green). integer_color(2, blue). integer_color(3, yellow).This allows us to query:

?- regions(Rs), label(Rs),These solutions look like this:maplist(integer_color, Rs, Cs), pairs_keys_values(Pairs, [a,b,c,d,e,f], Cs). Rs = [0, 1, 2, 3, 0, 1], Cs = [red, green, blue, yellow, red, green],Pairs = [a-red, b-green, c-blue, d-yellow, e-red, f-green]; Rs = [0, 1, 2, 3, 0, 2], Cs = [red, green, blue, yellow, red, blue],Pairs = [a-red, b-green, c-blue, d-yellow, e-red, f-blue]; etc.

?- regions(Rs), Rs ins 0..2, label(Rs).Major advantages of using CLP(FD) constraints for combinatorial tasks include:false.

*compactness*and*elegance*of declarative descriptions*efficiency*due to powerful*pruning*- intelligent
*labeling strategies*guided by remaining domains - availability of
*global constraints*tailored for specific applications.

We distinguish between

- a set
*V*of**vertices** - a set
*A*of**arcs**, which are directed edges of the form*v*→*w*(*v*,*w*∈*V*).

arc_from_to(a, b). arc_from_to(b, c). arc_from_to(a, c). arc_from_to(c, a).Such a representation is called

A typical way to describe

path_from_to(A, A, _) --> [A]. path_from_to(A, B, Visited) --> [A], { arc_from_to(A, Next), maplist(dif(Next), Visited) }, path_from_to(Next, B, [A|Visited]).We keep track of vertices that have already been

Example queries:

?- phrase(path_from_to(a, c, []), Ps).Ps = "abc" ; Ps = "ac" ; false.?- phrase(path_from_to(a, To, []), Ps).To = a, Ps = "a" ; To = b, Ps = "ab" ; ... .

Using all solutions predicates, we can convert any temporal representation to a

?- findall(From-To, arc_from_to(From, To), Arcs).Another example:Arcs = [a-b,b-c,a-c,c-a].

?- bagof(To, arc_from_to(From, To), Arcs). From = a,With these predicates, we can obtain a representation of the graph in the form of anArcs = "bc"; From = b,Arcs = "c"; From = c,Arcs = "a".

?- findall(From-Ls, bagof(To, arc_from_to(From, To), Ls), Is).In Prolog, this is often a good representation for graphs. We can easily turn this into anIs = [a-"bc",b-"c",c-"a"].

Note that

vertices([a,b,c,d]).In the adjacency list representation, the isolated vertex

- a set
*N*of**nodes** - a set
*E*of undirected**edges**of the form*x*−*y*(*x*,*y*∈*N*).

edges([a-b,a-c,a-d,a-f, b-c,b-d, c-d,c-e, d-e,d-f, e-f]). edge(X, Y) :- edges(Es), ( member(X-Y, Es) ; member(Y-X, Es) ).Now we can query:

?- bagof(E, edge(N, E), Es). Es = "bcdf", N = a ; Es = "cda", N = b ; Es = "deab", N = c ; Es = "efabc", N = d ; Es = "fcd", N = e ; Es = "ade", N = f.An explicit representation is well suited for further analysis of the graph.

In Prolog, trees are of special significance because Prolog terms naturally correspond to trees.

For example, we can

tree(nil) --> []. tree(node(_, Left, Right)) --> [_], tree(Left), tree(Right).Sample query:

?- length(Ls, _), phrase(tree(T), Ls). Ls = [], T = nil ; Ls = [_A], T = node(_B,nil,nil) ; Ls = [_A,_B], T = node(_C,nil,node(_D,nil,nil)) ; Ls = [_A,_B], T = node(_C,node(_D,nil,nil),nil) ; Ls = [_A,_B,_C], T = node(_D,nil,node(_E,nil,node(_F,nil,nil))) ; ... .

- solve
**Sudoku**puzzles **N-queens**puzzle- more examples:
**https://github.com/triska/clpz**