Inleiding

Er is een duistere wereld waarin een stinkend monster leeft. De zogenaamde wumpus. Deze wumpus is heel boos omdat hij door de AI onderzoekers is opgesloten werd in deze wereld die dan ook nog eens vol bodemloze putten zit. Bovendien is zijn naam wumpus wat hem ook niet zo gelukkig stemt, hij zou namelijk graag annita heten.

Onze wumpus heeft echter iets wat de AI onderzoekers heel graag willen, een hoop glinsterend goud. Daarom sturen ze een robot de wereld in om het goud te vinden. Deze robot heeft twee sensoren: een anemometer en een snuffelaar. Hiermee moet hij het goud zien te vinden. Voor het geval de robot de whumpus tegen zou komen is hij ook uitgerust met een pijl om mee te schieten.

Opgave

Gegeven een veld van N bij N vakjes met daarop minstens één bodemloze put (pit) en juist één wumpus.

Op het veld krijgt elk vakje een coördinaat waarbij het eerste cijfer de rij aangeeft en het tweede cijfer de kolom. Je begint op vakje (0,0) in de linkerbovenhoek.

Het is de bedoeling goud (een vakje met de eigenschap glitter) te vinden. Hierbij mag je geen vakje met een bodemloze put of de wumpus onderzoeken. Op de vakjes naast (niet diagonaal) een bodemloze put is een briesje (breeze). Op de vakjes naast de whumpus hangt er een stank (stench).

Voor een geldig ground coördinaat (X,Y) kun je een de oproep grid:shoot((X,Y)) gebruiken, dat zal er voor zorgen dat als de wumpus zich op (X,Y) bevindt hij geneutraliseerd wordt. Je kunt grid:shoot/1 maar 1 keer oproepen. Stel dit dus zo lang mogelijk uit.

Voor een geldig ground coördinaat (X,Y) kun je een de oproep grid:query((X,Y), Meting) doen waarbij Meting wordt geünificeerd met een lijst van metingen. Deze lijst kan volgende termen bevatten

• stench((X,Y)): het stinkt op positie (X,Y), de Wumpus is een aanliggend (niet diagonaal) vak
• no_stench((X,Y)): het stinkt niet op positie (X,Y)
• breeze((X,Y)): er is een briesje op positie (X,Y), er is een put in een aanliggend (niet diagonaal) vak
• no_breeze((X,Y)): het is windstil op (X,Y)
• glitter((X,Y)): er is goud op (X,Y)
• no_glitter((X,Y)): er is geen goud op (X,Y)
• wumpus((X,Y)): de wumpus bevind zich op (X,Y), als je hier niet eerst hebt geschoten faalt de grid:query/2.

Als je grid:query/2 uitvoert op een pit of de ongeschoten wunpus zal het falen en kun je geen verdere queries meer doen.

Schrijf een predicaat search(N, Plaats) dat aangeeft dat het goud zich bevind op Plaats in een N bij N bord. In je zoektocht mag je beginnen van de informatie [no_breeze((0,0)),no_stench((0,0)), no_glitter((0,0))], dus je weet al dat vakje (0,0) veilig is en dat er geen briesje, stank of glitter is.

Werkwijze

Bezoek eerst alle velden waarvan je zeker bent dat ze veilig zijn. Een veld die op zijn minst 1 naburig veld heeft dat geen briesje bevat is zeker geen gat. Analoog weet je dat als er geen stank is, er geen wumpus op het vak ernaast is.

Stel het schieten zo lang mogelijk uit. Schiet enkel als er geen enkel vak is waarvan je zeker bent dat het veilig is (geen whumpus en geen pit). Schieten doe je in dit geval op het vak dat lexicografisch het eerste is dat zeker geen pit is maar wel een wumpus zou kunnen zijn.

Vind je het goud niet, of kun je geen zeker veilige zetten meer doen? Dan mag het predicaat falen.

Module om te testen

Om je code te testen kun je gebruik maken van grid.pl¹, een module die je kunt importeren met :- use_module("grid.pl").. Deze module geeft je een grid:query en grid:shoot die uitgebreid zijn met debug informatie.

?- search(4, Plaats).

Investigating 0,1,
found: []

Investigating 0,0,
found: []

Investigating 0,2,
found: [stench]

Investigating 1,0,
found: []

Investigating 1,1,
found: [stench]

Investigating 2,0,
found: []

Investigating 2,1,
found: [breeze]

Investigating 3,0,
found: []

Investigating 3,1,
found: []

Investigating 3,2,
found: [breeze]

Pang! You shot at 0,3

Investigating 0,3,
found: [glitter]
Plaats =  (0, 3).