Re: Famoue problem by Eric Emmett
Hans Chalupsky <[email protected]> Tue, 13 Sep 2011 16:42:48 -0700
| Newsgroups | gmane.comp.ai.powerloom |
|---|---|
| Message-ID | <[email protected]> |
Well, yes and no. The first thing we can do is to introduce a definition f=
or
a birthday type, i.e., the set of values that could occupy the value of a
birthday-of relation:
(defconcept birthday (?x)
:<=3D> (and (integer ?x)
(member-of ?x (setof 1 2 3 4 5 6 7))))
(the INTEGER-INTERVAL class you found is a native STELLA class that isn't
really axiomatized and probably should go away to not confuse people).
The next thing one might do is to introduce a person class and a birthday-of
relation that maps a person onto his birthday:
(defconcept person (?x)
:<=3D> (member-of ?x (setof Alf Bert Charlie Doug Ernie Fred)))
(deffunction birthday-of ((?x person) (?y birthday)))
Now we would want to model constraints in terms of this relation. For
example,
(assert (=3D> (and (birthday-of Alf ?a)
(birthday-of Doug ?d)
(birthday-of Fred ?f))
(and (=3D (- ?d ?f) (- ?a ?d))
(< ?f ?d)
(< ?d ?a))))
or, turning that around,
(assert (=3D> (and (birthday-of Alf ?a)
(birthday-of Doug ?d)
(=3D (- ?d ?f) (- ?a ?d))
(< ?f ?d)
(< ?d ?a))
(birthday-of Fred ?f)))
The problem is that the solution to the puzzle is a set of values that obeys
some inter-value constraints as described by these rules plus also some who=
le set
constraints. So it can't really be naturally described with rules concludi=
ng
`(birthday-of ?x ?y)' without those rules looking at all other values at the
same time. Additionally, these rules would need to do some hypothetical
reasoning to work, since we don't know what Alf's or Doug's birthdays are.
So, the only way to model this I can see is at the set level which is simil=
ar
to the query posted before but by encapsulating some of the machinery in
relations. For example:
(defrelation consecutive-birthdays ((?x COLLECTION))
;; This relation tests whether an unordered list of birthdays can be
;; sorted into a set of consecutive integer values:
:<=3D> (exists (?n ?set ?min ?max)
(and (length-of-list ?x ?n)
(collect-into-set ?x ?set)
(cardinality ?set ?n) ;; there were no duplicates
(minimum-value ?set ?min)
(maximum-value ?set ?max)
(- ?max ?min (- ?n 1))))
:closed TRUE)
Now we can define valid puzzle solutions like this using some of the relati=
ons
defined above:
(defrelation birthday-puzzle (?a ?b ?c ?d ?e ?f)
:<=3D (and (birthday ?a)
(birthday ?b)
(birthday ?c)
(birthday ?d)
(birthday ?e)
(birthday ?f)
(bound-variables)
(=3D (- ?d ?f) (- ?a ?d))
(< ?f ?d)
(< ?d ?a)
(=3D (- ?f ?c) (- ?b ?f))
(< ?c ?f)
(< ?f ?b)
(=3D ?e 6)
(consecutive-birthdays (listof ?a ?b ?c ?d ?e ?f))))
|=3D (retrieve all (birthday-puzzle ?a ?b ?c ?d ?e ?f))
There is 1 solution:
#1: ?A=3D7, ?B=3D4, ?C=3D2, ?D=3D5, ?E=3D6, ?F=3D3
If there is a different more "natural" way to describe this, I'd be interes=
ted
to hear about it.
Hans
>>>>> Robert Onslow <[email protected]> writes:
> 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 birthday=
s =
> 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 ou=
t.
>> 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 Institu=
te
>> 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 Fre=
d=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 a=
nd =
>>> 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 =
> _______________________________________________
> powerloom-forum mailing list
> [email protected]
> http://mailman.isi.edu/mailman/listinfo/powerloom-forum