The princess (or prince if you're female) has been captured by the Evil Dragon and held prisoner in a tower. The tower is also surrounded by a maze to keep out the riff-raff. You are a knight out to rescue the princess (prince), and as the dragon has gone shopping for some BBQ spare ribs and a set of ear plugs, now is your chance. You must search the maze for the princess as quickly as possible before the dragon comes back. As the princess likes Heavy Metal Music, which she plays quite loudly, you can hear her from some distance away which may help your quest.

You need to produce a predicate representation of the maze (above). The noise_levels at various places within the maze have been defined as predicates at the end of this sheet.

You will also need to display the route taken through the maze, ensure it includes both the start and end state (the place names).

1) Describe, in detail, a suitable fast search technique for this problem describing any issues (e.g. local maxima, plateaus etc) associated with this technique and how you might overcome them.

2) Program your search technique in Prolog and test it. Do not forget that you can debug and test the constituent prolog rules separately.

Comment your code extensively and ensure you use indicative naming for rule and variable names. If you use any books or websites for help, ensure you include a list of references.

3) Add additional rules (do not amend those for part 2) to produce the actual shortest route (in terms of places visited. You will not need to consider the noise_levels to do this.

There are lots of useful hints in the lab notes and in Prolog books like Bratko (many copies in the library).