Sample Solutions to Assignment n+1

Syntax [5 marks]

Draw the terms corresponding to each of the following:

trans((H:-true), (H))

       trans
        / \
       :-  H
      / \
     H   true

X=(match(X,Y):-call(X), Y>0)

          =
         / \
        X   :-
           /  \
          /    \
       match    ,
        / \    / \
       X   Y call >
	       |   / \
	       X  Y   0

spaces --> [0' ], spaces ; []

         -->
         /   \
      spaces  ;
             / \
            ,   []
           / \
          . spaces
         / \
        32 []

[a, [X] | (b, c)]

       .
      / \
     a   .
        / \
       /   \
      .     ,
     / \   / \
    X  [] b   c

+ = '-' - 1

      -             =
     / \           / \
    +  -1   or	  +   -
    |		     / \
    =		    -   1

( The difference revolves around the interpretation of - 1 -- is this an integer, or a term (-)/1?

List Processing [15 marks]

Write Prolog predicates to perform the following list processing tasks. Each predicate must define everything it needs to run. I.e. do not define your predicate in terms of append, etc. In each case, precisely state the conditions required for the predicate to work e.g. ``at least one of L or M must be a proper list''. Provide a thorough set of test data, and sample output. For example:

%-- append( List1, List2, List3 )
%-- is true when List3 is the concatenation of List1 and List2.  The
%-- arguments can be variables, partially instantiated lists, or ground
%-- lists.
%--
%-- Test cases:
%--   append([1,2], [3,4], [1,2,3,4])
%--      should succeed
%--   append(A, [2,3], [1,2,3])
%--      should succeed, binding A to [1]
%--   append([1,2], [2,3], L)
%--      should succeed, binding L to [1,2,3,4]
%--   append([1,2], B, [1,2,3]
%--      should succeed, binding B to [3]
%--   append(A, B, [1,2]
%--      should give multiple solutions
%--          A = [], B = [1,2]
%--          A = [1], B = [2]
%--          A = [1,2], B = []
%--   append([], B, L)
%--      should unify B and L
%--   append(A, [], L)
%--      should unify A and L

Write a predicate nextto(X, Y, List) that can be used to enumerate successive pairs from a list. E.g. nextto(X,Y,[1,2,3]) should generate the solutions X=1,Y=2 and X=2,Y=3. [5 marks]

nextto( X, Y, [X,Y|_] ).
nextto( X, Y, [_|List] ) :-
	nextto( X, Y, List ).

Test cases:

| ?- nextto( X,Y,[] ).
no
| ?- nextto( X,Y, [_] ).
no
| ?- nextto( X, Y, [1,2] ).
X = 1, Y = 2 ;
( no other solutions )

| ?- nextto( 1,2, List ).
List = [1,2|_] ;
List = [_,1,2|_] ;
etc.

Write a predicate to spit a list into its even and odd elements. E.g. ?- even_odd([a,b,c,d],E,O) should bind E to [b,d] and O to [a,c]. [5 marks]

even_odd( [], [], [] ).
even_odd( [O|List], Evens, [O|Odds] ) :-
	odd_even( List, Evens, Odds ).

odd_even( [], [], [] ).
odd_even( [E|List], [E|Evens], Odds ) :-
	even_odd( List, Evens, Odds ).

Test cases:

| ?- even_odd( [], Even, Odd ).
Even = Odd = []
| ?- even_odd( [a], Even, Odd ).
Even = [], Odd = [a]
| ?- even_odd( [a,b], Even, Odd ).
Even = [b], Odd = [a]
| ?- even_odd( L, [a,b], [c,d] ).
L = [c,a,d,b]
| ?- even_odd( L, E, O ).
L = E = O = [] ;
L = O = [_], E = [] ;
L = [_1,_2], E = [_2], O = [_1] ;
L = [_1,_2,_3], E = [_2], O = [_1,_3] ;
etc.

Write a predicate to generate permutations of a list. E.g. perm([1,2,3], L) should (on backtracking) bind L to [1,2,3], [1,3,2], [2,1,3], etc. [5 marks]

perm( [], [] ).
perm( [X|Xs], Ys ) :-
	perm(Xs, Ys1),
	select(X, Ys, Ys1).

select(X, [X|R], R).
select(X, [H|T], [H|R]) :-
	select(X, T, R).

Test cases:

| ?- perm( [], L ).
L = []
| ?- perm( [a], L ).
L = [a]
| ?- perm( [a,b], L ).
L = [a,b] ;
L = [b,a]
| ?- perm( L, [a,b] ).
L = [a,b] ;
L = [b,a] ;
( hangs )

To prevent the predicate hanging, it can be coded as follows:

permutation( Xs, Ys ) :-
	permutation( Xs, Ys, Ys ).

permutation( [], [], [] ).
permutation( [X|Xs], Ys, [_|Bound] ) :-
	permutation(Xs, Ys1, Bound),
	select(X, Ys, Ys1).

Tic-Tac-Toe [15 marks]

You are to write a Prolog program to play tic-tac-toe (noughts-and-crosses). If you don't know how to play this game, send me some email and I will explain, The board will be represented as a term b/9, i.e. a term with b as the principle functor, and nine arguments. The arguments of this term will be either be `-' (for empty), `x' (for a cross) or `o' (for nought). The first three arguments are the top row of the board; the next three the middle row; and the last three the bottom row.

Write a predicate defining the initial board. [1 mark]
```
start( b(-,-,-,-,-,-,-,-,-) ).
```

Write a predicate that tests if a tic-tac-toe board is a winning board for a given player. E.g. win(b(x,x,x,o,x,o,o,-,-),P) should succeed, binding P to x. [3 marks]

win(b(X,X,X,_,_,_,_,_,_), X) :- player(X).
win(b(_,_,_,X,X,X,_,_,_), X) :- player(X).
win(b(_,_,_,_,_,_,X,X,X), X) :- player(X).
win(b(X,_,_,X,_,_,X,_,_), X) :- player(X).
win(b(_,X,_,_,X,_,_,X,_), X) :- player(X).
win(b(_,_,X,_,_,X,_,_,X), X) :- player(X).
win(b(X,_,_,_,X,_,_,_,X), X) :- player(X).
win(b(_,_,X,_,X,_,X,_,_), X) :- player(X).

player( x ).
player( o ).

Write a predicate to define legal moves in tic-tac-toe. The predicate will be given a player (x or o) and a board, and will return a new board and move number (e.g. 1--9). E.g. move(M, x, b(-,-,-,-,-,-,-,-,-), B1) should succeed, binding B1 to, say, b(x,-,-,-,-,-,-,-,-) and M to 1. [5 marks]

move( 1, X, b(-,B,C,D,E,F,G,H,I), b(X,B,C,D,E,F,G,H,I) ).
move( 2, X, b(A,-,C,D,E,F,G,H,I), b(A,X,C,D,E,F,G,H,I) ).
move( 3, X, b(A,B,-,D,E,F,G,H,I), b(A,B,X,D,E,F,G,H,I) ).
move( 4, X, b(A,B,C,-,E,F,G,H,I), b(A,B,C,X,E,F,G,H,I) ).
move( 5, X, b(A,B,C,D,-,F,G,H,I), b(A,B,C,D,X,F,G,H,I) ).
move( 6, X, b(A,B,C,D,E,-,G,H,I), b(A,B,C,D,E,X,G,H,I) ).
move( 7, X, b(A,B,C,D,E,F,-,H,I), b(A,B,C,D,E,F,X,H,I) ).
move( 8, X, b(A,B,C,D,E,F,G,-,I), b(A,B,C,D,E,F,G,X,I) ).
move( 9, X, b(A,B,C,D,E,F,G,H,-), b(A,B,C,D,E,F,G,H,X) ).

Write a predicate play that generates all complete tic-tac-toe games. E.g.

| ?- play( Moves ).
Moves = [1,2,3,4,5,6,7] ;
Moves = [1,2,3,4,5,6,8,7,9] ;
Moves = [1,2,3,4,5,6,8,9,7] ;
Moves = [1,2,3,4,5,6,9] ;
Moves = [1,2,3,4,5,7,6,8,9]
etc.

Note that boards like [1,2,3,4,5,6,7,8,9] are not generated, since there is an earlier win (to x in this case). [6 marks]

play( Moves ) :-
	start(B0),
	play( Moves, x,o, B0 ).

play( [], _,_, Win ) :-
	win(Win,_),
	!.
play( [M|Moves], P,Q, B0 ) :-
	move(M, P, B0, B1),
	play(Moves, Q,P, B1).

How would you ask Prolog to look for a five-move game?
```
| ?- length(Moves,5), play( Moves ).
```