Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have covered the Backtracking Algorithm for Kirkman Schoolgirls Problem and compared with the Brute Force approach. We have presented the Time and Space Complexity for various cases.
Table of contents:
- Introduction
- Naive Approach
- Backtracking
- Time and Space Complexity
- Conclusion
Introduction
There are fifteen schoolgirls attending a boarding school who would like to walk in rows of three.
How can it be set up so that every student walks in a row with every other student exactly once a week? For example, lets set the girls names as Abigail, Bailey, Camila, Daisy, Elise, Faith, Gabrielle, Haley, Isabella, Jane, Katie, Laurel, Mabel, Nancy, Olivia. We will use the first letter of their names to represent them in this article.
There are 15! ways the schoolgirls can arrange themselves in a day.There are 15! ^ 5 ways to choose five daily configurations. An example of how the schoolgirls could arrange themselves in the first day.
A , B , C
D , E , F
G , H , I
J , K , L
M , N , O
However, arranging the schoolgirls from the second day onward will be more complicated. A, B, C, B, A, C and C, A, B are the same permutation. There are two main constraints that we can think of with regards to the arrangement problem. Firstly, the schoolgirl can only walk once per day. Secondly, there should be no repetition of the grouping in the week.
Naive Approach
In naive approach,the algorithm assign the schoolgirls without any reasoning and later tests whether it was a valid placement.
This can be significantly time consuming and highly inefficient. The backtracking method could be used to improve this.
Backtracking
Backtracking is a type of brute-force strategy that is used when there are several options to examine while solving a problem because we are unsure of the best option. Instead, we use the trial-and-error method to explore each option one at a time until the solution is found.
The method described above can be used to solve the Kirkman Schoolgirls problem.
The key distinction between brute-force and backtracking is that during backtracking, we only consider viable choices while developing the answer piece by piece.
STEPS:
-We start by assigning a schoolgirl to an empty list. The size is define as number of schoolgirls x days, in this problem it will be 15 * 5 = 75. Every schoolgirls will be assigned to an unassigned slot, a total of 75 slots will be filled.
-If all the slots are filled then a valid solution to the problem is obtained.
-We try to place every schoolgirls (represented by 0 to 14) in the uunassigned slot.
-Before placing we check for the constraints such as whether the schoolgirl had walk for the current day and we make use of adjacency table (15 x 15 matrix) to keep track of possible permuations.
-If any of the any of the constraint becomes false we will not assign that schoolgirls.
-If all the constraints are true then we'll will assign the schoolgirl and then repeat the process by assigning the next schoolgirl.
-If at any point none of the schoolgirls can be assigned then we've to backtrack and assign a new schoolgirl.
PSEUDOCODE:
solve(slot)
if(all slots are assigned)
  return true;
for(all available schoolgirls)
 try to assign one schoolgirl sg;
  if(solve(assign slot with schoolgirl sg) is true)
    return true;
  unassign schoolgirl sg;
