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

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:

link(g,h).link(g,d).link(e,d).link(h,f).link(e,f).link(a,e).link(a,b).link(b,f).link(b,c).link(f,c).

go(X,X,[X]).

go(X,Y,[X|T]):-

link(X,Z),

go(Z,Y,T).

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]  ;

no

rather than

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

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

X = [a,b,c]  ;

no

Extra Credit (10% bonus):

Implement a generic best-first search algorithm.

Reference:

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 +10% before Monday, 09/21, 11:59PM no modification (on time) before Tuesday, 09/22, 11:59PM -10% from Wednesday, 09/23, 0:00AM to  Thursday, 09/24, 11:59PM -25% 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 userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via RPILMS.