Problem Description
This program is a rewrite of the
previous program to solve Kirkman's Schoolgirl problem and includes a search
all distinct solutions with discovery speed many
times faster that the original version.
Background & Techniques
The fascinating Kirkman's Schoolgirl problem asks for 7 arrangements of
15 girls so that they can walk in 5 groups of 3 each day for a week with no
girl in a group walking with another girl more than once. Since each girl
will be in a group with 2 other girls for each of 7 days, this means that
she will be paired with each of the other 14 girls exactly once.
Using a breadth first or depth first search of the "state space" for
solution of this problem is generally impractical because of the very large number of
possible arrangements to check. For such problems, various "heuristic" (from
Greek "discovery") techniques have been developed. A 2005 paper "A Simple and Efficient Tabu
Search Heuristics for Kirkman Schoolgirl Problem", (Dameng Deng, Jun Ma, and
Hao Shen), provided the inspiration for this Delphi program which can indeed
find all 7 distinct solutions in less than 60 seconds. The paper was
published by the Turku Center for Computer Science as TUCS Technical rReport
#704. It is quite readable as mathematical papers go, and is
currently (September, 2008) available online. .
Heuristics - Hill Climbing
A "state" describes a particular configuration of the board or puzzle being
investigated. In our case, a 7 particular arrangements of the 15 girls
defines a state. A "state space" is the set of all possible states for the
problem, a very large number for this problem. One of the heuristic
techniques for solving these problems when the space is too large to search
is called "Hill Climbing". We need some function that tells us how far we
are from the solution. It searches the neighborhood of a current states,
(the states we can reach from this state with a single move), and make the
move that takes us the largest step closer to the goal state. Hill climbing
is successful for many problems, but there are times when the method gets
stuck on top a "little hill" next to the mountain we want to climb, but we
cannot climb any higher without moving "downhill", further away from our
final goal.
In Kirkman's problem, our measure of distance to the solution is the
number of pairs of girls that end up walking together more than once during
the week under the current arrangement, we'll call it the "Conflict Score".
A "move" is defined as swapping the positions of a pair of girls within a
day and the desired moves are those which reduce the conflict score.
Heuristics II - Tabu Search
When
we reach the top of one of those "little hills" where no swap will reduce
the count further we need to expand the technique . At that point, the Tabu search kicks in and we'll make a
move that increases, or at least does not reduce the conflict score. The
"Tabu" part means that a particular pair swap for a particular day is
"taboo" (not allowed) for the next "Tabu tenure" moves. Tabu tenure is an
arbitrary number which depends on the nature of the problem and the
techniques used to choose the next move to be made. In this
implementation, 400 works well, the TUCS paper says they used 30, so clearly
their selection technique is different, and probably even better, than mine.
I was unable to track down the authors for more information.
The "Solution search" page of the program investigates finding solutions. Starting with
a random arrangement of girls for each day, solutions will be found at about
2 per second on most computers.
The 7 "Real" Solutions
The second part of the problem once we know how to find solutions rapidly,
is to identify the 7 distinct solutions, those which cannot be mapped into
another already identified solution by renaming the girls, rearranging the groups
within a day or rearranging order of the days. The "Search for unique
solutions" page accomplishes this in time which varies depending on the
random starting arrangement, but usually within few few minutes. The best "random seed" found so far finds the 7
unique solutions in under a minute after checking only 14 solved cases. The
uniqueness check uses only the first of the techniques described in the
paper "Solving the Kirkman’s Schoolgirl Problem in a Few Seconds",
(Nicolas Barnier and Pascal Brisset). When searching for a mapping that
converts a new solution to an existing unique solution, each pair of a
day in the new case must map to the same target day in the existing
unique case. This is a somewhat complicated piece of code
(meaning I wrote it a couple of years ago while "in the zone", but
can't really understand it now J). Perhaps
I'll add an option with extra output to help visualize the mapping
check process.
Addendum September 9, 2008: Version 3, posted today, adds a
4th tabbed page to the program to further investigate the algorithm which
searches for a mapping between two solutions. The mapping search
algorithm finds cases which are distinct much faster than it finds those
which map to each other because it takes advantage of the fact that each
pair of girls which are together on a day in Case1 , must map to the same
day in Case2. The first discrepancy found is enough to stop
checking that possible configuration of girls and move on the the next.
The algorithm used is presented in the Barnier and Brisset paper mentioned
above. In brief, it works like this:
- For each day of Case 2, start permuting the groups
within that day, There are 5! or 120 of these arrangements for
each day. (The algorithm starts with day 2 assuming
that both cases have been normalized.)
- For each of these arrangements, start permuting the girls within
their groups. There are 6 ways to arrange the three girls in their group
(ABC, ACB, BAC, BCA, CAB, and CBA). For the current arrangement of
5 groups there are 6x6x6x6x6 or 7,660 permutations to consider.
- For each of these 120 x 7,660 arrangements for that day, form a
trial mapping from of Case 1.
- With the trial map, check the target page for each pair of girls
within their groups for each of days 2 through 7 of Case 1.
Each pair within a day must map to the same day of Case 2 as every other
pair from that day. Note that is probably not the same day as
where they currently reside. The forst pait of girls that do not
map to the same page declares this mapping as invalid and the algorithm
can move back to step 1 for the next permutation.
- If step 4 ends without finding a mismatch, we have found the desired
mapping from Case1 to Case 2.
In the worst case, day 1 of Case 1 maps to the last permutation of day 7
of Case 2 over 300,000,000 pair comparison tests would have been made.
In practice the mapping, if one exists, is generally found to day 2 or 3
with "only" a few million comparisons.
The "Search for unique solution" page now has an option to save all
solutions found, unique of not, to a text file. These file may
be read into the "Checking Ismorphisms" page, and two cases selected for
checking. Case labels indicate existing mappings so it is easy to
select cases that will map to each other. When a mapping is found,
details of the mapping are displayed as well as other run statistics.
By the way, DFF library unit UCombV2 is used by Kirkman_Tabu and
for permuting groups is required to recompile. Download the
library zip file, DFFLibV11 or later to get access.
Addendum September 10, 2008: one more small update, making version
3.1, which adds a button to help find short solutions for the 7 unique
cases. the "Checking Isomorphisms" page also now shows the
reverse mapping from "normalized" back to "as read" versions of the cases
read.
November 23, 2012: A small cosmetic upgrade today to Version 3.2
which improves view-ability of the pages.
Running/Exploring the Program