Find Captain Frederick Selous in Zanzibar. Ask him 'map', then ask him 'mines'.
He will ask you to collect the horn of a rhino, this can be found on the black rhino in Zanzibar.
Alternatively, he will be more than happy to help you if you are a Knight of the Royal Explorer variety.
Once you give him the horn, ask him 'mines' again.
He will ask you to get a map. Go 3WN, Kneel in front of the statue.
You will fall, follow the path to its end, sit in the pentagram and ask the Imp 'map', then ask him 'challenge'.
He will tell you to go get him a random item. Once you've found the item, return to the imp and give it to him (sit pentagram again).
Go give the map to Frederick.