Hunt, kits ja kapsad

Selles vanas nuputamisülesandes peab farmer viima üle jõe hundi, kitse ja kapsad nii, et kõik säiliks tervetena. Farmeril on kasutada paat, kuhu peale tema mahuvad mitte rohkem kui kaks üleviidavat, kuid kui samale kaldale jäävad hunt ja kits või kits ja kapsad, tuleb kohe pahandus. Kui andmed on kodeeritud sobiva andmestruktuuri abil, on ülesannet Prologi abil lihtne lahendada. Kogu ülevedamist võib vaadelda kui vahelduvate seisude jada (selliselt kodeerituna on ylesarne sarnane näiteks kaardil tee otsimise ylesandega). Seis on neljaelemendiline nimistu, mille esimene element näitab, kummal kaldal (ida või läänekaldal) on farmer, teine - kummal kaldal on hunt, kolmas - kummal on kits ja neljas - kapsad, seega ülevedu algab seisust seis(ida,ida,ida,ida) ja lõpeb seisus seis(lääne,lääne,lääne,lääne).
Ülesande lahendab predikaat mine; et saada kõiki lahendedi, sunnitakse Prolog mine esimese lause lõpus predikaadiga fail järgmist lahendit otsima; kui uusi lahendeid rohkem enam ei ole, lõpetab teine lause mine(_,_) predikaadi töö; selline "sunnitud" kõigi lahendite otsimine on vajalik siis, kui predikaatides on kasutatud lõiget !, mis võib Prologi sisseehitatud tagurdamise (backtracking) katkestada.

alusta :-
mine(seis(ida,ida,ida,ida), seis(lääne,lääne,lääne,lääne)).

mine(Seis, Eesmärk) :-
seisujada(Seis, Eesmärk, [Seis], Nimistu),
nl,
write('Lahendus on:'),
nl,
näita_lahendus(Nimistu),
fail.

mine(_,_).

Lõpprekursiivse predikaadi seisujada esimene ja teine atribuut näitavad üleviimise alg- ja lõppseisu; kolmandaks attribuudiks on seni esinenud seisude jada (selle abil kontrollitakse, et seisud ei hakkaks korduma) ja neljas on vajalik vaid selle seisude jada edasiandmiseks eesmärgi saavutamisel: kui esimene ja teine argument on samad, s.t. eesmärk on saavutatud, saab neljas argument võrdseks kolmandaga (enne seda on ta muutuja). Predikaat member(Element, Nimistu) kontrollib, kas Element esineb nimistus Nimistu.

seisujada(Eesmärk, Eesmärk, Nimistu, Nimistu) :-
!.

seisujada(Seis, Eesmärk, Nimistu, L1) :-
ylesoit(Seis, Seis1),
not(hädaohtlik(Seis1)),
not(member(Seis1, Nimistu)),
seisujada(Seis1, Eesmärk, [Seis1|Nimistu], L1).

Ülesõidu ajal viib farmer ühe (hundi, kitse või kapsad) teisele kaldale; ülejäänud kaks objekti jäävad sinna kus nad olid:

ylesoit(seis(Rand1, Rand1, Kits, Kapsad), seis(Rand2, Rand2, Kits, Kapsad)) :-
vastaspoolne(Rand1, Rand2).

ylesoit(seis(Rand1, Hunt, Rand1, Kapsad), seis(Rand2, Hunt, Rand2, Kapsad)) :-
vastaspoolne(Rand1, Rand2).

ylesoit(seis(Rand1, Hunt, Kits, Rand1), seis(Rand2, Hunt, Kits, Rand2)) :-
vastaspoolne(Rand1, Rand2).

ylesoit(seis(Rand1, Hunt, Kits, Kapsad), seis(Rand2, Hunt, Kits, Kapsad)) :-
vastaspoolne(Rand1, Rand2).

vastaspoolne(ida, lääne).
vastaspoolne(lääne, ida).

Hädaohtlikud on seisud, kus samal rannal on hunt ja kits või kits ja kapsad, ja farmer on samal ajal jõe vastasrannal:

hädaohtlik(seis(Farmer, Rand1, Rand1,_)) :-
vastaspoolne(Farmer, Rand1).

hädaohtlik(seis(Farmer, _, Rand1, Rand1)) :-
vastaspoolne(Farmer, Rand1).

Predikaat näita_lahendus esitab predikaadi näita_ylesoit abil iga kahe järjestikuse seisu vahel esinenud ülesõidud:

näita_lahendus([T1,T2|T]) :-
!,
näita_ylesoit(T2,T1),
näita_lahendus([T2|T]).

näita_lahendus(_).

näita_ylesoit(seis(Rand1, Hunt, Kits, Kapsad), seis(Rand2, Hunt, Kits, Kapsad)) :-
!,
write('Farmer siirdub jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.

näita_ylesoit(seis(Rand1, Rand1, Kits, Kapsad),seis(Rand2, Rand2, Kits, Kapsad)):-
!,
write('Farmer saadab hundi jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.

näita_ylesoit(seis(Rand1, Hunt, Rand1, Kapsad), seis(Rand2, Hunt, Rand2, Kapsad)) :-
!,
write('Farmer viib kitse jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.

näita_ylesoit(seis(Rand1, Hunt, Kits, Rand1),seis(Rand2, Hunt, Kits, Rand2)) :-
!,
write('Farmer viib kapsad jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.

Abipredikaati member(Element, Nimistu) kasutatakse nii kontrolliks, kas element Element esineb nimistus Nimistu (kui selle poole pöördumisel on mõlematel muutujatel Element, Nimistu väärtus) kui ka antud nimistu elementide leidmiseks (s.t. pöördumisel on muutujal Nimistu väärtus, kuid muutujal Element ei ole väärtust - väärtus saadakse nimistu Nimistu elemendiga samastamisel).

Ülesandeid:

Hundi, kitse ja kapsaste üle jõe viimise ülesandega on sarnane ülesanne misjonäride ja kannibalide üle jõe viimisest:
Kolm misjonäri ja kolm kannibali peavad kõik pääsema üle jõe. Nende kasutada on paat, kuhu ei mahu rohkem kui kaks isikut; paadimeest ei ole, seega keegi neist endist peab alati paadi teisele kaldale toimetama, kuid kunagi ei või kaldale maha jääda rohkem kannibale kui seal on misjonäre.
Koosta programm probleemi lahendamiseks.

2. Järjestikuse seisude jadas lahenduseni viiva tee otsimisele taanduvad paljud klassikalised nuputamisülesanded.
Kolm mereröövlit said saagiks 24-liitrise nõu, mis on ääreni täis rummi ja tahavad selle omavahel võrdselt ära jagada. Neil on kolm nõu, mis mahutavad vastavalt 5, 11 ja 13 liitrit. Tee predikaat, mis leiab vajalikud kallamised.

3. Eelmise ülesande üldisem versioon: nõude (kokku 4) mahud antakse lahendama asumise algul; lahendama asudes on suurim nõu täis, lõppseisus peaks kolmes olema võrdne hulk vedelikku (loomulikult peavad nõude mahud olema antud nii, et neist vähemalt kolme mahtuvus on suurem kui kolmandik kõige suurema mahtuvusest). Vihje: iga nõu võiks (näiteks) kujutada kaheelemendilise nimistuna, esimene näitab, kui palju vedelikku on selles praegu ja teine - kui palju sinna üldse mahub, s.t. lahendamine algaks seisust [[0,5],[0,11],[0,13],[24,24]].

Küsimused, probleemid: