Турнир, расписание которого собирают каждую неделю: как состыковать игры и не допустить пересечений? Нужен совет
Мы делаем «Сбор» — сервис для детских футбольных школ: расписание, посещаемость, составы на игры. В прошлой статье рассказывали, что болит у тренеров и родителей. Теперь делаем новую роль — «Организатор турнира». И первое, обо что мы споткнулись, — расписание игр. Организаторы называют его главной своей проблемой.
Ниже — какие бывают турниры, что мы уже спроектировали, где схема ломается и какие у нас варианты. Готового ответа в статье нет: мы его ищем и просим помощи у тех, кто решал похожие задачи.
Два вида турниров
Даты известны заранее. Однодневный турнир или регулярный, где сетку игр строят сразу на весь сезон. Здесь задача в основном решённая: пары задаёт круговая система — метод круга, он же таблицы Бергера. Одна команда стоит на месте, остальные каждый тур сдвигаются на одну позицию, и за N − 1 туров каждый встречается с каждым.
Расписание собирают каждую неделю. Многие детские турниры идут два-три месяца, и играть каждые выходные может не каждая команда. Поэтому организатор каждую неделю заново отвечает на вопросы:
кто может играть на этой неделе и в какое время;
кто с кем ещё не играл;
как разделить команды по группам;
как не допустить, чтобы несколько игр одного клуба шли одновременно;
на каком поле и в какой час ставить каждую пару.
Вторая задача и есть главная боль. О ней статья.
Как это выглядит сейчас
В понедельник организатор спрашивает в чате, кто когда может. Тренеры отвечают как получится: «в субботу не можем», «в воскресенье только до обеда», «нам всё равно». К четвергу он сводит ответы в таблицу, смотрит, кто с кем уже играл, и рассылает расписание. В пятницу выясняется, что у одного тренера две команды играют в 11:00 на разных площадках.
Почему так происходит: одна школа заявляет в серию по команде в каждый возраст — например, 2013/2014, 2015, 2015/2016 и 2017 годов рождения. Тренеров меньше, чем команд, и один человек часто ведёт два года. Сильные ребята младшего года играют «за старших». Организатор видит команды, но не видит, что за ними стоят одни и те же люди.
Что мы уже спроектировали
Тур и опрос. У тура есть игровые даты — обычно суббота и воскресенье. Перед туром каждой команде приходит опрос с фиксированными ответами: «не готовы в субботу», «не готовы в воскресенье», «в субботу с … до …», «в воскресенье с … до …», «в любое время». Формат предложил сам организатор: свободные слоты тренеры заполняют плохо, а на вопрос с вариантами отвечают. Кто не ответил к сроку, считается не готовым играть в этом туре.
Черновик и «не удалось разместить». Система собирает черновик расписания тура. Пара, которую не удалось поставить, не пропадает молча: она попадает в отдельный список с причиной — например, «обе команды не готовы в субботу, а в воскресенье их окна не пересекаются». Дальше организатор ставит её руками.
Ограничение на пилот. Только PHP и Laravel, без внешних солверов и отдельных сервисов. Это осознанное решение, но, похоже, именно его придётся пересматривать.
Сначала мы хотели брать пары из сетки по методу круга и выкидывать уже сыгранные. Для недельного турнира это не работает.
Почему готовая сетка не подходит для недельного турнира
Метод круга предполагает, что каждую неделю играют все. Стоит одной команде пропустить тур, и её соперник из сетки остаётся без игры, а дальше порядок начинает разъезжаться. Поэтому пары приходится выбирать заново каждую неделю — из тех, кто может играть и ещё не встречался.
По сути это задача о паросочетании в графе. Вершины — команды, которые могут играть на этой неделе. Рёбра — пары, которые ещё не играли. Вес ребра — насколько нам выгодна эта пара: например, пусть отстающие по числу игр догоняют. Сначала набираем как можно больше пар, при равенстве — пары с большим весом.
Для группы до 15–16 команд хватает перебора по битовой маске с запоминанием: состояний 2ⁿ, для 16 команд — около 65 тысяч. Мы сверили этот перебор с полным перебором вариантов на 200 случайных группах — ответы совпали. Как это выглядит в сервисе:
<?php
use App\Services\Scheduling\WeeklyPairing;
$result = app(WeeklyPairing::class)->pick(
available: ['Север', 'Юг', 'Восток', 'Запад', 'Центр', 'Парк', 'Лес'], // «Мост» не может
played: [['Север', 'Юг'], ['Восток', 'Запад'], ['Центр', 'Лес'],
['Север', 'Восток'], ['Юг', 'Запад'], ['Центр', 'Мост']],
games: ['Север' => 2, 'Юг' => 2, 'Восток' => 2, 'Запад' => 2,
'Центр' => 2, 'Парк' => 0, 'Лес' => 1, 'Мост' => 1],
);
// пары: Юг — Восток, Запад — Центр, Парк — Лес; отдыхает: СеверСемь команд — значит, одна отдыхает. Здесь это «Север», у которого уже две игры, а «Парк», у которого игр не было, играет.
Полный код WeeklyPairing
<?php
namespace App\Services\Scheduling;
/**
* Пары на неделю: из команд, которые могут играть, и пар, которые ещё не встречались.
* Сначала — как можно больше пар, при равенстве — пары отстающих по числу игр.
* Перебор по битовой маске с запоминанием: годится для групп примерно до 16 команд.
*/
final class WeeklyPairing
{
private array $teams = [];
private array $weight = []; // [i][j] => вес пары или null, если уже играли
private array $memo = [];
/**
* @param list<string> $available кто может играть на этой неделе
* @param list<array{string, string}> $played уже сыгранные пары
* @param array<string, int> $games сколько игр уже у каждой команды
* @return array{pairs: list<array{string, string}>, rest: list<string>}
*/
public function pick(array $available, array $played, array $games): array
{
$this->teams = array_values($available);
$this->memo = [];
$wasPlayed = array_flip(array_map(fn (array $p) => $this->key(...$p), $played));
foreach ($this->teams as $i => $a) {
foreach ($this->teams as $j => $b) {
$this->weight[$i][$j] = $i !== $j && ! isset($wasPlayed[$this->key($a, $b)])
? 10 - $games[$a] - $games[$b] // отстающие догоняют
: null;
}
}
$pairs = [];
for ($mask = (1 << count($this->teams)) - 1; $mask !== 0;) {
[, $i, $j] = $this->best($mask);
$mask &= ~(1 << $i);
if ($j !== null) {
$pairs[] = [$this->teams[$i], $this->teams[$j]];
$mask &= ~(1 << $j);
}
}
return ['pairs' => $pairs, 'rest' => array_values(array_diff($this->teams, array_merge(...$pairs)))];
}
/** @return array{int, int, ?int} [очки, команда, её соперник или null — отдыхает] */
private function best(int $mask): array
{
if ($mask === 0) {
return [0, -1, null];
}
if (isset($this->memo[$mask])) {
return $this->memo[$mask];
}
$i = 0;
while (! ($mask >> $i & 1)) {
$i++;
}
$others = $mask & ~(1 << $i);
$result = [$this->best($others)[0], $i, null]; // вариант: $i отдыхает
for ($j = $i + 1; $j < count($this->teams); $j++) {
if (($others >> $j & 1) && $this->weight[$i][$j] !== null) {
$score = 1000 + $this->weight[$i][$j] + $this->best($others & ~(1 << $j))[0];
if ($score > $result[0]) {
$result = [$score, $i, $j]; // 1000 за пару: сначала число пар
}
}
}
return $this->memo[$mask] = $result;
}
private function key(string $a, string $b): string
{
return $a < $b ? "$a|$b" : "$b|$a";
}
}Для групп больше 16 команд перебор не годится, нужен алгоритм Эдмондса (blossom). На Packagist есть его порты на PHP, например bakert/blossom-php, но мы их ещё не пробовали.
Открытые вопросы здесь такие: какие веса брать, кому отдыхать при нечётном числе, как не загнать турнир в тупик. Если неудачно выбрать пары в начале, к концу останутся команды, которые друг с другом уже сыграли, а с остальными встретиться не успевают.
Игры одного клуба не должны накладываться
Даже когда пары выбраны, их нужно расставить по полям и часам. Внутри одного возрастного турнира это понятно: пересекаем окна команд из опроса и ищем свободный слот. Но конфликты возникают между возрастами:
Один тренер — две команды. Матчи 2015 и 2016 года одного тренера не могут идти одновременно. Если поля в разных местах, нужен ещё запас на дорогу.
Игроки «за старших» и сборные. У нас в системе уже есть сборные из игроков разных команд клуба, и у каждого игрока записано, из какой команды он взят. Матчи этих команд нельзя ставить в одно время, а подряд — можно, но нежелательно.
Клуб целиком. Некоторым клубам важно, чтобы их команды вообще не играли одновременно: один администратор, одна форма на два возраста, одни и те же родители.
Разная длина матча. У младших и старших разная продолжительность игры, поэтому на одном поле слоты получаются разной длины.
Справедливость. Кто-то каждый тур получает 9 утра, кто-то играет два матча в день без перерыва.
Мы видим три способа с этим справиться.
Перебор с возвратом — на PHP
Планировать не каждый возраст отдельно, а все возрасты тура вместе. Каждую команду можно связать с другими: «не одновременно» — общий тренер, общие игроки, клуб целиком; «лучше не подряд» — общие игроки. Матчи с меньшим числом вариантов ставим первыми. Если зашли в тупик — откатываемся и пробуем другой слот. Если штраф уже больше лучшего найденного — дальше не идём.
<?php
use App\Services\Scheduling\SlotPlanner;
$planner = new SlotPlanner(
slots: [9, 10, 11, 12, 13],
fields: ['поле 1', 'поле 2'],
windows: ['Восток-15' => [11, 12, 13], 'Парк-16' => [9, 10]], // ответы на опрос
noOverlap: [['Север-15', 'Север-16'], ['Юг-15', 'Юг-16']], // тренер; игроки
notInARow: [['Юг-15', 'Юг-16']],
);
$schedule = $planner->plan([
['Север-15', 'Запад-15'], ['Юг-15', 'Восток-15'], ['Центр-15', 'Парк-15'],
['Север-16', 'Юг-16'], ['Запад-16', 'Центр-16'], ['Восток-16', 'Парк-16'],
]); 9:00 поле 1: Восток-16 — Парк-16
9:00 поле 2: Север-15 — Запад-15
10:00 поле 1: Центр-15 — Парк-15
10:00 поле 2: Запад-16 — Центр-16
11:00 поле 1: Юг-15 — Восток-15
13:00 поле 1: Север-16 — Юг-16Тренер «Севера» проводит матчи в 9:00 и 13:00, ребята «Юга» играют в 11:00 и 13:00 — с перерывом. А вот «Центр» в 10:00 играет двумя командами сразу: правило «клуб целиком» мы для него не задали. Хороший пример того, что такие правила должен включать сам клуб или организатор — система их не угадает.
Полный код SlotPlanner
<?php
namespace App\Services\Scheduling;
/**
* Расставляет пары тура по слотам и полям.
* Жёстко: окна из опроса; на поле один матч; связанные команды (общий тренер,
* общие игроки, один клуб) не играют одновременно.
* Мягко: команды с общими игроками не играют подряд — за это штраф.
* Перебор с возвратом и отсечением по штрафу; первыми — матчи с меньшим числом вариантов.
*/
final class SlotPlanner
{
private ?array $best = null;
private int $bestPenalty = PHP_INT_MAX;
public function __construct(
private array $slots, // [9, 10, 11, 12, 13]
private array $fields, // ['поле 1', 'поле 2']
private array $windows, // ['Восток-15' => [11, 12, 13]] — ответы на опрос
private array $noOverlap, // [['Север-15', 'Север-16']] — не одновременно
private array $notInARow, // [['Юг-15', 'Юг-16']] — лучше не подряд
) {}
/** @param list<array{string, string}> $matches */
public function plan(array $matches): ?array
{
usort($matches, fn ($a, $b) => count($this->options($a)) <=> count($this->options($b)));
$this->search($matches, 0, [], 0);
if ($this->best !== null) {
usort($this->best, fn ($a, $b) => [$a['slot'], $a['field']] <=> [$b['slot'], $b['field']]);
}
return $this->best; // null — расставить не удалось
}
private function search(array $matches, int $k, array $placed, int $penalty): void
{
if ($penalty >= $this->bestPenalty) {
return; // уже хуже найденного — дальше не идём
}
if ($k === count($matches)) {
[$this->best, $this->bestPenalty] = [$placed, $penalty];
return;
}
$match = $matches[$k];
foreach ($this->options($match) as [$slot, $field]) {
if ($this->clashes($match, $slot, $field, $placed)) {
continue;
}
$placed[] = ['slot' => $slot, 'field' => $field, 'home' => $match[0], 'away' => $match[1]];
$this->search($matches, $k + 1, $placed, $penalty + $this->inARow($match, $slot, $placed));
array_pop($placed);
}
}
/** Слоты, в которые могут обе команды, × поля */
private function options(array $match): array
{
$options = [];
foreach ($this->slots as $slot) {
foreach ($match as $team) {
if (isset($this->windows[$team]) && ! in_array($slot, $this->windows[$team], true)) {
continue 2;
}
}
foreach ($this->fields as $field) {
$options[] = [$slot, $field];
}
}
return $options;
}
private function clashes(array $match, int $slot, string $field, array $placed): bool
{
foreach ($placed as $p) {
if ($p['slot'] !== $slot) {
continue;
}
if ($p['field'] === $field) {
return true; // поле занято
}
foreach ($match as $t) {
foreach ([$p['home'], $p['away']] as $u) {
if ($t === $u || $this->linked($this->noOverlap, $t, $u)) {
return true; // команда или «связанная» с ней уже играет
}
}
}
}
return false;
}
private function inARow(array $match, int $slot, array $placed): int
{
$n = 0;
foreach ($placed as $p) {
if (abs($p['slot'] - $slot) !== 1) {
continue;
}
foreach ($match as $t) {
foreach ([$p['home'], $p['away']] as $u) {
$n += (int) $this->linked($this->notInARow, $t, $u);
}
}
}
return $n;
}
private function linked(array $groups, string $a, string $b): bool
{
foreach ($groups as $group) {
if ($a !== $b && in_array($a, $group, true) && in_array($b, $group, true)) {
return true;
}
}
return false;
}
}Плюс — остаёмся в PHP и Laravel, а новые правила добавляются в конструктор. Минус — перебор экспоненциальный. На шести матчах он мгновенный, а сколько выдержит тур на 40 матчей и три поля, мы не знаем: порядок перебора и отсечение помогают, но гарантий не дают. Если расписания нет, планировщик возвращает null, и объяснить организатору причину — отдельная задача.
Внешний солвер
Описать всё ограничениями и отдать специализированному солверу — например, CP-SAT из Google OR-Tools. Правила записываются явно, оптимум ищется хорошо. Но таких солверов на PHP мы не знаем, а отдельный сервис на другом языке противоречит нашему правилу «PHP и Laravel». Если вы запускали солвер из Laravel-приложения — через очередь, отдельный контейнер или ещё как-то — расскажите, как это было устроено.
Защита на уровне базы
Черновик после генератора правят руками, и чаще всего пересечение создаёт именно ручная правка. Поэтому последнюю проверку хочется держать в PostgreSQL: ограничение исключения не даст записать одного человека в два матча с перекрывающимся временем. Миграция:
<?php
use Illuminate\Database\Migrations\Migration;
use Illuminate\Database\Schema\Blueprint;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Facades\Schema;
return new class extends Migration
{
public function up(): void
{
DB::statement('CREATE EXTENSION IF NOT EXISTS btree_gist');
Schema::create('match_busy', function (Blueprint $table) {
$table->id();
$table->foreignId('match_id')->constrained()->cascadeOnDelete();
$table->foreignId('person_id')->constrained('users'); // тренер или игрок
});
// Время матча плюс запас на дорогу. Пересечение у одного человека — ошибка базы.
DB::statement('ALTER TABLE match_busy ADD COLUMN period tstzrange NOT NULL');
DB::statement('ALTER TABLE match_busy ADD CONSTRAINT match_busy_no_overlap
EXCLUDE USING gist (person_id WITH =, period WITH &&)');
}
public function down(): void
{
Schema::dropIfExists('match_busy');
}
};А сервис превращает ошибку базы в понятное сообщение для организатора — по коду SQLSTATE 23P01:
<?php
namespace App\Services\Scheduling;
use Illuminate\Database\QueryException;
use Illuminate\Support\Facades\DB;
final class BusyGuard
{
/** Занять человека на время матча; пересечение — понятная ошибка вместо SQL. */
public function reserve(int $matchId, int $personId, string $from, string $to): void
{
try {
DB::insert(
'insert into match_busy (match_id, person_id, period) values (?, ?, tstzrange(?, ?))',
[$matchId, $personId, $from, $to],
);
} catch (QueryException $e) {
if ($e->getCode() === '23P01') { // exclusion_violation
throw new ScheduleConflict("У человека #$personId в это время уже есть матч");
}
throw $e;
}
}
}три матча одного тренера (#1):
10:00–11:30 → записано
11:30–13:00 → записано: впритык можно
11:00–12:30 → ScheduleConflict: «У человека #1 в это время уже есть матч»Вопрос в том, кого сюда писать. Тренеров — точно. Игроков — только по заявке: кто поедет на матч, тренер решает накануне, а расписание публикуется раньше. А «клуб целиком» — это уже не человек, а группа.
А как делить на группы?
Если команд много, турнир делят на группы, и это тоже часть расписания. Делить по силе по итогам прошлого сезона? По географии, чтобы меньше ездить? Разводить ли команды одного клуба по разным группам? И что делать, когда к середине турнира половина группы перестаёт приезжать? Здесь у нас больше вопросов, чем вариантов.
Вопросы к вам
Если вы составляли расписания турниров, лиг, смен или занятий — нам очень пригодится ваш опыт:
Пары на неделю. Паросочетание по весам — разумный путь? Какие веса брать и как не загнать турнир в тупик к последним турам?
Кто отдыхает. При нечётном числе команд — тот, у кого больше игр, по очереди или по жребию?
Все возрасты сразу или по очереди? Если по очереди — с какого начинать?
Перебор или солвер? Где проходит граница по масштабу? Пробовал ли кто-то солверы из PHP или порты blossom с Packagist в бою?
Как объяснять, почему матч не встал? Через минимальный набор противоречащих правил, через ослабление правил по одному, ещё как-то?
Какие правила жёсткие, а какие мягкие? Тренер на двух площадках — понятно. А «играет за старших подряд»? А «две недели подряд в 9 утра»?
Группы. По какому принципу делить и разводить ли команды одного клуба?
Организаторам турниров: что вы проверяете руками перед публикацией расписания, чего нет в нашем списке?
Что дальше
Мы соберём ответы, проверим два-три варианта на реальных данных одной детской лиги и вернёмся со второй частью — что выбрали и почему. Если вы решали похожую задачу в другой области — смены, аудитории, корты, — расскажите в комментариях, как это было устроено у вас.
Что почитать по теме:
метод круга и таблицы Бергера — Round-robin tournament, Wikipedia;
алгоритм Эдмондса на PHP — bakert/blossom-php на Packagist;
CP-SAT — OR-Tools: CP-SAT Solver;
ограничения исключения на диапазонах — PostgreSQL: 8.17.10. Constraints on Ranges;
классика по теме — Scheduling Sport Tournaments using Constraint Logic Programming (Springer).
KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.