CS-205 Declarative Programming Assignment

Question 1: Recursion, Lists and Accumulating Parameters

(a) Write the following program and compile it:

% Program: ROYAL

parent(queenmother,elisabeth).             parent(elisabeth,charles).

parent(elisabeth,andrew).                     parent(elisabeth,anne).

parent(elisabeth,edward).                     parent(diana,william).

parent(diana,harry).                             parent(sarah,beatrice).

parent(anne,peter).                              parent(anne,zara).

parent(george,elisabeth).                      parent(philip,charles).

parent(philip,andrew).                           parent(philip,edward).

parent(charles,william).                         parent(charles,harry).

parent(andrew,beatrice).                       parent(andrew,eugene).

parent(mark,peter).                              parent(mark,zara).

parent(william,georgejun).                     parent(kate,georgejun).

parent(kate,charlotte).

Define the following predicates on the persons in the program ROYAL.

(1) the_royal_females/1 (a list of all female members of the Royal Family)

(2) the_royal_males/1 (a list of all male members of the Royal Family)

(3) the_royal_family/1 (a list of all members of the Royal Family)

(4) mother/2

(5) has_child/1.

(6) ancestor/2 (use recursion).

(7) descendant/2 (use recursion or (6)).

Translate the following questions into Prolog queries and try them out:

(8) Who is the mother of Beatrice?

(9) Who has a child (one or more)?

(10) Who is a desencendant of the Queenmother?

(b) Use predicates of question (a) to define predicates sibling/2 and aunt/2 (w.r.t. the Royal Family). [Query: Who are the siblings of charles?]

(c) Write a predicate palindrome_list(L) which checks whether L is a palindromic list (i.e., reads the same forwards and backwards). Examples are [a,b,c,b,a] and [12,a,5,a,12]. The base cases are when the list is empty or a singleton. The general case is to check that the first element is the same as the last element and (recursively) the remaining part of the list is palindromic. To achieve this write a predicate last_element(L,X,R) which instantiates X to the last element of L and R to L with X removed. The easiest way to de?ne this is to use append.

(d) An example of a recursive predicate and a tail recursive version using an accumulating parameter.

i. The square of the Euclidean distance between two vectors x_i and y_i is _i=1∑ⁿ(x_i - y_i)_*(x_i - y_i). Write a recursive predicate euclidsqr(X,Y,ED) which returns the value in ED when X and Y are lists representing vectors of the same length.

ii Now write a tail recursive predicate euclidsqr_acc(X,Y,A,ED) to compute the same function using the accumulating parameter A to store intermediate calculations. (Look at sum_a in example prolog code).

Question 2: Backtracking Solution of Futoshiki Puzzle

Here is a Futoshiki puzzle downloaded from the internet (popular in many news-papers).

The aim is to place digits 1-4 in the empty cells so that each row and column contains distinct digits and the constraints speci?ed by the inequality signs are all satisfied. You are to write a generate and test backtracking program in Prolog to solve this puzzle.

(a) Define the predicate member_rem(E,L,R) which chooses an element E from list L leaving remainder R.

(b) Using the above define gen_list_n(N,D,L) which generates a list L of N distinct elements from the list D where the length of D is ≥ N.

gen_n(0, _,[]).

gen_n (N, D, [X|Xs]) :-

N > 0, N1 is N - 1,

 . . . .

gen_n(N1, D1, Xs).

Define gen4(L) to generate a list of 4 distinct digits from 1-4.

(c) To check that two list of numbers X, Y are different at each entry (i.e, Xi differs from Yi for all i) define a predicate distinct_in_entries(X,Y). As elements of the lists are numbers you use =\= to check for inequality.

(d) Now you can generate a possible solution [R1, R2, R3, R4] where Ri are rows of 4 distinct numbers from 1-4 and all the columns consist of distinct numbers as follows: generate R1 (using gen4), then R2 and check R1 and R2 are distinct at all entries; generate R3 and check this is distinct in entries with R1 and R2 and so on. Call this predicate gen_poss_soln([R1, R2, R3, R4]). So e.g., it will produce [[1, 2, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]] as an output.

 (e) Finally define solve ([R1, R2, R3, R4]) using generate and test by generating a possible solution, [R1, R2, R3, R4], and then testing each of the in-equalities. Notice that the only constraints in R1 are on R11 and R12 (R11 > R12) so you only need say R1 = [R11, R12, _, _]. You should deal with the other rows and constraints in a similar manner.

(f) The solver solve will find the solution for a 4x4 Futoshiki problem in a reasonable time, but if you scaled it up in an obvious manner for 5x5 problems it would be too inefficient. So produce a more efficient version of solve which splits up the generate and test tasks. Call this solve_in_steps ([R1, R2, R3, R4]) and this time, generate R1 first and test any constraints you can, just involving row 1 (in this case its only R11 > R12), then generate R2 and apply the constraints on any variables in R1 and R2 and so on. This approach should be able to cope with 5x5 problems (though there are many other improvements you can make to speed up the solver).