Week 5: Exercises

1. Beethoven's Wig

Someone has stolen Beethoven's wig and has put it in one of four locked boxes. The boxes are numbered 1,2,3,4 in that order. There are four different keys that each have their own color. Also:

  1. The green key goes to the third or fourth box.

  2. The wig is to the left of the fourth box.

  3. The wig is to the right of the first box.

  4. The yellow key is to the left of the wig.

  5. The blue key is to the right of the yellow key and to the left of the green key.

  6. The red key goes to the first box.

Which box contains Beethoven's wig? Write a Prolog program that can find the answer.

2. Cryptarithmetic

In this cryptarithmetic puzzle, every letter stands for a different digit:

  A P P L E
+ G R A P E
+   P L U M
=========== 
B A N A N A

Additionally, no leading digit may be zero.

Write a Prolog program that can find a solution to the puzzle.

3. N Queens

Can we place N queens on a chessboard so that none of them attack any other?

Write a predicate queens(N, L) that is true if L is a solution to the N-queens problem. L will be a list of integers from 1 to N representing the row position of the queen in each column. Your predicate should be able to check and generate solutions.

4. Magic Square

A magic square is a square of size N x N that contains all integers from 1 .. N2 and in which every row, column and diagonal adds to the same value.

Write a Prolog predicate that can test whether a square is magical. When run backward, it should also be able to generate magic squares of a given size.

5. Mini-Minesweeper, Revisited

Consider the following tiny Minesweeper board of dimensions 5 x 2:

1?
2?
2?
2?
1?

A number N means that there are N mines in adjacent squares (which may be adjacent horizontally or diagonally).

Write a Prolog program that can find all possible positions for the mines. Use integer constraints.

6. Vertical Minesweeper

Generalize the previous exercise as follows. Consider a Minesweeper board of dimensions N x 2, where the left column contains integers and the contents of all squares in the right column is unknown. Write a predicate minesweeper(L, M), where L is the integers in the left column, and M is a list of values 'mine' or 'no_mine'. For example, minesweeper([1, 2, 2, 2, 1], M) will give a solution to the previous exercise.

7. Tree Check

IIn Prolog we can represent a binary tree as either the atom nil (for the empty tree) or as t(L, V, R), where V is the value at the root and L and R are the left and right subtrees.

Write a Prolog predicate isTree(T) that is true if T is a binary tree. (It does not need to be a binary search tree; values can appear in any order and can have any type).

8. Tree Sum

Write a predicate sum(T, N) that is true if T is a binary tree of integers and N is the sum of the integers in the tree.

9. Tree Leaves

Write a Prolog predicate leaves(T, S) that is true if S is a list of values in the leaves of the binary tree T. Recall that a leaf is a node with no chlidren. Ideally your predicate will run in time O(|S|). Your predicate should work in both directions.

10. Symmetrical Tree

Write a Prolog predicate symmetrical(T) that is true if T is a symmetrical binary tree: its left-to-right reflection is itself.

11. Binary Search Tree

Write a Prolog predicate is_search_tree(T) that succeeds if T is a binary tree of integers that satisfies the ordering requirements of a binary search tree: for any node N has value V, every value in N's left subtree has a value that is less than V, and every value in N's right subtree has a value that is greater than V.

12. Tree Fold

Write a Prolog predicate tree_foldl(G, T, A, R) that is like foldl, but folds the goal G across all values in the binary search tree T to produce a result R from an initial accumulator value A.

13. Rectangles

Suppose that we have a set of rectangles, each with a given width and height. We want to know whether they can be packed into a rectangle R with a given width and height and depth. The rectangles may not be rotated.

We will represent a rectangle as a structure rect(Width, Height).

Write a predicate pack(L, R, Positions) that is true if the rectangles in list L can be packed into the rectangle R at the given list of positions. A rectangle's position pos(X, Y) is the position of its upper-left corner relative to the upper-left corner of rectangle R.

14. Rectangles, Rotated

Modify your solution to the previous exercise so that the rectangles in list L may be rotated by 90 degrees as they are packed into R. Now each position should have the form pos(X, Y, R), where R = rot if the rectangle has been rotated by 90 degrees, otherwise R = not.