CSC 173, Fall 2006

Assignment 6: Prolog

You are to write a simple program in Prolog to find a path through a maze. Your input will consist of facts of the form 

    pway(a, b, 10).
indicating that there is a passageway from intersection a to intersection b of length 10 meters. You are to write a rule 
    solve(X, Y, P, N) :- ...
that will find a path P of length N (if one exists) from intersection X to intersection Y. The intent is that the user will invoke solve as a query, specifying X and Y as constants and P and N as variables.

Here is a concrete example. Suppose the database contains the following rules: 

    pway(a, b, 10).
    pway(b, c, 15).
    pway(d, c, 5).
    pway(d, b, 10).
If the user types 
    solve(a, d, P, N)
the Prolog interpreter might respond with 
    P = [a, b, c, d]
    N = 30
If at this point the user types a semicolon, the interpreter should respond with 
    P = [a, b, d]
    N = 20
One more semicolon should produce 
    no
There are no more paths.

Subtleties

  1. Note that passageways are bi-directional; if you can walk 10 meters from from a to b, you can also walk 10 meters from b to a.
  2. Most mazes will have cycles. Your code must cope with them. There's no point in passing through the same intersection more than once, and you certainly don't want the interpreter to fall into an infinite regression doing so.
  3. Note that the bi-directionality of passageways creates a huge number of trivial cycles: you'll want to avoid walking from a to b and back to a again.

Extra Credit

As extra credit, you could output paths in increasing order of length. In the example above, for example, [a, b, d] should show up before [a, b, c, d]. Note: I recommend that you worry about ordering only after implementing and debugging the original version of your program.

Hints

  1. Professor John Fisher at Cal Poly Pomona has put together an excellent tutorial that you might find useful.
  2. You shouldn't need to use any imperative features of Prolog (the cut, fail, or database ordering) for the basic assignment. In fact, you shouldn't even need not, though you'll probably want \= (numeric ``not equal''). A solution for the assignment consisting of only seven rules does exist!
  3. You will want to use the consult and reconsult primitives. Put your program in one file. Put each sample maze in another. Read the program into the interpreter using consult. Read the first maze the same way. If you change your program, read it again using reconsult (this will over-ride the earlier definitions of your rules). If you want to try a different maze, read it using reconsult (this will over-ride all previous pway facts).
  4. You'll want to add distances. Remember that you must use the is predicate to force arithmetic computation.
  5. You can solve the extra credit by generating all possible solutions, sorting them, and then producing them one-by-one on demand. Other approaches may be easier, however. You may need the use of cut and fail for the extra credit part of the assignment.

Be sure to follow the applicable parts of the General Guidelines for All Assignments.

DUE DATE:

Tuesday December 12, 11:59 p.m. There is no trivial ``pre-assignment'' for this project, but you only have a week to write the program proper. Watch your e-mail for possible instructions and additions (homework-style written problems) to the assignment.

What/how to turn in

As in previous assignments, you will submit your work using the turnin script. Make sure to include your test cases/mazes.

Back to the assignments and grading page

Back to the course home page

Last Change: 29 November 2006 /