CSC 411: Artificial Intelligence

 (Fall 2006)

 

Programming Project 1: Prolog Basics

Due by October 12, Thursday, 2006

 

 Write Prolog programs for each of following problems. For each of your programs

a.       Execute your code and draw a graph of the search space.

b.      Alter the rule ordering to produce alternative solution paths.

  1. A Prolog code to answer Wirth’s “I am my own grandfather” problem:

I married a widow (let’s call her W) who has a grown-up daughter (call her D). My father (F), who visited us quite often, fell in love with my step-daughter and married her. Hence my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (S1), who became the brother-in-law of my father, as well as my uncle. The wife of my father, that is, my step-daughter, also had a son (S2).

  1. A Prolog code to solve the farmer, wolf, goat, and cabbage problem:

A farmer with his wolf, goat, and cabbage come to the edge of a river they wish to cross. There is a boat at the river’s edge, but, of course, only the farmer can row. The boat also can carry only two things, including the rower, at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrives safely on the other side of the river.

  1. A Prolog code for the missionary and cannibal problem:

Three missionaries and three cannibals come to the bank of a river they wish to cross. Three is a boat that will hold only two, and any of the group is able to row. If there are ever more missionaries than cannibals on any side of the river the cannibals will get converted. Devise a series of moves to get all the people across the river with no conversions.

  1. A Prolog code for the water jugs problem:

There are two jugs, one holding 3 and the other 5 gallons of water. A number of things can be done with the jugs: they can be filled, emptied, and dumped one into the other either until the poured-into jug is full or until the poured-out-of jug is empty. Devise a sequence of actions that will produce 4 gallons of water in the larger jug. (Hint: use only integers.)