Re: Famoue problem by Eric Emmett

Hi Robert,

this is a type of Zebra puzzle which usually involve enumerating possible
variable assignments and then checking constraints.  The constraints you
formulated can't be evaluated by PowerLoom, since there is not enough
information to get the evaluation started.  You basically have to try
different possible assignments and then see whether any of them works out.
This type of search is best formulated via backward inference in PowerLoom.
For example, here is one possible formulation:

STELLA(27): (retrieve all (?a ?b ?c ?d ?e)
                     (and (=3D ?days (listof 1 2 3 4 5 6 7))
                          (member-of ?a ?days)
                          (member-of ?b ?days)
                          (member-of ?c ?days)
                          (member-of ?d ?days)
                          (member-of ?e ?days)
                          (=3D (- ?d ?f) (- ?a ?d))
                          (=3D (- ?f ?c) (- ?b ?f))
                          (=3D ?e 6)
                          (different ?a ?b ?c ?d ?e)
                          (=3D ?birthdays (listof ?a ?b ?c ?d ?e))
                          ;; these clauses encode that birthdays are consec=
utive:
                          (minimum-value ?birthdays ?minb)
                          (maximum-value ?birthdays ?maxb)
                          (=3D (- ?maxb ?minb) 5)))
There are 4 solutions:
  #1: ?A=3D7, ?B=3D4, ?C=3D2, ?D=3D5, ?E=3D6
  #2: ?A=3D7, ?B=3D2, ?C=3D4, ?D=3D5, ?E=3D6
  #3: ?A=3D2, ?B=3D7, ?C=3D5, ?D=3D4, ?E=3D6
  #4: ?A=3D2, ?B=3D5, ?C=3D7, ?D=3D4, ?E=3D6

We get four solutions above, since the arithmetic constraints also allow
negative distances.  If we add the inequalities below to constrain not only
the birthday differences but also their relative order as given in the prob=
lem
forumlation, then we get a unique solution:

STELLA(28): (retrieve all (?a ?b ?c ?d ?e)
                     (and (=3D ?days (listof 1 2 3 4 5 6 7))
                          (member-of ?a ?days)
                          (member-of ?b ?days)
                          (member-of ?c ?days)
                          (member-of ?d ?days)
                          (member-of ?e ?days)
                          (=3D (- ?d ?f) (- ?a ?d))
                          (< ?f ?d)
                          (< ?d ?a)
                          (=3D (- ?f ?c) (- ?b ?f))
                          (< ?c ?f)
                          (< ?f ?b)
                          (=3D ?e 6)
                          (different ?a ?b ?c ?d ?e)
                          (=3D ?birthdays (listof ?a ?b ?c ?d ?e))
                          (minimum-value ?birthdays ?minb)
                          (maximum-value ?birthdays ?maxb)
                          (=3D (- ?maxb ?minb) 5)))
There is 1 solution:
  #1: ?A=3D7, ?B=3D4, ?C=3D2, ?D=3D5, ?E=3D6
STELLA(29): =


Hope that helps,

Hans

--------------------------------------------------------------------------
Hans Chalupsky, PhD                     USC Information Sciences Institute
Project Leader, Loom KR&R Group         4676 Admiralty Way
<[email protected]>                          Marina del Rey, CA 90292
(310) 448-8745
--------------------------------------------------------------------------

>>>>> Robert Onslow <[email protected]> writes:

> Dear All.
> I am trying Powerloom to solve the following famous problem by Eric Emmet=
t:
 =

> Alf, Bert, Charlie, Doug, Ernie and Fred have their birthdays on consecut=
ive days, but not necessarily in that order.
> Doug=E2??s birthday is as many days before Alf=E2??s as it is after Fred=
=E2??s. Charlie=E2??s birthday is as many days before Freds as
> Berts is after Freds. This year, Ernie=E2??s birthday is on  a Saturday, =
On what days of the week do the birthdays of the other 5
> men fall this year?

> I have got
> (defconcept person)
> (deffunction birthday ((?p person)) :- > (?n integer))
> (assert (and (person a) (person b) (person c) (person d) (person e)))
> (assert (=3D (- (birthday a) (birthday d)) (- (birthday d) (birthday f)))
> (assert (=3D (- (birthday f) (birthday c)) (- (birthday b) (birthday f)))
> (assert (birthday e 6)
 =

> What is the best way to assert that the set of birthday values is mutuall=
y disjoint and drawn from a list of integers from 1 to
> 7. I can=E2??t seem to do it in a way which yields solutions.
> Can anyone help? I have solved this problem in Mozart and Prover/Mace and=
 would like to do the same in Powerloom, which I feel
> will be the most intuitive solution.
 =

> Thanks
> Robert


> ----------------------------------------------------------------------
> _______________________________________________
> powerloom-forum mailing list
> [email protected]
> http://mailman.isi.edu/mailman/listinfo/powerloom-forum