Permutation Puzzles

```Consider five women, Anne, Betsy, Corrine, Donna, and Emily, who live
(not necessarily respectively) in the cities Anaheim, Baltimore,
Cleveland, Denver, and Enumclaw.  Each woman has exactly one son, and
their names are Andy, Bob, Chuck, Dave, and Edward (again, not
necessarily in that order).  The ages of the women are 41, 42, 43,
45, and 46 (again, not necessarily in that order).  We're given the
following information:

1. Emily lives in Anaheim. She's one year older than Chuck's
mother who lives in Cleveland.
2. Edward's mother is Donna.  She's one year older than Anne whose
son isn't Dave.
3. The woman in Denver (who isn't Betsy) is younger than the woman in
Enumclaw.
4. Andy's mother (not Corrine) is 43.
5. The woman living in Baltimore is 45.

How old is each woman, who is her son, and where does she live?
Moreover, is there an efficient formal technique for solving problems
like this?  Perhaps if we think about the thought process we would
use to solve it "by hand", and then think about how we might program
a computer to do the same thing, the process could be formalized.

The most useful information in the particular puzzle stated above
seems to be the ages and their relations to each other.  There are
two distinct pairs of women whose ages differ by only one, and the
list of ages contains only three such possibilities.  Furthermore,
we know Chuck's mother isn't 45 (from her location), so we must have
either [Emily=42,Chuck's=41] or else [Emily=43,Chuck's=42].  Both of
these involve the age 42, so we have Donna=46 and Anne=45, hence
Anne is in Baltimore.  Also, we must put Donna in Enumclaw to make
its resident older than the woman in Denver, who must be Corrine.
Then we see Andy must be Emily's son, so she is 43, and the rest
falls into place.  The result is

Emily     Anne        Betsy       Corrine    Donna
43        45          42          41         46
Andy      Bob         Chuck       Dave       Edward
Anaheim   Baltimore   Cleveland   Denver     Enumclaw

There are probably many different and equivalent ways of expressing
and formalizing the constraints.  One way is in terms of compositions
of permutations.  We have four groups (names, ages, son's names, and
locations) of five elements, and we can arbitrarily assign the numbers
1 to 5 to the elements of each group as shown below

City        Woman       Son         Age

1     Anaheim      Anne        Dave         41
2     Baltimore    Donna       Chuck        42
3     Cleveland    Emily       Bob          43
4     Denver       Betsy       Andy         45
5     Enumclaw     Corrine     Edward       46

We seek permutations of these four sets that, when aligned, satisfy
certain conditions.  The solution can be expressed by the following
set of four permutations

Cities      12345 I
Women       31452
Sons        43215
Ages        34215

These permutations match each city with the resident woman, her
son, and her age.  Of course, there are really 120 distinct ways of
permuting the five columns, and they all represent the same logical
solution.  I just arbitrarily chose to arrange the columns so that
the cities have the identity permutation 12345.  Three other ways of
expressing the same solution are

Cities  25134        Cities  43215        Cities  43125
Women   12345 I      Women   54132        Women   54312
Sons    35421        Sons    12345 I      Sons    12435
Ages    45321        Ages    12435        Ages    12345 I

where "I" denotes the category that has the identity permutation.
Obviously if the permutation from Cities to Women (for example) is
31452, then the inverse is 25134.  Notice that the composition of
any permutation and its inverse is the identity permutation.  More
generally, the composition of any "loop" of permutations must yield
the identity, and this fact can be used to infer information about
some of the permutations given information about some of the others.
To illustrate, consider the three categories Cities, Ages, and Women,
and note that we have the permutations

Cities to Women:  31452
Women to Sons:    35421
Sons to Cities:   43215

The composition of these three permutations, in sequence, necessarily
gives the identity.  To show how this establishes conditions on the
solution, recall that we were told explicitly that Emily is in Anaheim,
so the permutation from Women to Cities is of the form {**1**}.  In
all but two permutations from Cities to Ages, namely, {24135} and
{34215}.  Taking the second of these, we have

Cities to Ages:  3****
Ages to Women:   *****
Women to Cities: **1**

The composition of these three permutations must be the identity
permutation, which clearly requires that the permutation from Ages
to Women must be of the form {**3**}.  In other words, we've deduced
that the 43 year old woman is Emily, which determines the rest of
the solution.

Of course, there's nothing profound going on here.  The leading "3"
in the permutation from Cities to Ages signifies that the woman in
Anaheim is 43, and the middle "1" in the permutation from Women to
Cities signifies that Emily is in Anaheim.  These two facts in
combination obviously imply Emily is 43.  This just illustrates how
information on one basis is related to information on other bases.

It's important to recognize that there are three distinct aspects of
puzzles of this kind.  The first is just general computation.  For
example, the particular puzzle above required making use of numerical
relations between a given set of numbers.  More generally, conditions
could be imposed such as "The age of person A has exactly two prime
divisors in common with the age of person B".  Before even beginning
to solve the puzzle, we must first resolve all the computational
"clues" of this kind, and express them as constrants on the allowable
permutations. These computational aspects could be arbitrarily
difficult - or even practically impossible - to resolve.  Fro example,
it might be specified that person A lives in city D if and only if
the 100 trillionth decimal digit of pi is 7.  This is a perfectly
deterministic and well-defined "clue", but it is practically useless.

Assuming we can solve the computational aspects of the puzzle, the
second task is to determine which permutations between two given sets
are allowed based on a set of clues.  This has nothing to do with
transferring information from one basis to another.  It is essentially
just the classical "satisfiability problem", i.e., given a set of
logical variables feeding into a fixed system of logic gates with a
single logical output variable, determine which (if any) input states
set the output TRUE.  (It is this kind of reasoning that enables us
to say the permutation from Cities to Ages must be either {24135} or
{34215}, without even taking any other information into account.)
This is known to be NP-complete, so we can't expect there to exist
any simple recipe that would work in polynomial time in all cases.

The third task involved in solving such puzzles is to relate the
information that has been provided on different bases.  It is only
this third task (the simplest of the three) that can be formalized
in terms of the compositions of permutations.
```