Golf Problem

Prologers might find this problem, originating in the sci.math
newsgroup, both appropriate and challenging:

You do not need to be a golfer to help with my problem.

I am arranging a competition for 12 players (say A through L)
over 5 days. Each day 3 groups of 4 will play. Day one could
be A+B v C+D, E+F v G+H and I+J v K+L (Easy so far!). The
problem is that I cannot make the 15 groups (3x5) such that:

Every player plays in a group with ever other player during
the 5 days at least once and ideally not more than twice.

No player partners any other player more than once. eg If A+B
v C+D is a group then another group of A+B v E+K is not
acceptable but A+E v B+K is.

Each player tees off in the first group at least once but no
more than twice over the 5 days.

After hours of looking for patterns and juggling with letters
I have not found a solution but have been so near that I am
convinced that it is mathematically possible.
A real mathematician might find this easy but I am a chemist!

No useful replies were forthcoming in the sci.math newsgroup!

--
Mail sent to this email address is automatically deleted
(unread) on the server. Send replies to the newsgroup.

Nameless wrote:
>
>     Every player plays in a group with ever other player during
>     the 5 days at least once and ideally not more than twice.
>

I'm not sure that even this requirement can be fulfilled. I quick
translation to Prolog up to here:

group(G) :-
G = gr(pair(P1,P2),pair(P3,P4)).


groups([]).
groups([G|Gs]) :-
group(G),
groups(Gs).

day(D) :-
D = day(Gr1,Gr2,Gr3),
groups([Gr1,Gr2,Gr3]).

days([]).
days([D|Ds]) :-
day(D),
days(Ds).

choosetwo([X|Xs],(X,Y)) :-
member(Y,Xs).
choosetwo([_,X|Xs],Two) :-
choosetwo([X|Xs],Two).

group_day(Gr1,day(Gr1,_,_)).
group_day(Gr2,day(_,Gr2,_)).
group_day(Gr3,day(_,_,Gr3)).

twoinanygroup((T1,T2),Day) :-
group_day(Group,Day),
Group = gr(pair(P1,P2),pair(P3,P4)),
Players = [P1,P2,P3,P4],
member(T1,Players),
member(T2,Players).


twosplayingroup([],_).
twosplayingroup([Two|Twos],Ds) :-
member(Day,Ds),
twoinanygroup(Two,Day),
twosplayingroup(Twos,Ds).


tournament(Ds) :-
Ds = [D1,D2,D3,D4,D5],
days(Ds),
Players = [1,2,3,4,5,6,7,8,9,10,11,12],
 findall(Two,choosetwo(Players,Two),Twos)
,
twosplayingroup(Twos,Ds).


I'm unable to find any solution for tournament(Ds) even after waiting
for several minutes. Maybe someone can recommend a different search
strategy or prove that this requirement can or cannot be fulfilled?


Best regards,
Markus.

Nameless wrote:
> Prologers might find this problem, originating in the sci.math
> newsgroup, both appropriate and challenging:
>
>     You do not need to be a golfer to help with my problem.
>
>     I am arranging a competition for 12 players (say A through L)
>     over 5 days. Each day 3 groups of 4 will play. Day one could
>     be A+B v C+D, E+F v G+H and I+J v K+L (Easy so far!). The
>     problem is that I cannot make the 15 groups (3x5) such that:
>
>     Every player plays in a group with ever other player during
>     the 5 days at least once and ideally not more than twice.
>
>     No player partners any other player more than once. eg If A+B
>     v C+D is a group then another group of A+B v E+K is not
>     acceptable but A+E v B+K is.
>
>     Each player tees off in the first group at least once but no
>     more than twice over the 5 days.
>
>     After hours of looking for patterns and juggling with letters
>     I have not found a solution but have been so near that I am
>     convinced that it is mathematically possible.
>     A real mathematician might find this easy but I am a chemist!
>
> No useful replies were forthcoming in the sci.math newsgroup!
>

Aha, Daniel is back :-)

The above (at least superficially) looks like the social golfer problem.
Here are some related references:

www.recherche.enac.fr/opti/papers/articles/golf.ps.gz

http://www.icparc.ic.ac.uk/eclipse/appl/index.html (there is a paper
about scheduling tournaments - I didn't pursue it)

http://www.icparc.ic.ac.uk/eclipse/...es/golf.ecl.txt

