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 = 30If at this point the user types a semicolon, the interpreter should respond with
P = [a, b, d] N = 20One more semicolon should produce
noThere are no more paths.
a
to b
, you can also walk 10 meters from
b
to a
.
a
to
b
and back to a
again.
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.
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!
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).
is
predicate to force arithmetic
computation.
Be sure to follow the applicable parts of the General Guidelines for All Assignments.
As in previous assignments, you will submit your work using the
turnin
script. Make sure to include your test cases/mazes.
Last Change: 29 November 2006 /