CSI 2120

Lab 8: Prolog

Exercise 1: Permutations

Given three colors: red, green and blue. Generate a list that finds all possible permutations of these three colors. Note, that in a permutation order matters and e.g., [ red, blue, green] is not the same as [ green, red, blue]. Hint: use setof.


color(red).
color(green).
color(blue).

?- __________________.


L = [[red,red,red],[red,red,green],[red,red,blue], ... ]

Exercise 2: Leaf Nodes

Write a Prolog program that finds all the leaf nodes of binary tree and returns them in a list.


?- leafNodes(t( 2, nil, t(3, nil, nil)),L).
L = [3].

Exercise 3: Cabin Puzzle

Six girls sleep in bunk beds in the junior cabin at camp . Each girl has a different color blanket on her bed. The beds are lined up in a row with red, black, yellow, brown, blue and green blankets.

Reeva and Haley are closest to the door.
The color of the blankets on the bottom bunks all begin with the same letter.
The color of Beth's blanket doesn't begin with the same letter as her name.
The blue blanket is under the red blanket.
Liza and Kayla like their lower bunks.
Kayla is in the middle bed.
Zoe doesn't share a bunk with Kayla.
The brown blanket is at the end of a row.
The yellow is above the black blanket.

The solution should be represented as follows Sol= [[Name,Color],[Name,Color],...] where the order encodes the beds. They are in the following order bottom, up, bottom, up from left to right. Using the built-in predicate member/2 and the or operator ; Complete the following bunkbed predicate:


bunkbeds(L):- L=[[N1,C1],[N2,C2],[kayla,C3],[N4,C4],[N5,C5],[N6,C6]],
    ((N1=reeva,N2=haley);(N2=reeva,N1=haley)),  /* Constraint 1.*/
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________,
    ______________________________________.

Exercise 4 and Quiz:

Please hand-in the answer to this question on Virtual Campus during your lab session but at the latest by Friday 6:00pm! Remember, your submission will only count if you have signed the lab attendance sheet.

Complete the Prolog program below that processes a binary tree replacing all keys in nodes with a value of 0 with a value of 1.


  zeroNodes(nil,_______________________) :- !.

zeroNodes(t(0,L,R),________________________) :- 
    zeroNodes(L,___________________),
    zeroNodes(R,___________________), !.
        
zeroNodes(t(Key,L,R),________________________) :-
    zeroNodes(L,___________________),
    zeroNodes(R,___________________).



Examples:

?- zeroNodes(t(0,nil,nil),T).
T = t(1, nil, nil).

?- zeroNodes(t(0,t(3,nil,t(0,nil,nil)),t(3,nil,nil)),T).
T = t(1, t(3, nil, t(1, nil, nil)), t(3, nil, nil)).