Preface

There is a dark world in which a stinking monster lives. The so-called wumpus. This wumpus is very angry because he was locked up in this world by the AI-researchers. To make matters even worse, the world is filled with bottomless pits. Making life very unpleasant.

However, our wumpus has something the AI-researchers really want, a lot glittering gold. That’s why they send a robot into the world to find the gold and bring it back. The robot has two sensors: an anemometer and a sniffer. This should be sufficient to find the gold. In case the robot would encounter the whumpus he is also equipped with an arrow to shoot.

Exercise

Given a NxN field with at least 1 bottomless pit (pit) and 1 wumpus.

Each square on the field is has a coordinate, the first digit indicates the row and the second digit indicates the column. The robot starts at square (0,0) in the upper left corner.

The intention is to find gold (a square with the property glitter). We cannot examine the squares with a bottomless pit or the whnpus, as doing so would result in losing the robot. On the squares adjacent to (not diagonally) a bottomless pit is a breeze (breeze) is measurable. On the squares next to the whumpus there is a stench (stench).

For a valid coordinate (X, Y) you can do a infer grid:shoot((X, Y)) this will ensure that if the wumpus is on (X, Y) he will be neutralized. This can only be done once. And must therefore be postponed as long as possible.

For a valid coordinate (X, Y) you can use a infer grid:query((X, Y), Measurement) in which Measurement is unified with a list of measurements. This list can contain the following terms

• stench((X, Y)): it stinks at position (X, Y)
• no_stench((X, Y)): it does not stink at position (X, Y)
• breeze((X, Y)): there is a breeze at position (X, Y)
• no_breeze((X, Y)): it is no breeze on (X, Y)
• glitter((X, Y)): there is gold on (X, Y)
• no_glitter((X, Y)): there is no gold on (X, Y)
• wumpus((X, Y)): the wumpus is located at (X, Y) , if you did not shoot here first trying to infer grid:query/2 will fail.

If you run grid:query/2 on a pit or the unprotected wunpus it will fail and you will not be able to do further queries.

Write a predicate search(N, Site) indicating that the gold is located on Site, in an N by N grid. In your search you can start from the information [no_breeze ((0,0)), no_stench ((0,0)), no_glitter ((0,0))], so you already know that box (0,0) is safe and that there is no breeze, smell or glitter.

Method

First visit all fields of which you are sure that they are safe. A field that has at least 1 neighboring field that does not contain a breeze is certainly not a hole. Analog you know that if there is no stench, there is no wumpus on the box next to it.

Postpone shooting as long as possible. Shoot only if there is no certainly-safe square. In this case, shoot at the on the coordinate that is lexicographically the first that is certainly not a ‘pit’ but could be a wumpus.

If the gold is unreachable or there are no more safe moves, your predicate may fail.

Module to test

To test your code you can use grid.pl¹, a module that you can import with :- use_module (" grid.pl ").. This module gives you grid:query and grid:shoot that are extended with debug information.

? - search (4, City).

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]
Place = (0, 3).