ダブルスの試合を2コートでまわすときにプレイヤーの重複のない組み合わせを探す

問題設定

ダブルスの試合をたくさんやることになりました。試合組はすでに決まっています。
2面を使って試合をし、2つとも終わった段階で次の2試合を始める方式とします。これを1ターンと呼びます。
全部で20試合あるので理論上10ターンで終わるはずです。しかし、当然1人が同一ターンの2試合に出ることはできません。
これを解消する必要がありますが、適当に組んでたらどうにもうまくいかなかったのでプログラムを書くことになりました。

制約

• 試合ごとにかかる時間は一定ではないので、長い時間がかかる試合と短い時間がかかる試合が同じターンにあるとロスが大きいのですが、ここではかかる時間は一定であるとします
• 連続した試合は当然避けたいものですが、この後のステップでターンごとに並び替えればよいのでここでは気にしないことにします

解法

games は Hash{Integer => Array<String>} で試合IDとプレイヤー名の配列が入っているものとします。
出力はなんでもいいのですが spreadsheet に食わせるので1ターンごとに1行で id_1,id_2 というCSV形式にしました。

方針自体は割と簡単で、とりあえず詰めてみて、制約違反が発覚したら1手戻してみるという形式です。
+ より push して pop すればよかった気はしなくもない。

全部で20ゲーム、ターン内の組み合わせは可換、10ターンの並び替えも可換なので組み合わせ的には 20!/(2^10)/10! ですかね。
手元で実行したら 0.17s でした。

def solve(games, table)
  if table.size == games.size
    return table
  end

  if table.size % 2 == 0
    games.each do |k, v|
      unless table.include?(k)
        ans = solve(games, table + [k])
        if ans
          return ans
        end
      end
    end
    nil
  else
    used_id = table[-1]
    used = games[used_id]

    games.each do |k, v|
      unless table.include?(k)
        if used.none? { |p| v.include?(p) }
          ans = solve(games, table + [k])
          if ans
            return ans
          end
        end
      end
    end

    return nil
  end
end

ans = solve(games, [])

ans.each_slice(2) do |a, b|
  puts "#{a},#{b}"
end

以下テスト用のデータです。

{
  "2": [
    "a",
    "b",
    "c",
    "d"
  ],
  "3": [
    "b",
    "e",
    "c",
    "f"
  ],
  "4": [
    "a",
    "g",
    "f",
    "d"
  ],
  "5": [
    "a",
    "h",
    "c",
    "i"
  ],
  "6": [
    "g",
    "e",
    "f",
    "j"
  ],
  "7": [
    "a",
    "k",
    "f",
    "i"
  ],
  "8": [
    "b",
    "k",
    "c",
    "l"
  ],
  "9": [
    "b",
    "h",
    "d",
    "j"
  ],
  "10": [
    "a",
    "e",
    "f",
    "l"
  ],
  "11": [
    "b",
    "m",
    "c",
    "j"
  ],
  "12": [
    "h",
    "g",
    "d",
    "l"
  ],
  "13": [
    "h",
    "e",
    "i",
    "l"
  ],
  "14": [
    "g",
    "k",
    "d",
    "n"
  ],
  "15": [
    "e",
    "k",
    "c",
    "n"
  ],
  "16": [
    "a",
    "m",
    "i",
    "j"
  ],
  "17": [
    "h",
    "k",
    "l",
    "j"
  ],
  "18": [
    "e",
    "m",
    "f",
    "n"
  ],
  "19": [
    "g",
    "m",
    "i",
    "n"
  ],
  "20": [
    "h",
    "m",
    "l",
    "n"
  ],
  "21": [
    "k",
    "m",
    "j",
    "n"
  ]
}