Planning team play

by Richard A. DeVenezia, back to round robin

I call this a social square, and first encountered the problem from an entry in the guestbook. If you know a more mathematical or formal name, please let me know.

This analysis was a dead-end but did lead to an algorithm for squares of primes.

Problem

Plan a schedule for M teams of M players. In each round all M teams will play. M+1 rounds will be played. The schedule must satisfy this criteria, No player is paired with another player more than once. In other words, each player is paired with each other player only once. This is why I use the term social.

N = M x M. What if you have N players and N is slightly less than a square ?
Plan for N^*=N+G players, where G is the number of ghost players. Some teams will have more players than others.

What if you have N players and N is slightly more than a square ?
Plan for N^*=N-X players, where X is the number of excess players. In the first round, put X players on standby. In subsequent rounds randomly replace X players with those on standby. Some players will play more (or less) than other players.

Possible solution?

Not being of good analytical mood, I look to brute force. All possible teams are enumerated as T, and combinations of elements of T are evaluated for meeting the scheduling criteria. Not smartest, not swiftest, works for squares of 1, 2, 3, and 4. Squares of 5 and 6 failed, didn't try 7... too many combinations.

Brute force exhaustive searches of a combination space don't scale well. I call such approaches the bulldozer method. However, the few solutions found gave the opportunity to look for patterns, which led to a generator.

Label the players as 1,2,3,...,N. For M <=5 N is <=25, which is suitable for labeling players with letters of the alphabet A,B,C,...

I will explain using letters, but the program uses numbers (which can easily be mapped to letters if need be). Round 1 is always the list of players.

A schedule for 9 (=3x3) teams in rounds 2 to 4 has to be searched for out of 27 (=3^3) possible teams created by combining 3 players at a time. In general, M*M teams have to be selected from M^M possible team combinations. Here is the enumeration for M=3.

ADG
  H
  I
 EG
  H
  I
 FG
  H
  I

BDG
  H
  I
 EG
  H
  I
 FG
  H
  I

CDG
  H
  I
 EG
  H
  I
 FG
  H
  I

Further prepare the groundwork; let the initial search state be represented as such:

From here you can get a feel on what the search has to do. Note that for Team 1, candidates come for column 1 of enumeration, for team 2 column 2, etc.

Set the candidate cell, proceeding top to bottom, left to right. The cell can be referenced as (row,col). Select the first team combination from the enumeration column col. If the candidate selection passes the criteria test proceed to the next column; if not proceed to the next candidate in the enumeration column that would pass the test that just failed. When at the last column proceed to first column of next row. When at last column of last row the plan is complete. If the next candidate exceeds the current enumeration column, the algorithm has failed to find a plan. When the algorithm fails, you need to find a new algorithm or analysis that would prove such an algorithm is findable (meaning you can prove a plan for square N exists).

"If the candidate selection passes the criteria test"

That's a pretty broad statement, what does it mean?

For each player in the candidate team these things have to be satisfied:
- No player can be already present in a row (they can only be on one team at a time in a round)
- No pair of players can be already present in any prior team planned (the social criteria)

Show me