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, 1, 0, 3] ; Rs = [0, 1, 2, 1, 3, 3] ; Rs = [0, 1, 2, 3, 0, 1] ; etc.

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 = [a, b, c] ; Ps = [a, c] ; false.?- phrase(path_from_to(a, To, []), Ps).To = a, Ps = [a] ; To = b, Ps = [a, b] ; etc.

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 = [b, c] ;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-[b, c], 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 **timetabling**for schools**sports scheduling****N-queens**puzzle- more examples:
**https://github.com/triska/clpz**