CPSC 631 - Homework #1
due: Tues, Oct 4, 2005


1. Sorting in Prolog

Write a Prolog program to define a predicate 'sorted(L)' for L a list
of integers, which is true if and only if L is sorted in ascending order.

Write a Prolog program to define a predicate 'perm(L,M)', which is true if
and only if M is a permutation of L.

Define 'sort(L,M)', where M is a sorted version of L, using 'perm' and 'sorted'.


2. SEND+MORE=MONEY

SEND + MORE = MONEY is a classical ``crypto-arithmetic'' puzzle: the
variables S, E, N, D, M, O, R, Y represent digits between 0 and 9, and
the task is finding values for then such that the following arithmetic
operation is correct:

     S  E  N  D
+    M  O  R  E
----------------
  M  O  N  E  Y

Moreover, all variables must take unique values, and all the numbers
must be well-formed (which implies that M > 0 and S > 0. 


3. Jobs Puzzle

There are four people: Roberta, Thelma, Steve, and Pete.
Among them, they hold eight different jobs.
Each holds exactly two jobs.
The jobs are chef, guard, nurse, clerk, police officer (gender not implied), 
  teacher, actor (gender implied), and boxer.
The job of nurse is held by a male.
The husband of the chef is the clerk.
Roberta is not a boxer.
Pete has no education past the ninth grade.
Teachers, nurses, and police officers must be educated.
Roberta, the chef, and the police officer (3 separate people) 
  went golfing together.

Question: Who holds which jobs?