Spring 99, CSE 428: Assignment 9

Distributed: April 15.
Due: April 27 in class.
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with Logic Programming.

Please give an hard copy of the source code (i.e. a file containing the definitions of the requested relations, plus the auxiliary relations, if any) to the instructor by the due date. Furthermore, you should also email your source code to cg428@cse.psu.edu by the due date, so to allow us to check that your program runs correctly. Please send the code as an attachment (not by "cut-and-paste"), and use the 4 digits of your student id, followed by ".pl", as the filename (example: if your id is 1001, then the file should have name 1001.pl).

Please make sure that your source code can be compiled and executed under SWI Prolog on Unix. For a brief explanation on how to run SWI Prolog and how to load and execute programs, see http://www.cse.psu.edu/~catuscia/teaching/prolog/index.html

  1. [Points 15] Assume given a set of clauses of the form 
       father(name1,name2)
    representing the relation "name1 is father of name2"

    1. Define the predicate 
         uncle(X,Y)
      representing the relation "X is an uncle of Y", i.e. "X is a brother of the father of Y".

    2. Define the predicate 
         relative(X,Y)
      representing the relation "X and Y either have an ancestor in common, or X is an ancestor of Y, or Y is an ancestor of X".

    Example: if one of the trees representing the fatherhood relation contains a subtree like 

            arnold
         / \
       bob carl
        |
       dan
    then we should have the following answers: 
    ?- uncle(X,Y).
 
X = carl
Y = dan ;
 
No

?- relative(X,Y).
 
X = arnold
Y = bob ;
 
X = arnold
Y = dan ;
 
X = arnold
Y = carl ;
 
X = bob
Y = dan ;
 
X = bob
Y = arnold ;
 
X = bob
Y = dan ;
 
X = bob
Y = carl ;
 
X = dan
Y = arnold ;
 
X = dan
Y = bob ;
 
X = dan
Y = carl ;
 
X = carl
Y = arnold ;
 
X = carl
Y = bob ;
 
X = carl
Y = dan ;
 
X = dan
Y = bob ;
 
No
    Do not worry about the order of the answers, about repetitions of the same answer and about answers that represent symmetric solutions (like X = bob Y = dan and X = dan Y = bob). However, avoid infinite loops and avoid wrong answers, like X = bob Y = dan for the query uncle(X,Y) and X = bob Y = bob for the query relative(X,Y). To this purpose, you might find useful to use the relation not(X=Y), which holds if and only if X and Y are instantiated to different values.

  2. [Points 15] Define the predicate 
       sublist(L1,L2)
    representing the relation "L1 is a sublist of L2", i.e. "L1 contains a sequence of contiguous elements identical to L2". Note that this exercise corresponds to Exercise 2 of Assignment 7.

    Example: We should get the follwowing answers: 

    ?- sublist(L,[1,2,3]).
 
L = [] ;
 
L = [1] ;
 
L = [1, 2] ;
 
L = [1, 2, 3] ;
 
L = [] ;
 
L = [2] ;
 
L = [2, 3] ;
 
L = [] ;
 
L = [3] ;
 
L = [] ;
 
No
    Again, don't worry about repetitions of the same answer and about the order of the answers. Avoid infinite loops, at least for queries where the second argument is completely instantiated (i.e. it does not contain variables).

  3. [Points 20] Define the predicate 
       flat(L1,L2)
    representing the relation "L2 is the flattened version of L1". In other words, L1 is a list whose elements can be lists, whose elements can be lists again, etc. L2 should contain the same items of L1, and in the same order, but where all levels of square brackets (eccept the top one) are "stripped off". Note:You are not allowed to use the predefined predicate flatten.

    Example: We should get the follwowing answers: 

    ?- flat([],L).
 
L = [] ;
 
No

?- flat([1,2],L).
 
L = [1, 2] ;
 
No

?- flat([1,[[2],[[3]]],[],[4,5]],L).
 
L = [1, 2, 3, 4, 5] ;
 
No
    Avoid infinite loops, at least for queries where the first argument is completely instantiated (i.e. it does not contain variables).

    You might find useful to use a predicate not_list(X), which holds iff and only if X is not a list. Such predicate can be defined as 

       not_list(X) :- not(X=[]), not(X=[_|_]).
    Note that the predicate flat as defined above could not be implemented in ML, because in ML lists are homogeneous, i.e. all the elements must be of the same type.

  4. [Points 50] Suppose that we have a chessboard of N * N positions, and that we want to place on it N queens so that no queen can attack any other queen. Remember that two queens can attach each other if and only if they are either in the same row, or in the same column, or in the same diagonal. A solution to the problem can be represented as a list Pos = [J1,J2,...,JN], where each JI represents an index of column, and means that a queen is placed in the position (I,JI) in the chessboard.

    Define a predicate 

       queens(N,Pos)
    Such that: given a positive number N, the relation holds if and only if Pos is a list which represents a solution to the problem of the N queens.

    Example: We should get the follwowing answers: 

    queens(4,Pos).
 
Pos = [2, 4, 1, 3] ;
 
Pos = [3, 1, 4, 2] ;
 
No

?- queens(5,Pos).
 
Pos = [2, 4, 1, 3, 5] ;
 
Pos = [3, 1, 4, 2, 5] ;
 
Pos = [1, 3, 5, 2, 4] ;
 
Pos = [2, 5, 3, 1, 4] ;
 
Pos = [1, 4, 2, 5, 3] ;
 
Pos = [5, 2, 4, 1, 3] ;
 
Pos = [4, 1, 3, 5, 2] ;
 
Pos = [5, 3, 1, 4, 2] ;
 
Pos = [3, 5, 2, 4, 1] ;
 
Pos = [4, 2, 5, 3, 1] ;
 
No

?- queens(3,Pos).
 
No
    We only requires that the program works correctly when the first argument is instantiated (to a positive integer). Do not worry about the generation of symmetric solutions, like Pos = [2, 4, 1, 3] and Pos = [3, 1, 4, 2].

    Hint: The simplest solution to this problem (although not very efficient) consists in the so-called "generate and test" approach: first we generate a candidate to a possible solution, and then we check that it satisfies the constraints. Following this scheme, the predicate queens can be defined as: 

        queens(N,Pos) :- generate(N,Pos), safe(Pos).
    where: