Esto es muy similar al Problema del Torneo Itinerante , que se trata de programar equipos de fútbol. En TTP, pueden encontrar la solución óptima hasta solo 8 equipos. Cualquiera que rompa un récord continuo de 10 o más equipos, tiene mucho más fácil ser publicado en una revista de investigación.

Es NP difícil y el truco es utilizar meta-heurística, como búsqueda tabu, recocido simulado,... en lugar de fuerza bruta o rama y atado.

Echa un vistazo mi implementación con Drools Planner (código abierto, java). Aquí están las restricciones, debería ser sencillo reemplazarlas con restricciones como Nadie juega 2 rondas sin un descanso.

Cada jugador debe jugar al menos n - 1 partidos donde n es el número de jugadores. Así que el mínimo de rondas es 2 (n-1) - 1, ya que cada jugador necesita descansar un partido. El mínimo también está limitado por(n (n-1))/2 partidos totales divididos por el número de pistas. Usando el más pequeño de estos dos le da la longitud de la solución óptima. Entonces es cuestión de llegar a una buena fórmula de estimación más baja ((número de partidos+restos restantes)/canchas) y ejecutar A* search.

Como Geoffrey dicho esto, creo que el problema es NP Duro, pero meta-heurística como A * es muy aplicable.

Solución Python:

import itertools

def subsets(items, count = None):
    if count is None:
        count = len(items)

    for idx in range(count + 1):
        for group in itertools.combinations(items, idx):
            yield frozenset(group)

def to_players(games):
    return [game[0] for game in games] + [game[1] for game in games]

def rounds(games, court_count):
    for round in subsets(games, court_count):
        players = to_players(round)
        if len(set(players)) == len(players):
            yield round

def is_canonical(player_count, games_played):
    played = [0] * player_count
    for players in games_played:
        for player in players:
            played[player] += 1

    return sorted(played) == played



def solve(court_count, player_count):
    courts = range(court_count)
    players = range(player_count)

    games = list( itertools.combinations(players, 2) )
    possible_rounds = list( rounds(games, court_count) )

    rounds_last = {}
    rounds_all = {}
    choices_last = {}
    choices_all = {}



    def update(target, choices, name, value, choice):
        try:
            current = target[name]
        except KeyError:
            target[name] = value
            choices[name] = choice
        else:
            if current > value:
                target[name] = value
                choices[name] = choice

    def solution(games_played, players, score, choice, last_players):
        games_played = frozenset(games_played)
        players = frozenset(players)

        choice = (choice, last_players)

        update(rounds_last.setdefault(games_played, {}), 
                choices_last.setdefault(games_played, {}), 
                players, score, choice)
        update(rounds_all, choices_all, games_played, score, choice)

    solution( [], [], 0, None, None)

    for games_played in subsets(games):
        if is_canonical(player_count, games_played):
            try:
                best = rounds_all[games_played]
            except KeyError:
                pass
            else:
                for next_round in possible_rounds:
                    next_games_played = games_played.union(next_round)

                    solution( 
                        next_games_played, to_players(next_round), best + 2,
                        next_round, [])

                for last_players, score in rounds_last[games_played].items():
                    for next_round in possible_rounds:
                        if not last_players.intersection( to_players(next_round) ):
                            next_games_played = games_played.union(next_round)
                            solution( next_games_played, to_players(next_round), score + 1,
                                    next_round, last_players)

    all_games = frozenset(games)


    print rounds_all[ all_games ]
    round, prev = choices_all[ frozenset(games) ]
    while all_games:
        print "X ", list(round)
        all_games = all_games - round
        if not all_games:
            break
        round, prev = choices_last[all_games][ frozenset(prev) ]

solve(2, 6)

Salida:

11
X  [(1, 2), (0, 3)]
X  [(4, 5)]
X  [(1, 3), (0, 2)]
X  []
X  [(0, 5), (1, 4)]
X  [(2, 3)]
X  [(1, 5), (0, 4)]
X  []
X  [(2, 5), (3, 4)]
X  [(0, 1)]
X  [(2, 4), (3, 5)]

Esto significa que tomará 11 rondas. La lista muestra los juegos que se jugarán en las rondas en orden inverso. (Aunque creo que el mismo horario funciona hacia adelante y hacia atrás.) Volveré y explicaré por qué tengo la oportunidad.

Obtiene respuestas incorrectas para una cancha, cinco jugadores.

Algunos pensamientos, tal vez una solución...

Ampliando el problema a los jugadores de X y las canchas de Y, creo que podemos decir con seguridad que cuando se nos da la opción, debemos seleccionar a los jugadores con el menor número de partidos completados, de lo contrario corremos el riesgo de terminar con un jugador que solo puede jugar cada dos semanas y terminamos con muchas semanas vacías en el medio. Imagina el caso con 20 jugadores y 3 canchas. Podemos ver que durante la ronda 1 los jugadores 1-6 se reúnen, luego en la ronda 2 los jugadores 7-12 se reúnen, y en la ronda 3 podríamos reutilizar a los jugadores 1-6 dejando a los jugadores 13-20 hasta más tarde. Por lo tanto, creo que nuestra solución no puede ser codiciosa y debe equilibrar a los jugadores.

Con esa suposición, aquí hay un primer intento de una solución:

 1. Create master-list of all matches ([12][13][14][15][16][23][24]...[45][56].)
 2. While (master-list > 0) {
 3.     Create sub-list containing only eligible players (eliminate all players who played the previous round.)
 4.     While (available-courts > 0) {
 5.         Select match from sub-list where player1.games_remaining plus player2.games_remaining is maximized.
 6.         Place selected match in next available court, and 
 7.         decrement available-courts.
 8.         Remove selected match from master-list.
 9.         Remove all matches that contain either player1 or player2 from sub-list.
10.     } Next available-court
11.     Print schedule for ++Round.
12. } Next master-list

No puedo probar que esto produzca un calendario con el menor número de rondas, pero debería estar cerca. El paso que puede causar problemas es #5 (seleccionar partido que maximiza las partidas restantes del jugador. Puedo imaginar que podría haber un caso en el que es mejor elegir una partida que casi maximiza 'games_remaining' para dejar más opciones en la siguiente ronda.

La salida de este algoritmo sería algo así como:

Round    Court1    Court2
  1       [12]      [34]
  2       [56]       --
  3       [13]      [24]
  4        --        --
  5       [15]      [26]
  6        --        --
  7       [35]      [46]
  .         .         .

Una inspección detallada mostrará que en la ronda 5, si el partido en Court2 hubiera sido [23], entonces el partido [46] podría haberse jugado durante la ronda 6. Eso, sin embargo, no garantiza que no habrá un problema similar en una ronda posterior.

Estoy trabajando en otra solución, pero eso tendrá que espera a más tarde.

No se si esto importa, los datos de ejemplo de "5 Jugadores y 2 Canchas" faltan otros tres partidos: [1,3], [2,4] y [3,5]. Basado en la instrucción: "Todo el mundo juega un partido contra todos los demás."