CSCI.4430/6969 Programming Languages fall 2005
Programming Assignment #4

This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TAs or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also answer/see the answers.



The goal of this assignment is to implement a generic predicate call_bfs  that attempts to satisfy goals breadth-first-search rather than using Prolog's depth-first search strategy. Use your generic predicate to find solutions to at least one of the following problems Missionaries and Cannibals and The Knight's Tour.


Here is a simple example demonstrating how call_bfs(G) is different from call(G):

If we have a graph and paths as defined by the code below:







And suppose your goal is to find all the paths from a to c, denoted by go(a,c,X), call_bfs(go(a,c,X)) will get the following results:

            X = [a,b,c]  ;

      X = [a,e,f,c]  ;

      X = [a,b,f,c]  ;


rather than

            X = [a,e,f,c]  ;

      X = [a,b,f,c]  ;

      X = [a,b,c]  ;



Hint: You will want to keep a queue of yet-to-be pursued sub-goals, each of which is represented by a stack that captures backtracking alternatives. You may want to use Prolog’s reflective capabilities, such as the clause predicate.

Extra Credit (10% bonus if working individually, required for full credit if working in a pair).

Implement a generic best-first search algorithm.


Prolog Tutorial 1

Prolog Tutorial 2  Be sure to read 3.3 Meta-interpreters in Prolog

Due Date:  

Received Time

Grade Modification

before Monday, 11/28, 11:59PM


before Tuesday, 11/29, 11:59PM

no modification (on time)

before Wednesday, 11/30, 11:59PM


from Thursday, 11/31, 12:00AM to 
Friday, 04/22, 11:59PM


after Saturday, 12/1, 12:00AM

not accepted

Grading: The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!).  See the professor or TAs, if you have ideas for other extensions for this assignment and would like extra credit for implementing them.

Submission Requirements: Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two). Your README file should also have a list of specific features / bugs in your solution. Your ZIP file should be named with your WebCT user name(s) as the filename, either or Only submit one assignment per pair via WebCT.