A Software Solution to the Unsol

In this paper, we explore the mathematical problem behind creating a proper schedule for a bowling tournament. Then, we discuss the implementation of a system with a graphical user interface that uses a brute force method to generate the schedule.

In a bowling tournament, several teams participate and compete against each other in groups of two or more. In such a tournament, we want to make sure that each team bowls against as many teams as possible without repeat, and more importantly, each team bowls in every round of the tournament. We can accomplish this by reshuffling the group in each round in such a way that no two teams will belong to the same group more than once and each team belongs to at least one group in each round. Table 1 shows a tentative schedule for 16 teams, labeled T1 through T16. In this schedule, for example, T1 is grouped with T2, T3, and T4 in round 0. Hence, in the subsequent four rounds, T1 is never grouped again with T2, T3, or T4. This approach applies to every team.

Some mathematics reveals that it is easy to create such a schedule when teams are grouped in two! However, an attempt to create such a schedule by hand when teams are to be grouped by more than two reveals that it is not an easy task! In this paper, we present this problem in mathematical terms, explore the related mathematical field, and discuss the design of the Graphical User Interface (GUI) enabled software that uses a brute force method to create such schedules.

Games	Group 0	Group 1	Group 2	Group 3
Round 0	T1,T2,T3,T4	T5,T6,T7,T8	T9,T10,T11,T12	T13,T14,T15,T16
Round 1	T1,T5,T9,T13	T2,T6,T10,T14	T3,T7,T11,T15	T4,T8,T12,T16
Round 2	T1,T6,T11,T16	T2,T5,T12,T15	T3,T8,T9,T14	T4,T7,T10,T13
Round 3	T1,T7,T12,T14	T2,T8,T11,T13	T3,T5,T10,T16	T4,T6,T9,T15
Round 4	T1,T8,T10,T15	T2,T7,T9,T16	T3,T6,T12,T13	T4,T5,T11,T14

Suppose we partition set A of n objects into subsets of size k >2, where

. Let us denote the

partition by

and the

subset within the partition

. Then,

First, we are interested in the maximum number of partitions that can be obtained such that

Secondly, we are interested in how such partitions can be obtained for large n and

. Example 1 shows the computation of such partitions for

and

Example 1: Suppose we have

and we partition

into subsets of size 3. Then, partition 0,

We depict the results from example 1 using a graph in Figure 1. We represent n objects as vertices of the graph. An edge exists between two vertices if and only if they belong to the same subset. Furthermore, two edges have the same color if and only if the edges belong to the same partition. The edges belonging to partitions

, and

are colored in green, blue, red, and purple respectively.

Figure SEQ Figure \* ARABIC 1: A graph theoretic representation of the partitions of a set containing 9 elements.

Although graph theory provides excellent method of visualizing the solution for smaller n, the visualization becomes increasing complex with larger values of m and n. Moreover, graph theory does not provide us with tools to generate such a solution. Thus, we explore the area of combinatorial design theory which concerns questions about whether it is possible to arrange elements of a finite set into subsets so that certain 'balance' properties are satisfied [1].

Definition 1: A design is a pair

such that the following properties are satisfied:

The word design is used due to the origin of the problem in the experimental design. One of the most important types of design is called balanced incomplete block design which we define below.

Definition 2: Let v, k, and

be positive integers such that

. A -balanced incomplete block design (BIBD) is a design

such that the following properties are satisfied:

The constraint as described in line 3 of the definition is called the 'balance' property. For all the cases that we consider in this paper,

because any pair of teams belong to a group (block) only once throughout the tournament. As teams are grouped by four in a bowling tournament, we are primarily concerned with cases where

. Although BIBD captures most of the conditions of our problem, it fails to capture one vital condition, i.e., there should be at least one set of blocks whose union should contain all the teams participating in the tournament. This condition, which allows us to construct round(s) of games from blocks, is captured by a resolvable BIBD which we define below.

Definition 3: Suppose

is a -BIBD. A parallel class in

is a subset of disjoint blocks from

whose union is X. A partition of

into r parallel classes is called a resolution, and

is said to be a resolvable BIBD if

has at least one resolution [1]. Such partition is possible only when

Example 2: The design shown in table 1 is a

. Moreover, this BIBD is resolvable because we are able to obtain five different resolutions, i.e. five different rounds of games.

Remark 1: Assuming

, cases where

is equal to 4, 8 and 12 are trivial cases since the maximum number of blocks that can be constructed is 1,2, and 3 respectively. Hence, only one resolution is possible in each case.

Remark 2: Assuming

