The purpose of this assignment is to provide some experience with logic programming.

1. [Points 40]   Define in Prolog a predicate sub_ord(K,L) which is true if and only if L is any maximal ordered sublist of K containing at least two elements. For instance, we should have the following results:

      ?- sub_ord([1,2,2,9,6,8,4,2,4,5],L).
      
      L = [1,2,2,9];
      L = [6,8];
      L = [2,4,5];
      no
   
      ?- sub_ord([6,5,1,1,4,6,8,7,5,1,3,3,5],L).
   
      L = [1,1,4,6,8];
      L = [1,3,3,5];
      no
   

   You can assume that K and L are integer lists.

   Hint: A sublist of a list can be generated by using append in reverse mode. For instance, to obtain all the sublists of lenght at least 1 of the list L, one can define the following predicate:

      sub(L,[X|S]) :- append(_,K,L), append([X|S],_,K).
   

   For instance, we have:

      ?- sub([a,b,c],S).
   
      S = [a] ;
      S = [a, b] ;
      S = [a, b, c] ;
      S = [b] ;
      S = [b, c] ;
      S = [c] ;
      No
   

   ---

2. [Points 20]   Trees can be represented in Prolog in the same way as in ML, by using the term leaf(X) to represent a tree composed by a unique node (leaf) labeled by X, and the term node(T1,X,T2) to represent a tree with root X , left subtree T1, and right subtree T2 . For example, the following trees

           T1              T2
   
            a               1
           / \             / \
          b   c           2   3
         / \             / \    
        d   e           4   5  
                           / \
                          6   7
   

   Can be represented by the following Prolog terms:

     T1 = node(node(leaf(d),b,leaf(e)),a,leaf(c))
   
     T2 = node(node(leaf(4),2,node(leaf(6),5,leaf(7))),1,leaf(3))
   

   Define a predicate branch(T,L) which is true iff L is the list of nodes of a branch (a path from root to leaf) in T. For instance, for the trees T1 and T2 illustrated above, we should have the following results:

      ?- branch(node(node(leaf(d),b,leaf(e)),a,leaf(c)),L).
   
         L = [a,b,d];
         L = [a,b,e];
         L = [a,c];
         no
   
      ?- branch(node(node(leaf(4),2,node(leaf(6),5,leaf(7))),1,leaf(3)),L).
   
         L = [1,2,4];
         L = [1,2,5,6];
         L = [1,2,5,7];
         L = [1,3];
         no
   
   

   ---

3. [Points 40]   A maze can be thought of as a bidimentional array in which each position can contain the value " " (blank) or "X". Finding an exit in a maze from a given position (m,n) means to find a path through the blank positions from (m,n) till a position on the border. We assume that it is possible to move only in horizontal and in vertical (not in diagonal).

   The following is an example of a maze:

        123456789
   
      1 XXX XXXXX
      2 X XX    X
      3 X    X X
      4 X XX   XX
      5 X  X XX X
      6 X XXX   X
      7 XXX   X X
      8  XX X   X
      9 XXX X XXX
   
   

   For instance, from Position (5,8) we can exit (by two different exists), but from Position (5,5) we cannot exit.

   In Prolog, one convenient way to represent a maze is to list all the blank positions. This can be done by defining a predicate m(M,N) which holds iff (M,N) is a blank position. Note that we are representing a position as a pair of numbers (M,N): the index of the row and of the column respectively.

   For instance the m above would be represented by the following program:

                              m(1,4).
              m(2,2).                 m(2,5). m(2,6). m(2,7). m(2,8).
              m(3,2). m(3,3). m(3,4). m(3,5).         m(3,7).         m(3,9).
              m(4,2).                 m(4,5). m(4,6). m(4,7). 
              m(5,2). m(5,3).         m(5,5).                 m(5,8). 
              m(6,2).                         m(6,6). m(6,7). m(6,8). 
                              m(7,4). m(7,5). m(7,6).         m(7,8).
      m(8,1).                 m(8,4).         m(8,6). m(8,7). m(8,8).
                              m(9,4).         m(9,6). 
   
   
   

   Define a predicate can_exit(M,N) which checks whether it is possible to exit the maze from position (M,N). For instance, we should have:

      ?- can_exit(5,5).
   
      no
   
      ?- can_exit(5,8).
   
      yes
   
      ?- can_exit(8,1).
   
      yes
      
      ?- can_exit(8,2).
   
      no
   

   You can assume that the maze is 9 x 9, and hence the positions on the border are those of the form (1,_), (_,1), (9,_), and (_,9).

   Hint: The tricky part of this problem is to avoid infinite loops, which could in principle be generated by the circular paths. In order to avoid this problem, you should maintain a list of the positions which have already been visited, and then, each time you try a new position, you should check that this position is not in the list. This check can be done by using the predefined connective not (logical negation): assuming that memb represents the membership predicate, namely memb(x,k) holds iff x is a member of the list k, then not(memb(x,k)) holds iff x is not a member of the list k (provided that x and k are instantiated to non-variable terms, otherwise there are some subtle problems in the use of not).

How to write and test your solution

Download this solution frame and fill it in with your definitions. Save it with name XXXX.pl, where XXXX are the last 4 digits of your student id.

The code of the examples above is here. You can download it, then save it with name definitions.pl. Now you can enter SWI-Prolog with the Unix command

   /home/users3/cg428/pl-3.2.9/src/pl

   ?- consult('XXXX.pl').
   ?- consult('definitions.pl').

   ?- can_exit(5,5).

   no

Please note the following:.

1. Please make sure that your program can be compiled and executed under the Unix SWI-Prolog. Solutions which cannot be compiled or executed will receive, at most, 40 points.
2. Please don't change the name of the predicates and the representation !!!.
3. Its your responsibility to write a sound, reliable program, so please test your code thoroughly before you submit it.
4. The TA will test your program with some additional test cases. A program which works only for the examples in this page will receive, at most, 70 points. Otherwise it will receive a score between 70 and 100 depending on how many of the additional tests it passes.
5. A program which enters an infinite loop on a certain test will be considered having failed the test.

Format of the solution