Problem Description
Here's is a problem commonly known as Kirkman's
Schoolgirl problem:
Fifteen young ladies of a school walk out
three abreast for seven days in succession: it is required to arrange them
daily so that no two shall walk abreast more than once.
Background & Techniques
This puzzle was proposed by English amateur mathematician Thomas
Penyngton Kirkman in 1850 in a popular magazine called "The Lady's
and Gentleman's Diary". There are 7 unique solutions and
Kirkman found them all. (Apparently none of the lady or gentleman
subscribers came up with a solution.) By unique
solutions, we mean solutions that cannot be transformed into one of the
other six by renaming the girls or by rearranging the rows or
days. By the way, the technical word for solutions which
can be so transformed is "isomorphic".
This is the toughest program I've tackled in a long time. It has
taken a couple of months of "spare" programming time to produce
the current version,. It solves the first part of the problem
(find a solution) finding about 60 solutions
per hour on my 2ghz Pentium 4 - with no attempt yet to solve the implied
2nd part (find the 7 unique solutions). I ran it for 7 1/2 hours and found
522 of the trillions of non-unique solutions that exist.
I suspect I've really only found one of the unique seven but I'll know
for
sure once I've solved the other half of the problem.
By the way, the number of ways to select the 35 groups of girls that
define a solution from the 455 possible groups is about 1027 - approximately
the diameter of the universe in inches!
Assume that the girls are named Anne, Barbara, Celia, Dorothy,
...., Nancy, and Opra so we can identify them by the first letters of
theirs names (A, B, C, D, ...N, O). The program lists solutions as
they are found and the search may be interrupted at any time. I also
added a button to save solutions to a text file for further study.
The best relevant
paper I've found on the web is "Solving the Kirkman's Schoolgirl
Problem in a Few Seconds" by Nicolas Barnier and Pascal
Brisset. It is relevant and probably very good
work, but not exactly easy reading for the amateur (me). I found it on the web a few weeks ago at but the site
seems to be down recently. Send me a note if interested and cannot locate it..
You can find a numeric form of the 7 solutions here.
Or my alpha translation of the same solutions here.
Notes for Programmers
The current version, which is named Kirkman1, is actually about
Kirkman7. The first several versions were attempts to establish
backtracking a two levels - one backing out groups of 3 girls when we
cannot find one meeting the criteria that they have not yet walked with each
other and that they have not already occurred in a row in today's set of
girls. The second level of backtracking would occur when
we have examined all combinations of girls for a particular day
without completing the day's set and must therefore back out
the entire day and try a different version of the previous day.
I finally gave up on that approach and implemented a more
straightforward version considering only groups of girls. I adapted
the depth first search technique from my Graph
Searching program posted some
time ago. In that simple case, we needed only to identify nodes that
had already been visited and the goal state was known. In the
current problem, things are not quite so simple. We do not
know the goal state in advance and there are additional criteria for
valid "next" nodes.
I defined the 455 possible groupings of girls as the nodes to be
searched (455 is the number of ways to select combinations of 3 girls from a
population of 15). As in the Graph Traverse program, each
group has an associated adjacency list of possible next nodes. These
are all defined in an TGroup object class - one instance for
each triplet of girls.
When selecting groups, we need additional criteria beyond having not
previously visited them - they must also not contain two girls that have
already walked together. A 15 x 15 Boolean array, Pairs, identifies
this condition. Procedures UpdatePairs and Undopairs
update (and undo updates) for groups being added or removed from the trial
solution being developed.
In addition, I adopted the
conventions recommended in the Barnier/Brisset paper referenced
above. Letters within groups are in alphabetical order, the
rows for each day are maintained in lexicographical order, the first day
always contains the rows [ABC, DEF, GHI, JKL, MNO] in that order,
the first group of the second day is fixed as ADG.
Because of these constraints, we need to identify the groups which start a
new day and select from the remaining unused groups that start with
"A" as the first row of a day. Since we never need to revisit them, the groups
of the fixed first row are not maintained in the queue of nodes in the
current solution, we just mark them initially as visited in the Visited
array and set all pairs to true in the Pairs
array.
The search proceeds by adding groups by the above criteria,
backtracking whenever we run out of adjacent nodes to try. A
solution is found when we have 30 groups representing 6 days in the queue (these
plus the fixed first row define the 7 days of a solution).
Now - on to the uniqueness part!
Addendum September 3, 2008:
Program Kirkman_Tabu was posted today
which uses a new search technique and finds solutions much faster than
this version. It finds the 7 distinct solutions in less than a
minute!
Running/Exploring the Program