, be cautioned that our problem is a resolvable BIBD for only certain values of

. For instance, when

or when n=28, every possible pair of teams appear in the block and hence is a case of BIBD (by definition 3). However, when

, every possible pair of teams does not appear in the block and hence is not the case of BIBD.

In some 'nice' cases of BIBD, where each team appears for equal number of times, we calculate the number of blocks (r) in which each team appears as follows:

For a resolvable BIBD, each team appears in a resolution at most once. Hence the number of resolutions (e) possible to construct is smaller or equal to the number of blocks in which each team appears. Mathematically,

Next, the total number of blocks (b) that can be constructed is given by the following relation:

Hence, each team appears in the schedule five times. From the above calculation, we also conclude that

Hence, the number of blocks possible to construct is 20. In this case, every block can be used to construct resolution. Therefore, it is possible to construct five resolutions (i.e. five rounds of games).

The problem presented here is popularly known as Social Golfer Problem. In general, it is an unsolved problem in mathematics. No analytic method exists for computing the maximum number of blocks and resolutions for any n, k, and

Due to the nature of the mathematical problem, no algorithm exists to generate a schedule for n teams grouped by k teams [2]. However, the solution to the problem entails a high degree of symmetry, the exploitation of which makes it easier to generate the solutions. In all the subsequent discussions, we assume

and

. In this section, we show how one can generate the schedule for the tournament with 16 teams using example 4. We use the variations of the techniques used in this example to generate schedules when n equals 20, 24, 28, 32, 36, 40, 44, and 48.

Round 1: We obtain group (subset) 0 by taking the team in position 0 from each group in round (partition) 0. Likewise, we obtain group 1 by taking the team in position 1 of each group in the round 0 and so on. In general, the

group of round 1 is generated by taking the

team from each group of round 0. Thus, round 1 of the tournament is given by the partition,

Round 2: We create each group for round 2 by taking elements in positions

and

of subsets

, and

respectively. To construct group 0 and group 2, we compute the position,

, as follows:

Similarly, to construct group 1 and group 3, we compute the position,

, as follows:

Round 3: We obtain each group of round 3 by taking elements in positions

, and

of subsets

, and

respectively. To construct group 0 and group 2, we compute the position,

, as follows:

Similarly, to construct group 1 and group 3, we compute the position,

, as follows:

Round 4: We obtain each group of round 4 by taking elements in positions

, and

of subsets

, and

respectively. To construct group 0 and group 2, we compute the position,

, as follows:

Similarly, to construct group 1 and group 3, we compute the position,

, as follows:

Games	Group 0	Group 1	Group 2	Group 3
Round 0	1, 2, 3, 4	5, 6, 7, 8	9, 10, 11, 12	13, 14, 15, 16
Round 1	1, 5, 9, 13	2, 6, 10, 14	3, 7, 11, 15	4, 8, 12, 16
Round 2	1, 6, 11, 16	2, 5, 12, 15	3, 8, 9, 14	4, 7, 10, 13
Round 3	1, 7, 12, 14	2, 8, 11, 13	3, 5, 10, 16	4, 6, 9, 15
Round 4	1, 8, 10, 15	2, 7, 9, 16	3, 6, 12, 13	4, 5, 11, 14

Table 3 shows the number of rounds we obtained for the different numbers of teams. The highest number of rounds possible is 9, and it occurs when

. We computed schedule for each n in table 3 and hard coded the solution in the software.

Table SEQ Table \* ARABIC 3: Number of rounds obtained for different values of n

No of Teams (n) =	No of rounds (e) =
4	1
8	1
12	1
16	5
20	5
24	6
28	7
32	9
36	6
40	5
44	5
48	5

We designed and implemented the software application titled 'McKendree Schedule Maker' using the object-oriented paradigm. The design contains the following main classes, whose purposes we describe below in the context of their functionality and interaction:

The MainForm is the main class. It is responsible for orchestrating other classes. The NewScheduleDialog class collects information necessary to generate a new schedule from the user. Inside the NewScheduleDialog class, an instance of the class NewScheduleInputData is instantiated with the user provided information and passed to class MainForm by reference. The NewScheduleInputData class provides necessary data structure to hold all the information required to create a new schedule. The user provided information is then passed by reference from MainForm to ScheduleDisplayInternalForm, which is responsible for formatting and displaying the schedule in a table inside the internal frame. ScheduleDisplayInternalForm first uses ManipulateSchedule class to obtain the schedule for the given number of teams and rounds of games. The class ManipulateSchedule contains pre-computed schedule for those cases where number of teams is a positive multiple of four less than 48. We first compute the lowest multiple of four that is greater than or equal to the user-specified number of teams and consider the schedule corresponding to that multiple of four as a base schedule. If the number of rounds required is more than the rounds available in the base schedule then, we generate additional rounds while minimizing the number of times a pair of teams are grouped together. Next, if the user-specified number of teams is not a multiple of four, then we get rid of the extra teams from the base schedule. We also randomly reshuffle teams within the group so that they are not always on the same side of other teams in a bowling alley. Moreover, we reshuffle groups within each round of the tournament so that a group does not belong to the same bowling alley each time. The final schedule is passed to the ScheduleDisplayInternalForm which converts the schedule into formatted string and displays it in a table along with the index table.

