CSCI.4430/6969 Programming Languages Fall 2009
Programming Assignment #

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 help from the TAs or the instructor. You are encouraged to use the RPILMS 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 using 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):

Implement a generic best-first search algorithm.


Prolog Tutorial 1

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


Note: We will use SWI-Prolog in this assignment. If you have problems compiling sample code from online tutorials, please pay attention to syntactic differences among Prolog implementations, such as using "=<" instead of "<=".

Due Date:  

Received Time

Grade Modification

before Saturday, 09/19, 11:59PM


before Monday, 09/21, 11:59PM

no modification (on time)

before Tuesday, 09/22, 11:59PM


from Wednesday, 09/23, 0:00AM to 
Thursday, 09/24, 11:59PM


after Friday, 09/25, 0: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 RPILMS user name(s) as the filename, either or Only submit one assignment per pair via RPILMS.