Re: Famoue problem by Eric Emmett
Hans Chalupsky <[email protected]> Mon, 12 Sep 2011 18:01:59 -0700
| Newsgroups | gmane.comp.ai.powerloom |
|---|---|
| Message-ID | <[email protected]> |
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 PowerLoo=
m.
> 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 cons=
ecutive:
> (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 on=
ly
> the birthday differences but also their relative order as given in the pr=
oblem
> 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 Emme=
tt:
=
>> Alf, Bert, Charlie, Doug, Ernie and Fred have their birthdays on consecu=
tive 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 mutual=
ly 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