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

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). N = a, Es = [b, c, d, f] ; N = b, Es = [c, d, a] ; N = c, Es = [d, e, a, b] ; N = d, Es = [e, f, a, b, c] ; N = e, Es = [f, c, d] ; N = f, Es = [a, d, e].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 = [_8284], T = node(_8296, nil, nil) ; Ls = [_8284, _8290], T = node(_8302, nil, node(_8310, nil, nil)) ; Ls = [_8284, _8290], T = node(_8302, node(_8310, nil, nil), nil) ; Ls = [_8284, _8290, _8296], T = node(_8308, nil, node(_8316, nil, node(_8324, nil, nil))) ; Ls = [_8284, _8290, _8296], T = node(_8308, nil, node(_8316, node(_8324, nil, nil), nil)) .

- solve
**Sudoku**puzzles **timetabling**for schools**sports scheduling****N-queens**puzzle- more examples:
**https://github.com/triska/clpfd**