Maybe the last one is what people interested in the problem should have
a look at.

ECLiPSe used to have a webpage with the "solved" golfer problems - this
is maybe just vague memory - I can't find it anymore - maybe someone
from ECLiPSe can comment ?

Cheers

Bart Demoen

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1104262941.464412@seven.kulnet.kuleuven.ac.be...
> Nameless wrote: 
>
> Aha, Daniel is back :-)

Wrong--again! Maybe you should limit yourself to three
guesses, with just one more remaining. :)

--
Mail sent to this email address is automatically deleted
(unread) on the server. Send replies to the newsgroup.

Nameless wrote:
> "Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
> news:1104262941.464412@seven.kulnet.kuleuven.ac.be...
> 
>
>
> Wrong--again! Maybe you should limit yourself to three
> guesses, with just one more remaining. :)
>

I am no guessing: in this newsgroup, the failure to prove that you are
someone else than Daniel, is common cause for assuming that you are.

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1104272966.434764@seven.kulnet.kuleuven.ac.be...
> Nameless wrote: 
>
> I am no guessing: in this newsgroup, the failure to prove that
> you are someone else than Daniel, is common cause for assuming
> that you are.

Yer, in your fantasy! Dream on... any burden of proof must
necessarily fall on you, I choose to keep my anonymity.
Besides, as the newsgroup administrator, you should know
that this is off-topic. :(

--
Mail sent to this email address is automatically deleted
(unread) on the server. Send replies to the newsgroup.

Nameless wrote:
> Besides, as the newsgroup administrator, you should know
> that this is off-topic. :(

After all these years in comp.lang.prolog, you should know that
there is no newsgroup administrator here !

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1104307207.572610@seven.kulnet.kuleuven.ac.be...
> Nameless wrote: 
>
> After all these years in comp.lang.prolog, you should know
> that there is no newsgroup administrator here !

Well, since you've relegated the conversation to off-topic
status anyway, two of Aesop's Fables come to mind...

Once upon a time a Wolf was lapping at a spring on a
hillside, when, looking up, what should he see but a Lamb
just beginning to drink a little lower down. 'There's my
supper,' thought he, 'if only I can find some excuse to
seize it.' Then he called out to the Lamb, 'How dare you
muddle the water from which I am drinking?'
Nay, master, nay,' said Lambikin; 'if the water be
muddy up there, I cannot be the cause of it, for it runs
down from you to me.'
'Well, then,' said the Wolf, 'why did you call me bad
names this time last year?'
'That cannot be,' said the Lamb; 'I am only six months
old.'
'I don't care,' snarled the Wolf; 'if it was not you it
was your father;' and with that he rushed upon the poor
little Lamb and WARRA WARRA WARRA WARRA WARRA ate her all
up. But before she died she gasped out 'Any excuse will
serve a tyrant.'

- The Wolf and the Lamb

One fine day two Crabs came out from their home to take
a stroll on the sand. 'Child,' said the mother, 'you are
walking very ungracefully. You should accustom yourself, to
walking straight forward without twisting from side to side.'
'Pray, mother,' said the young one, 'do but set the
example yourself, and I will follow you.'
Example is the best precept.

- The Two Crabs

--
Mail sent to this email address is automatically deleted
(unread) on the server. Send replies to the newsgroup.

Mats wrote:

> Problems of this kind lend themselves very naturally to a constraint
> programming formulation.  Using the SICStus library(clpfd), the
> following schedule was found in a few milliseconds:

Could you please provide details of your implementation? I also tried a
constraint formulation, for example:

twoinanygroup((T1,T2),Day) :-
group_day(Group,Day),
Group = gr(pair(P1,P2),pair(P3,P4)),
( P1 #= T1 #\/ P2 #= T1 #\/ P3 #= T1 #\/ P4 #= T1 ),
( P1 #= T2 #\/ P2 #= T2 #\/ P3 #= T2 #\/ P4 #= T2 ).

but it does not improve running time considerably. I'm therefore curious
about how you went about formulating for example the "each player with
every other in some group"-constraint.

Best regards,
Markus.

> I'm therefore curious
> about how you went about formulating for example the "each player
> [plays] with every other in some group"-constraint.

The general idea is to form the multiset of all pairs of players that
occur in the groups, and to constrain that multiset to contain every
feasible pair of players.

I prefer to wait a few days before posting the source code, to
encourage others to have a try.
--Mats