INF-121 H-2005

Obligatorisk oppgave III.


Du skal levere (per epost til en av gruppeledere) en fil
	navn.pl
der "navn" er ditt etternavn. Filen skal inneholde loesninger til begge
oppgavene klart adskilt fra hverandre. Man skal kunne laste filen til
Prolog-tolken (?- consult(navn).) og eksekvere de definerte predikater for aa
sjekke din loesning.  

Frist for innlevering er: onsdag, 23.11, kl.16:00

Noen spoersmaal om oppgaven vil kunne stilles paa gruppen onsdag, 16.11 eller fredag 18.11.


Oppgave 1.___________________________________________________________________________

Definer et predikat
	queen(N,X)
som holder hvis og bare hvis N er et heltall (helst stoerre enn 0) og X er en
loesning paa N-dronningsproblemet. Nemlig, N angir stoerrelse paa et NxN
brett, der man skal plassere N dronninger slik at ingen slaar hverandre. (En
dronning kan slaa en brikke som staar i samme rad eller samme kolonne eller
paa samme diagonalen (enten / eller \) som dronningen.) 

Det kan vaere lurt (men kreves ikke) aa benytte seg av predikatet skriv(P,N)
fra oppgave 5, uke 44, for aa vise loesninger paa skjermen i noenlunde
oversiktlig format. Merk at da skal en loesning X ha formen som en liste av
par, f.eks., for N=4, listen [1:1,2:2,3:3,4:4] representerer en plassering av
dronningene paa (den ene) diagonalen (altsaa ikke en loesning), mens
[1:3,2:1,3:4,4:2] og [1:2,2:4,3:1,4:3] representerer to eneste loesninger
(som skal altsaa skrives ut etter query queen(4,X).) 
Dersom du avviker fra denne konvensjonen, beskriv kort i kommentarer hvordan
du representerer plasseringer/loesninger.  

[Hint: Loesning paa hele oppgaven (unntatt evt. definisjon av skriv(...))
boer ikke ha mer enn ca. 20 linjer.] 


Oppgave 2.___________________________________________________________________________

Definer et predikat
	col(Kart, Farger, Fargelegging)
som holder hvis og bare hvis Fargelegging er en lovlig fargelegging av
Kart'et med Farger. (Lovlig fargelegging er altsaa en der hvert land paa
kartet faar noeyaktig en farge fra Farger og der ingen naboland har samme
farge.) 

Kart tenkes representert som en liste av naboer, f.eks.,
	[1:2,1:3,2:3]
representerer et kart der hvert av tre landene grenser mot de to
andre. (Rekkefoelgen paa naboer i hvert par eller paa par i hele listen burde
ikke spille noen rolle. Dvs. kartet over kunne ogsaa oppgis som, f.eks.,
listen [2:1,2:3,3:1].) 

Farger er en liste med fargenavn, f.eks., [b,g,r,s]. En query tenkes altsaa som, f.eks.
?-	col( [1:2,1:3,2:3], [a,b], C).
og denne skal gi som resultat No, siden dette kartet kan ikke fargelegges med kun to farger. 
Query:
?-	col( [1:2,1:3,2:3], [a,b,c], C).
skal, f.eks., generere svar
C = [1:c, 2:a, 3:b] ;
C = [1:b, 2:a, 3:c] ;
...

Vi tenker altsaa at Fargelegging er en liste med par land:farge. Hvis du
avviker fra denne konvensjonen, beskriv kort i kommentarer hvordan du
representerer Kart, Farger og Fargelegging. 

Husk at ifoelge et beroemt teorem kan enhver planar graf (altsaa en som
representerer et mulig kart) fargelegges med hoeyst 4 farger, saa ditt
program skal helst finne en slik fargelegging for et vilkaarlig kart, naar
Farger-listen har 4 elementer. Noen kart kan fargelegges med faerre enn 4
farger. F.eks., foelgende angir en mulig relasjon:
        col([1:2,1:3,1:5,3:2,3:4,3:5,4:2,4:5], [a,b,c], [1:a,2:b,3:c,4:a,5:b]).

[NB! Det kan hende at du vil maatte bruke snitt, !, et sted i denne oppgaven.]

[Hint: Loesning paa denne oppgaven boer ikke ha mer enn ca. 15 linjer.]