# Assignment 9: Prolog

Due: 5:00pm, Friday, November 9. [Students scheduled to present November 12 or earlier, and any teammates of these students, have an assignment deadline of 5pm, November 19.] Value: 30 pts.

Create and submit a text file containing Prolog definitions of the predicates requested below.

## Part A: `unite`

Write a `unite` predicate where `unite(A, B, U)` applies for some U that holds every element found in A or B but without any duplicates. (It may assume that A and B do not contain duplicates.)

Below is a sample test illustrating a correct solution; but a correct solution might well find a different ordering instead, and it might find additional reorderings of the list.

```?- unite([a,c,e], [b,d,c], X).

X = [a, b, c, d, e] ;

No
```

To do this, you'll likely find the built-in `member` predicate useful; `member(X, L)` applies whenever X can be found in the list L. You'll also likely find the NOT operator “`\+`” useful. Both are illustrated by the below definition of `all_unique` which applies to any list containing no duplicates.

`all_unique([]).all_unique([H | T]) :- \+ member(H, T), all_unique(T).`

## Part B: `connect` Say we have an `adj` predicate that applies when two locations in a maze are adjacent. The below example shows how to define `adj` for the maze illustrated at right.

`edge(q00, q01). edge(q01, q11). edge(q10, q11). edge(q00, q10). edge(q10, q20).edge(q02, q12).edge(q21, q22).adj(X, Y) :- edge(X, Y).adj(X, Y) :- edge(Y, X).`

Define a `connect` predicate where `connect(S, T, V)` applies whenever there is a route from S to T. The final V is present simply to be a list tracking locations visited earlier in the recursion; this will help you to avoid infinite recursion.

```?- connect(q01, q20, []).

true? ;

yes

?- connect(q01, q02, V).

no
```

The gprolog command is freely available; it is already installed in the Linux lab. Once installed, you can start the interactive interpreter with the “gprolog” command.

You will want to compose some predicates of your own in a text file. Suppose, for example, that you have stored your solutions in a file named “soln.pl”. To load these predicates into the interpreter, you will first want to ensure you're in the same directory as the file, start gprolog, and then enter the filename enclosed in single quotes and brackets.

```linux% cat soln.pl
edge(q00, q01). edge(q01, q11). edge(q10, q11). edge(q00, q10). edge(q10, q20).
edge(q02, q12).
edge(q21, q22).
linux% gprolog
GNU Prolog 1.3.0
By Daniel Diaz
| ?- ['soln.pl'].
```

If you later decide to edit the file, you do not need to exit gprolog but rather just re-execute the command to load the file.

After gprolog loads the file, you can then enter queries at the interactive prompt. For example, if the file contained the above definition of `adj` defining the maze, we could enter a query to ask what locations are adjacent to `q00`.

```| ?- adj(q00, X).

X = q01 ? ;

X = q10 ? ;

no
```

The interpreter first responds with `q01` as a solution; after you type “;” to suggest that it continue searching for solution, it responds with `q10` as an alternative solution. A request to find more solutions leads to the response of “no”.