Vaje 12: Programiranje z omejitvami

Uvod

Da lahko programiramo z omejitvami, moramo v prolog naložiti ustrezno knjižnico. Na začetek našega programa zapišemo direktivo

:- use_module(library(clpfd)).

za delo s končnimi domenami (celimi števili) oziroma

:- use_module(library(clpr)).

za delo z realnimi števili.

Na vajah bomo uporabljali omejitve na celih številih. Knjižnica CLP(FD) podpira aritmetične operacije in operatorje za primerjavo:

+   -   *   ^   min   max   mod   rem   abs   //   div
#=   #\=   #>=   #=<   #>   #<

Domeno za posamezno spremenljivko določimo tako:

A in 0..42
B in inf..sup

ali za seznam spremenljivk hkrati:

[A,B,C] ins 1..10

Omejitev all_distinct([A,B,C]) zagotovi, da imajo spremenljivke A, B in C različne vrednosti. S predikatom label([A,B,C]) pa naročimo prologu, da s preiskovanjem našteje konkretne vrednosti spremenljivk, ki ustrezajo vsem podanim omejitvam. Preden uporabimo label, morajo biti domene vseh spremenljivk omejene.

Naloga

Na rednem tedenskem srečanju se je zbralo X klekljaric. Nekatere so s sabo pripeljale tudi svoje mačke; teh je bilo skupaj Y. Vemo, da je na srečanju bilo 22 glav in 72 nog. Napiši predikat meeting(X, Y), ki postavi ustrezne omejitve in vrne število klekljaric in mačk, ki so bile na srečanju.

Jedilnik

SloRest želi optimizirati ponudbo hrane v menzi na FRI. Pri tem mora upoštevati več dejavnikov: obroki morajo biti uravnoteženi po hranilni vrednosti (tj. vsebnosti kalorij, beljakovin in ogljikovih hidratov), hkrati pa dovolj poceni, da restavracija obrne profit. Podatki o posameznih jedeh so podani z naslednjimi predikati:

% tip jedi
predjed(goveja_juha).
glavna_jed(polnjene_bucke).
priloga(polenta).
sladica(tortica).
sadje(jabolko).

% cena (v centih) in hranilne vrednosti posamezne jedi
cena(polenta, 81).
kalorije(polenta, 275).
beljakovine(polenta, 26).
ogljikovi_hidrati(polenta, 41).

% vegetarijanske jedi
vege(polenta).

Datoteko s podatki najdete na učilnici.

Kosilo

Kosilo je sestavljeno iz 1) glavne jedi in priloge ter 2) dveh dodatkov, ki jih izberemo izmed predjedi, sadja in sladice. Napišite predikat kosilo(Seznam), ki vrača različne kombinacije štirih jedi, ki sestavljajo kosilo. Primer:

?- kosilo(K).
K = [polnjene_bucke, polenta, paradiznikova_juha, mafin] ;
…

Vegetarijansko kosilo

Napišite predikat vege_kosilo(K), ki preveri, ali kosilo K vsebuje samo vegetarijanske jedi. Primer:

?- vege_kosilo([polnjene_bucke, polenta, paradiznikova_juha, mafin]).
true.

Namig: pomagate si lahko s predikatom maplist/2.

Ustrezno kosilo

Napišite predikat ustrezno_kosilo(Kosilo, MaxCena, MinKalorij, MaxKalorij, MinBeljakovin, MinOH), ki preveri, ali kosilo K ustreza naslednjim pogojem:

• cenejše od MaxCena,
• vsaj MinKalorij in največ MaxKalorij,
• vsaj MinBeljakovin ter
• vsaj MinOH ogljikovih hidratov.

Namig: pomagate si lahko s predikatom maplist/3. Primer:

?- maplist(length, [[1,2,3], [2,3], [2,2,2,2], [2]], Lengths).
Lengths = [3, 2, 4, 1].

Namig: pomagate si lahko s predikatom sum/3. Primer:

?- sum([1, 2, 3], #>=, 6).
true.

Z ustrezno poizvedbo poiščite različna kosila, ki stanejo največ 5.00 € in vsebujejo vsaj 900 kalorij ter vsaj 50 g beljakovin. Poizvedbo razširite tako, da bo vračala samo vegetarijanska kosila.

Problem n dam

Napisali bomo program, ki na šahovsko ploščo velikosti n×n razporedi n dam tako, da se med sabo ne napadajo (torej noben par dam ni na isti horizontali, vertikali ali diagonali). Koordinate posamezne figure bomo zapisali v obliki X/Y.

safe_pair(X1/Y1, X2/Y2)

Napišite predikat safe_pair(X1/Y1, X2/Y2), ki z ustreznimi omejitvami zagotovi, da se dami na poljih X1/Y1 in X2/Y2 med sabo ne napadata. Primer:

?- safe_pair(1/1, 2/2).
false.
?- safe_pair(4/2, 5/3).
false.
?- safe_pair(3/3, 4/2).
false.
?- safe_pair(1/1, 2/3).
true.

safe_list/2

Napišite predikat safe_list(X/Y, L), ki sprejme koordinate ene dame in seznam koordinat preostalih dam ter preveri, da dama na koordinatah X/Y ne napada nobene v seznamu. Primer:

?- safe_list(1/1, [3/4, 3/8, 2/3, 3/5]).
true.

safe_list/1

Napišite predikat safe_list(L), ki sprejme seznam koordinat in preveri, da se med sabo ne napada noben par dam v seznamu. Primer:

?- safe_list([3/3, 2/5, 1/7, 8/6, 5/4, 7/8]).
true.

place_queens/3

Napišite predikat place_queens(N, I, L), ki na šahovnico velikosti N×N razporedi N dam tako, da je vsaka v svojem stolpcu (ima svojo koordinato X). Predikat naj vrne koordinate v seznamu L. I je pomožen parameter, ki hrani trenutno vrednost koordinate X. Primer:

?- place_queens(2, 0, L), term_variables(L, Vars), label(Vars).
L = [1/1, 2/1],
X = [1, 1] ;
L = [1/1, 2/2],
X = [1, 2] ;
L = [1/2, 2/1],
X = [2, 1] ;
L = [1/2, 2/2],
X = [2, 2] ;
false.

Predikat term_variables(L, Vars) poišče vse spremenljivke v izrazu (seznamu) L in jih shrani v seznam Vars, na katerem lahko potem pokličemo label/1. Predikat place_queens/2 poskusite napisati tako, da se ustavi, ko vrne vse rešitve.

queens/2

Napišite predikat queens(N, L), ki na šahovnico velikosti N×N razporedi N dam tako, da se med sabo ne napadajo. Njihove koordinate naj vrne v seznamu L. Kakšen je najmanjši N>1, za katerega obstaja vsaj ena rešitev?