Introduction :

For this assignment, you're being asked to write five Prolog files according to the given specifications. This will give you the opportunity to practice logical programming. As a standard for this course, we will use an environment called SWI-Prolog, SWI-Prolog can be downloaded free for your use at http://www.swi-prolog.org. The latest version, as of this writing, is 7.6.4.

Part I: Prolog predicate definition (70 points)

Question Required definitions Sample usage (1) (20 points) median(List,Median) Note that List will always be a list with an odd number of distinct integers.

?- median([7,4,2,8,1,3,6],M). M = 4

?- median([1,2,3],2). true

?- median([1,2,3],1). false

(2) (20 points) subsets(S,PS) Note that the subsets need not be listed exactly in the order shown.

?- subsets([1],[[1],[]]). true

?- subsets([1],[[1],[2]]). false

?- subsets([1,2],PS). PS = [[],[1],[2],[1,2]]

(3) (25 points) mergesort(US,S)

?- mergesort([3,4,5,1,2,6],[1,2,3,4,5,6]). true

?- mergesort([3,4,5,1,2,6],[1,2,3,4,5]). false

?- mergesort([3,4,5,1,2,6],T). T = [1, 2, 3, 4, 5, 6] (4)

(5 points) quicksort(US,S)

?- quicksort([3,4,5,1,2,6],[1,2,3,4,5,6]). true

?- quicksort([3,4,5,1,2,6],[1,2,3,4,5]). false

?- quicksort([3,4,5,1,2,6],T). T = [1, 2, 3, 4, 5, 6]

Part II: Path finding in a maze (30 points) Write Prolog rules to find paths through a maze in a file called p2.pl. The maze has various destinations, and directed edges between them. Each edge has a cost. Here is a representation of the available edges:

edge(b, a, 5).

edge(a, u, 10).

edge(u, o, 140).

edge(u, r, 130).

edge(r, o, 20).

edge(r, v, 50).

edge(o, v, 45).

edge(b, v, 20).

The first fact means, for example, that there is an edge from b to a, which costs $5. These edges only go one way (to make this a directed acyclic graph). You can't get back from a to b. You can use these facts directly as part of your program. You should then write rules that define the path relation:

path(Start, Finish, Stops, Cost) :- ....

This succeeds if there is a sequences of edges from Start to Finish, through the points in the list Stops (including the start and the finish), with a total cost of Cost. For example, the goal path(b, u, S, C) should succeed, with S=[b, a, u], C=15.

The goal path(r, u, S, C) should fail, since there isn't any path from r back to u in this maze. The goal path(b, v, S, C) should succeed in four different ways, with costs of 20, 200, 195, and 210 and corresponding lists of stops. (It doesn't matter what order you generate these in.)

You should include 3 types of tests, which show different ways of testing one of the goals (for example path from b to v):

(1) nondeterministic test of one path;

(2) test for all of the specified costs for 4 possible paths;

(3) an exhaustive test of all 4 paths. (You need to include more tests with other paths.)

/* First a nondeterministic test of one path: */

path(b, v, [b, a, u, o, v], 200).

/* Second a test for all of the costs for the all(4) possible paths (ignoring the route): */

path(b, v, _, C).

/* Finally an exhaustive test of all(4) paths, including both route and costs. */

path(b, v, S, C).

Hints: try solving this in a series of steps. First, solve a simplified version, in which you omit the list of stops and the cost from the goal. Then modify your solution to include the cost. Then after that's working, add the stops. Note that there are no edges from a stop to itself, i.e. there is no implicit rule edge(b, b, 0).

When you add the code to find the stops, you might find your solution almost works, except that your path comes out in reverse order. There are various ways to solve this (including reversing the list). The more elegant approach, however, is to construct the list from the end. (Doing this will likely only require minor changes to your code.) For example, suppose that you are searching for a path from b to r. Your rule might find an edge from b to a, and a recursive call to your rule might find a path from a to r. Then the path from b to r can be formed by taking the path from a to r (namely [a,u,r]) and putting the new node on the front of this list to yield the path from b (namely [b,a,u,r]).