Escape from Zurg: An Exercise in Logic Programming

Here are two Haskell modules that define a type class for programming search problems in Haskell. The module SearchStrat.hs is an extended version of the module Search.hs offering parameterization of search functions by a search strategy.

• Search.hs
• SearchStrat.hs

The implementation of an example application, a riddle, using either of the above modules can be found in the module Zurg.hs. (The module is ZurgStrat.hs is a variation that uses SearchStrat.hs.)

• Zurg.hs
• ZurgStrat.hs

A Prolog solution to the riddle is contained in the file zurg.pl.

If one is interested in solving only this particular riddle, the search need not be factored in a type class, and knowledge about the particular problem can be exploited to code a solution more directly. For example, since four toys have to cross and only two can go at the same time, it is clear that the pattern of crossings has to be 2 forward, 1 back, 2 forward, 1 back, 2 forward. Moreover, the names of the toys don't really matter, so that one can represent the toys directly by the times they need to cross the bridge. Here is a corresponding direct implementation in Haskell.

• ZurgDirect.hs