In 1850, Kirkman posed the following problem, which relates to a BIBD (Balanced Incomplete Block Design) problem in mathematics.
How 15 school girls can walk in 5 rows of 3 each for 7 days so that no girl walks with any other girl in the same triplet more than once.
The following program finds the arrangement.
kirkman(Groups) :- (arrange(35, Groups) -<> cont) -<> gen_res(15).gen_res(0) :- cont. gen_res(N) :- N > 0, (g(N),g(N),g(N),g(N),g(N),g(N),g(N)) -<> gen_res(1, N).
gen_res(N, N) :- N1 is N-1, gen_res(N1). gen_res(I, N) :- I < N, I1 is I+1, meet(I, N) -<> gen_res(I1, N).
arrange(0, []). arrange(I, [[G1,G2,G3]|Groups]) :- I > 0, g(G1), g(G2), g(G3), meet(G1, G2), meet(G1, G3), meet(G2, G3), I1 is I-1, arrange(I1, Groups).
This program works as follows.
gen_res
creates resources of seven g(i)'s for
each i=1..15 and meet(i,j) for each i=1..14, j=(i+1)..15.
Seven g(i)'s correspond to seven attendances of i-th girl.
Resource meet(i,j) corresponds to each pair of girls.gen_res
calls a goal cont,
which calls the goal
arrange(35, Groups) because cont is a rule-type resource.arrange
finds 35 groups, so that
each group consists of three girls,
each girl appears in seven groups, and
any pair of girls is included in exactly one group.