return false;
Implementation
import numpy as np
class Kirkman:
def __init__(self):
'''
initialise our variable
1. week is 1-Dimensional array holding the schoolgirl walking position. 15 students x 5 days= 75
2. schoolgirl is 2-Dimensional array (adjacency table) 15 x 15 schoolgirls, this prevent same permutation being generated.
[A, B, C] is same as [C, A, B]
3. option is a list representing the 15 schoolgirls from A to O.
'''
self.week = np.empty(75, dtype=int)
self.week.fill(-1)
self.schoolgirl = np.zeros(shape=(15, 15), dtype=int)
self.option = list(map(chr, range(ord('A'), ord('O')+1)))
def print_solution(self):
'''
loop through our 1-D array week[] in steps of 3 to pretty print out the result
# '''
for i in range (0, 75, 3):
if i % 15 == 0 and i >0:
print ("-----")
print (f"{self.option[self.week[i]]} , {self.option[self.week[i+1]]} , {self.option[self.week[i+2]]}")
def can_place(self, pos, student):
'''
A utility function to check if a "student" can be placed in the given "pos" for each day of the week
1. Check if the student had walked for the day
if it exist in the week[day] position [day1 01-14, day2 15-29,..., day5 - 61-75]
need to determine which day
day 1 -> range (0,15)
day 5 -> range(60, 75)
day n -> range ([n-1] * 15, n * 15)
return false
2. Check if is the first person of each group (3 students per group, 5 groups per day, ). If yes, proceed to place student
3. Else Continue checking the adjacency table to ensure different permutation
'''
# 1. Check if the student had walked for the day
day = pos//15 + 1
for x in range((day-1)*15, day*15):
if self.week[x] == student:
return False
# Column 1 - check adjacency table to avoid permutation/repetition
if pos%3 == 1:
if self.schoolgirl[self.week[pos-1]][student] == 1 or self.schoolgirl[student][self.week[pos-1]] ==1:
return False
# Column 2 - check adjacency table to avoid permutation/repetition
if pos%3 == 2:
if self.schoolgirl[self.week[pos-2]][student] == 1 or self.schoolgirl[student][self.week[pos-2]] ==1:
return False
elif self.schoolgirl[self.week[pos-1]][student] == 1 or self.schoolgirl[student][self.week[pos-1]] ==1:
return False
# Column 0 - no adjacency table check
return True
def add_schoolgirl(self, pos, student):
'''
Function to Add to the solution - week[] and the adjacency table schoolgirl[][]
'''
self.week[pos] = student
if pos%3 == 0:
self.schoolgirl[student][student] = 1
elif pos%3 == 1:
self.schoolgirl[self.week[pos-1]][student] = 1
self.schoolgirl[student][self.week[pos-1]] = 1
elif pos%3 ==2:
self.schoolgirl[self.week[pos-2]][student] = 1
self.schoolgirl[student][self.week[pos-2]] = 1
self.schoolgirl[self.week[pos-1]][student] = 1
self.schoolgirl[student][self.week[pos-1]] = 1
def remove_schoolgirl(self, pos):
'''
Function to remove from the solution - week[] and the adjacency table schoolgirl[][]
'''
student = self.week[pos]
self.week[pos] = -1
if pos%3 == 0:
self.schoolgirl[student][student] = 0
elif pos%3 == 1:
self.schoolgirl[self.week[pos-1]][student] = 0
self.schoolgirl[student][self.week[pos-1]] = 0
elif pos%3 ==2:
self.schoolgirl[self.week[pos-2]][student] = 0
self.schoolgirl[student][self.week[pos-2]] = 0
self.schoolgirl[self.week[pos-1]][student] = 0
self.schoolgirl[student][self.week[pos-1]] = 0
def solve_kirkman(self, pos):
# base case: If all schoolgirls are placed
# then return true to avoid further backtracking
if pos >=len(self.week):
return True
for student in range(0, 15, 1):
# Check if we can place the student (0-14, where 0 is A and !4 is O) in the given slot (pos)
# if yes, we move to next slot (pos+1)
if self.can_place(pos, student):
#add the schoolgirl to the solution - week[]
self.add_schoolgirl(pos, student)
# recursive function call to place rest of the students on the next slot (pos+1)
if self.solve_kirkman(pos+1):
return True
# Backtracked and removing the assigned student
self.remove_schoolgirl(pos)
return False
# Driver Code
if __name__ =="__main__":
km = Kirkman()
if (km.solve_kirkman(0)):
km.print_solution()
else:
print("no solution exists ")
Output of solution:
A , B , C
D , E , F
G , H , I
J , K , L
M , N , O
-----
A , D , G
B , E , H
C , J , M
F , K , N
I , L , O
-----
A , E , I
B , D , J
C , F , O
G , K , M
H , L , N
-----
A , F , H
B , G , N
C , I , K
D , L , M
E , J , O
-----
A , J , N
B , K , O
C , D , H
E , G , L
F , I , M
Time and Space Complexity
Time Complexity:
For every unassigned slots there are M possibilites to explore and there are N unassigned slots in the Kirkman Schoolgirls problem. Therefore the backtracking algorithm takes O (N ^ M) time.
Space Complexity:
There are N function calls, therefore the space complexity would be O(N).
Conclusion
Other ways to solve Kirkman schoolgirls problem are using tools such as SAT Solvers and Inference Engines (example: Prolog Programming Language).
With this article at OpenGenus, you must have the complete idea of Backtracking Algorithm for Kirkman Schoolgirls problems.