The class FileActivity provides with facility to browse the filesystem so that the user can choose the location and filename to save or load a schedule. Once the user chooses the filename and location to open the file, The FileActivity class returns the name and location of the file to the class ScheuduleDisplayInternalFrame which then formats and displays the schedule. Similarly, once the user chooses the filename and location to save the schedule, the FileActivity class returns this information to ScheduleDisplayInternalFrame, which then writes the schedule to the specific file in the specific location. Additionally, ScheduleDisplayInternalFrame also generates the HTML code for the schedule being displayed and allows the user to save the HTML file in one�s chosen location. Furthermore, it provides the HTML file location to the class OpenInternetBrowser which then launches a default web browser with the HTML file displayed in it. The application also maintains the database of all the team names in a league. The class ManipulateTeam enables the user to add or remove a team permanently from the database. We summarize the functionality described in this section using a data flow diagram in figure 2. We present the Unified Modeling Language (UML) class diagram for these main classes in figure 3.

Figure SEQ Figure \* ARABIC 2: Data Flow Diagram for the McKendree Schedule Maker

A user-friendly graphical interface is an integral part of this software. The main display frame consists of a menu, a toolbar and a display pane where the user opens one or more schedule for display; however, only one of them is in focus or activated at any given time. The menu bar contains drop-down menus, namely File, Action, and Help. File consists of menu items that enable the user to create a new schedule, open a saved schedule, save a schedule, save schedule with a new filename, close a schedule and exit the application. Likewise, Action consists of facilities to add a team to the database of teams or remove a team from it, generate a web page, print the schedule, and also e-mail it. Note that the printing and e-mailing facilities are disabled in the first release of the software. Finally, the Help menu consists of menu items to access information about the software, its creator and to look up help topics. The user can also access most of these functionalities by using the buttons on the toolbar situated below the menu bar. Figure 4 shows the screen shot of the application.

The user can either create a completely new schedule by using a form shown in figure 5 or load a saved schedule from a file. This form also makes sure that the user selects the exact number of teams that one wishes to select.

The application displays each schedule in an internal window on the display pane of the main window as shown in figure 4. The user can close or minimize these internal windows individually. Inside the internal window, it displays the schedule in a table using numerical indices for participating teams. In the next table below the schedule, it displays names of the participating teams alongside their corresponding indices. The user can change the team that has been assigned to specific numerical index by double clicking on the team name and selecting different name from the list of teams participating in the tournament. Moreover, for portability and printing, one can generate the HTML code for the schedule with a single click. The application also prompts the user to save the webpage in a desired location and automatically displays it in a default browser. Figure 6 shows the webpage generated by the application.

The user can also add or remove team(s) from the database which contains names of more than 260 teams belonging to a league by using the form shown in figure 7.

To guide the new users through the application, it contains hyperlinked help pages which can be launched in a web browser using a single click. Figure 8 shows the help main topic page.

In this paper, we presented the unsolved mathematics behind bowling tournament scheduling. We showed how the maximum number of rounds for a tournament can be calculated for some cases, and how symmetry of the problem can be exploited to generate the solution by brute force. Finally, we presented the software implementation of the solution. We expect the resulting software to ease the burden of creating an efficient bowling schedule for the bowling tournament organizers.

[1] Stinson, Douglas R. Combinatorial Designs Construction and Analysis. New York : Springer- Verlag,

[2] Colbourn, C.J and J, Colbourn M. Algorithms in Combinatorial Design Theory. Amsterdam : Elsevier

[3] Pless, Vera. Introduction to the Theory of Error-Correcting Codes. New York : John Wiley & Sons,

[4] Pressman, Roger S. Software Engineering: A Practitioner's Approach. New York : McGraw-Hill, 2005.

[5] Buckley, Fred and Lewinter, Marty. A Friendly Introduction to Graph Theory. New York : Prentice