Kirkman's Schoolgirl Problem

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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 

Suggestions for Further Explorations

Done! Sept 3, 2008 : The big one - identifying  isomorphic solutions as they  are being  developed.
The solution queue is actually used as a stack.  Perhaps using Delphi's TStack component would speed the search?   (I doubt it, but haven't checked.)

 

Original Date: July 10, 2004 

Modified: February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.