next up previous
Next: Cryptarithmetic Puzzles Up: EXAMPLES Previous: Knight Tour

Kirkman's School Girl Problem

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.

  1. 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.
  2. Then, gen_res calls a goal cont, which calls the goal arrange(35, Groups) because cont is a rule-type resource.
  3. 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.


Naoyuki Tamura
Thu May 8 20:39:01 JST 1997