Neljavärviprobleem

"Tõesta, et iga tasapinnalist kaarti on võimalik värvida vaid nelja värvi kasutades nii, et ühise piiriga maad on kõikjal eri värvi"

Selle aastal 1857 esitatud matemaatikaprobleemi kallal juurdlesid paljud matemaatikud sajandite vältel (näiteks ka professor Jaakson Tartu ülikoolis), kuni lõpuks aastal 1987 esitati tõestus, mis põhines väga suure arvu variantide läbivaatamisele arvutis (esimese tõestuse saamiseks töötas arvuti 1200 tundi); "inimlikku" s.t. sellist, mida inimene ilma arvutita suudaks kontrollida, ei ole seni veel leitud.

Teoreemi tõestav programm on läbivaadatave versioonide suure hulga ja üsna keeruka kirjelduse tõttu üsna keeruline, kuid programm, mis värvib etteantud kaardi nii, et naabermaad on alati eri värvi, on lihtne. Sõna "piir" all mõeldakse sageli vaid maismaapiiri; kuna kaardil ka meri peaks olema kuidagi värvitud, siis võib merd käsitleda ühena maadest.

Ka selle ülesande jaoks on programm seda lihtsam, mida otstarbekam on algandmete esitusviis. Programmi jaoks on oluline vaid see, millistel maadel on ühine piir ja millseid värve võib kasutada; siin on esitatud rohkem kui neli värvi, kuid Prolog leiab alati lahenduse, kus kasutatakse vaid nelja värvi.

naabrid(soome,rootsi).
naabrid(soome,norra).
naabrid(rootsi,norra).
naabrid(soome,venemaa).
naabrid(taani,saksa).
naabrid(saksa,poola).
naabrid(poola,valgevene).

naabrid(poola,venemaa).

naabrid(poola,leedu).

naabrid(leedu,läti).

naabrid(leedu,venemaa).

naabrid(leedu,valgevene).

naabrid(läti,eesti).

naabrid(läti,venemaa).

naabrid(eesti,venemaa).
naabrid(venemaa,valgevene).

naabrid(norra,meri).

naabrid(rootsi,meri).

naabrid(taani,meri).

naabrid(venemaa,meri).

naabrid(taani,meri).

naabrid(saksa,meri).

naabrid(leedu,meri).

naabrid(läti,meri).

naabrid(eesti,meri).

värv(roheline).
värv(hall).
värv(sinine).
värv(pruun).
värv(kollane).

Need faktid võib modulaaruses saavutamiseks salvestada eraldi failides (näit "naabermaad.pl", "värvid.pl", salvestada ja laadida enne päringu tegemist käsuga consult (võib kasutada ka süntaksit ['naabermaad.pl'],['värvid.pl'])). Predikaat värvi otsib maa Maa, mis pole veel värvitud, otsib värvi Värv, millega seda maad võib värvida (s.t. sellise värvi, millega ei ole värvitud ükski ükski naabermaa) ja salvestab siis värvimise lausega värvitud(Maa,Värv); kui kõik maad on värvitud, siis esitab tulemuse:

Maad esinevad naabrite loetelus kusagil kas esimese või teise argumendina; erandiks on Inglismaa, millel pole ühist piiri teiste selle kaardi maadega:

Predikaat näita esitab iga maa värvi ja samas eemaldab vastava lause Prologi mälust; kui rohkem lauseid värvitud enam pole, lõpetab predikaadi näita teine lause töö. Predikaat loe_värvid kogub süsteemipredikaadi findall abil kõik kasutatud värvid nimistuks Värvid, mille süsteemipredikaat sortjärjestab, eemaldades ühtlasi ka duplikaadid, nii et süsteemipredikaadi length poolt saadakse erinevate kasutatud värvide arv: