Re: Famoue problem by Eric Emmett

Thanks Hans
Is it possible to generalise your answer in a way which defines birthday as =

a function whose value is constrained to be an integer drawn from =

integer-interval, with upper bound 7 and lower bound 1, with all birthdays =

distinct. I can't find much documentation on using integer-interval.
Robert




-----Original Message----- =

From: Hans Chalupsky
Sent: Tuesday, September 13, 2011 2:01 AM
To: Robert Onslow
Cc: [email protected]
Subject: Re: Famoue problem by Eric Emmett

Below is a minor correction to my original reply which didn't handle ?f
in all places:

STELLA(41): (retrieve all (?a ?b ?c ?d ?e ?f)
                     (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)
                          (member-of ?f ?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 ?f)
                          (=3D ?birthdays (listof ?a ?b ?c ?d ?e ?f))
                          (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, ?F=3D3

In fact, looking at the structure of the constraints, we only have to
enumerate two of the variables to get a solution:

STELLA(42): (retrieve all (?a ?b ?c ?d ?e ?f)
                     (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)
                          ;(member-of ?f ?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 ?f)
                          (=3D ?birthdays (listof ?a ?b ?c ?d ?e ?f))
                          (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, ?F=3D3
STELLA(43):

Hans

>>>>> Hans Chalupsky <[email protected]> writes:

> 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 =

> consecutive:
>                           (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 =

> problem
> 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 =

>> Emmett:

>> Alf, Bert, Charlie, Doug, Ernie and Fred have their birthdays on =

>> consecutive 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 =

>> mutually 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 an=
d =

>> 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

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