Мы делаем «Сбор» — сервис для детских футбольных школ: расписание, посещаемость, составы на игры. В прошлой статье рассказывали, что болит у тренеров и родителей. Теперь делаем новую роль — «Организатор турнира». И первое, обо что мы споткнулись, — расписание игр. Организаторы называют его главной своей проблемой.

Ниже — какие бывают турниры, что мы уже спроектировали, где схема ломается и какие у нас варианты. Готового ответа в статье нет: мы его ищем и просим помощи у тех, кто решал похожие задачи.

Два вида турниров

Даты известны заранее. Однодневный турнир или регулярный, где сетку игр строят сразу на весь сезон. Здесь задача в основном решённая: пары задаёт круговая система — метод круга, он же таблицы Бергера. Одна команда стоит на месте, остальные каждый тур сдвигаются на одну позицию, и за 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],
);
// пары: Юг — Восток, Запад — Центр, Парк — Лес; отдыхает: Север

Семь команд — значит, одна отдыхает. Здесь это «Север», у которого уже две игры, а «Парк», у которого игр не было, играет.

<?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, но мы их ещё не пробовали.

Открытые вопросы здесь такие: какие веса брать, кому отдыхать при нечётном числе, как не загнать турнир в тупик. Если неудачно выбрать пары в начале, к концу останутся команды, которые друг с другом уже сыграли, а с остальными встретиться не успевают.

Игры одного клуба не должны накладываться

Даже когда пары выбраны, их нужно расставить по полям и часам. Внутри одного возрастного турнира это понятно: пересекаем окна команд из опроса и ищем свободный слот. Но конфликты возникают между возрастами:

1. Один тренер — две команды. Матчи 2015 и 2016 года одного тренера не могут идти одновременно. Если поля в разных местах, нужен ещё запас на дорогу.

2. Игроки «за старших» и сборные. У нас в системе уже есть сборные из игроков разных команд клуба, и у каждого игрока записано, из какой команды он взят. Матчи этих команд нельзя ставить в одно время, а подряд — можно, но нежелательно.

3. Клуб целиком. Некоторым клубам важно, чтобы их команды вообще не играли одновременно: один администратор, одна форма на два возраста, одни и те же родители.

4. Разная длина матча. У младших и старших разная продолжительность игры, поэтому на одном поле слоты получаются разной длины.

5. Справедливость. Кто-то каждый тур получает 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 играет двумя командами сразу: правило «клуб целиком» мы для него не задали. Хороший пример того, что такие правила должен включать сам клуб или организатор — система их не угадает.

<?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 в это время уже есть матч»

Вопрос в том, кого сюда писать. Тренеров — точно. Игроков — только по заявке: кто поедет на матч, тренер решает накануне, а расписание публикуется раньше. А «клуб целиком» — это уже не человек, а группа.

А как делить на группы?

Если команд много, турнир делят на группы, и это тоже часть расписания. Делить по силе по итогам прошлого сезона? По географии, чтобы меньше ездить? Разводить ли команды одного клуба по разным группам? И что делать, когда к середине турнира половина группы перестаёт приезжать? Здесь у нас больше вопросов, чем вариантов.

Вопросы к вам

Если вы составляли расписания турниров, лиг, смен или занятий — нам очень пригодится ваш опыт:

1. Пары на неделю. Паросочетание по весам — разумный путь? Какие веса брать и как не загнать турнир в тупик к последним турам?

2. Кто отдыхает. При нечётном числе команд — тот, у кого больше игр, по очереди или по жребию?

3. Все возрасты сразу или по очереди? Если по очереди — с какого начинать?

4. Перебор или солвер? Где проходит граница по масштабу? Пробовал ли кто-то солверы из PHP или порты blossom с Packagist в бою?

5. Как объяснять, почему матч не встал? Через минимальный набор противоречащих правил, через ослабление правил по одному, ещё как-то?

6. Какие правила жёсткие, а какие мягкие? Тренер на двух площадках — понятно. А «играет за старших подряд»? А «две недели подряд в 9 утра»?

7. Группы. По какому принципу делить и разводить ли команды одного клуба?

8. Организаторам турниров: что вы проверяете руками перед публикацией расписания, чего нет в нашем списке?

Что дальше

Мы соберём ответы, проверим два-три варианта на реальных данных одной детской лиги и вернёмся со второй частью — что выбрали и почему. Если вы решали похожую задачу в другой области — смены, аудитории, корты, — расскажите в комментариях, как это было устроено у вас.

Что почитать по теме:

• метод круга и таблицы Бергера — 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).