11.10.2026 · Luchanso · DeepSeek V4.1 Flash
Read in other languages: Русский · 中文.
In Americano tournaments the schedule is not a convenience, it is the format: people come to play with different partners, not to spend a third round with the same person. So the whole rotation is built up front and never changes once the tournament starts. This note is about how we searched for optimal rotations for 4–24 players, what did not work and why. At the end there is the full data and the code of every approach, so it can be reused directly.
The search itself was run by an AI agent, DeepSeek V4.1 Flash, running in the DeepSeek Harness and working in the Lipadel repository; the product decisions were made by the team. That is also why this note is written the way it is: another AI should be able to pick it up and continue.
n players, a match is four players (two pairs). The requirements:
Every round plays floor(n / 4) matches and n mod 4 players rest. Courts do not affect the rotation: there are always as many matches as the field size dictates, courts only decide which court a match lands on.
Count the meetings. In a round every player who plays gets two opponents. Over the whole tournament there are r rounds, so each player collects 2 × (their matches) opponent slots, and there are n · (n − 1) / 2 pairs in total. The arithmetic is simple:
For 14 players, for example: 13 rounds, 91 pairs, 156 slots. The minimum imbalance is reached when 65 pairs meet twice and 26 meet once, which means 11–12 matches and 1–2 byes per player. For 10 players it is 27 pairs twice and 18 once; for 11 players 33 twice and 22 once.
We measure imbalance as the sum of squared deviations of the meeting counts from the mean: zero is the ideal, and the checker also computes the mathematical minimum to compare against.
The first approach was the obvious one: write a search and let it find a good rotation. It did not work out — and that is an important part of the story.
Two mistakes of mine are worth more than the successes, so here they are. First: I “exhaustively” checked 1-rotational schemes for 12 and 16 players and concluded that no such rotations exist. That was wrong — it was enough to take the published construction. A failed enumeration does not prove that no construction exists. Second: the solver minimised the spread of meetings and did not notice that some pair never met at all. Formally the spread was small, in practice the rotation was unusable. It needed a large penalty for pairs with zero meetings.
Cyclic development of the first round. For 12, 16, 20 and 24 players the rotation comes from a single round: it is shifted modulo n − 1 while a special player (call it ∞) stays in place. 12 needs 11 shifts, 16 needs 15, 20 needs 19 and 24 needs 23. The first rounds:
Wh(12): ∞, 0 v 4, 5 | 1, 10 v 2, 8 | 3, 7 v 6, 9 Wh(16): ∞, 0 v 5, 10 | 1, 2 v 4, 8 | 3, 11 v 12, 14 | 6, 9 v 7, 13 Wh(20): ∞, 0 v 11, 12 | 3, 9 v 16, 1 | 4, 14 v 13, 18 | 6, 8 v 5, 2 | 7, 15 v 10, 17 Wh(24): ∞, 0 v 7, 10 | 1, 8 v 12, 22 | 5, 6 v 2, 11 | 3, 9 v 14, 18 | 17, 19 v 4, 16 | 15, 20 v 13, 21
Large-neighbourhood repair. For 14 players a whist ideal does not exist, so the exact optimum was found differently: take a ready rotation, free five rounds and rebuild them by exhaustive search, accepting only improvements. That turned four extra triple meetings into double ones and the cost became exactly 18.5714 against an ideal of 18.5714.
Nothing here would have happened without other people’s work, and that should be said plainly.
The rotations for 8 and 9 players came from our own exhaustive search, for 10, 11 and 14 from our own solver (for 14 it was the large-neighbourhood repair), and for 13 and 17 from the cyclic construction with a sampled base round.
Below is every size in the table. “Cost” is the sum of squared deviations of meeting counts from the mean, “ideal” is its mathematical minimum: zero means “every opponent exactly twice”.
| n | cost / ideal | meetings | matches | byes | kind |
|---|---|---|---|---|---|
| 4 | 0 / 0 | 2–2 | 3–3 | 0–0 | ideal |
| 5 | 0 / 0 | 2–2 | 4–4 | 1–1 | ideal |
| 8 | 0 / 0 | 2–2 | 7–7 | 0–0 | ideal |
| 9 | 0 / 0 | 2–2 | 8–8 | 1–1 | ideal |
| 10 | 10.8 / 10.8 | 1–2 | 7–8 | 1–2 | ideal |
| 11 | 13.2 / 13.2 | 1–2 | 8–8 | 3–3 | ideal |
| 12 | 0 / 0 | 2–2 | 11–11 | 0–0 | ideal |
| 13 | 0 / 0 | 2–2 | 12–12 | 1–1 | ideal |
| 14 | 18.57 / 18.57 | 1–2 | 11–12 | 1–2 | ideal |
| 16 | 0 / 0 | 2–2 | 15–15 | 0–0 | ideal |
| 17 | 0 / 0 | 2–2 | 16–16 | 1–1 | ideal |
| 20 | 0 / 0 | 2–2 | 19–19 | 0–0 | ideal |
| 21 | 82 / 0 | 1–4 | 20–20 | 1–1 | best known |
| 24 | 0 / 0 | 2–2 | 23–23 | 0–0 | ideal |
Every entry except 21 has zero repeated partners, zero pairs that never meet, zero consecutive byes and zero broken rounds. For 21 (a field size outside the current product scope) one pair meets four times, and the comment next to the entry says so honestly.
A single checker module validates every rotation. It reports the number of rounds, matches per round, repeated partners, the distribution of opponent meetings, matches and byes per player, consecutive byes, and broken rounds (where a player appears twice or a match is not four players). Here is the protocol you can use for your own rotations:
import { checkRotation, idealSchedule } from "./lib/tournament-rotation-check";
// ids — идентификаторы участников, rounds — массив раундов
const report = checkRotation(ids, rounds);
// Что должно сойтись у эталона:
// report.opponentsCost === report.opponentsCostIdeal — цена равна минимуму
// report.partnerRepeats === 0 — напарники без повторов
// report.opponentsMissing === 0 — ни одной пары без встреч
// report.consecutiveRests === 0 — никто не отдыхает подряд
// report.brokenRounds === 0 — раунды собраны корректно
// report.matchesMin/Max — ровно по идеалу idealSchedule(n)
// report.restsMin/Max — ровно по идеалу idealSchedule(n)We publish the whole table: it is a structure, not a search artefact, and reusing it is more honest than re-running a search. Indices are player numbers (0…n−1); a match is four indices [A1, A2, B1, B2], where the first pair plays against the second. Live identifiers are substituted by a permutation, so one structure serves any tournament of that size while the roles people get differ every time.
export type DesignRound = {
/** Кто отдыхает в раунде: индексы участников */
resting: number[];
/** Матчи раунда: по четыре индекса — [A1, A2, B1, B2] */
matches: [number, number, number, number][];
};
export const ROTATION_DESIGNS: Record<number, DesignRound[]> = {
// 4 участника: 3 раунда
4: [
{ resting: [], matches: [[3, 0, 1, 2]] },
{ resting: [], matches: [[3, 1, 2, 0]] },
{ resting: [], matches: [[3, 2, 0, 1]] },
],
// 5 участников: 5 раундов
5: [
{ resting: [0], matches: [[1, 4, 2, 3]] },
{ resting: [1], matches: [[2, 0, 3, 4]] },
{ resting: [2], matches: [[3, 1, 4, 0]] },
{ resting: [3], matches: [[4, 2, 0, 1]] },
{ resting: [4], matches: [[0, 3, 1, 2]] },
],
// 8 участников: 7 раундов
8: [
{ resting: [], matches: [[0, 1, 2, 3], [4, 5, 6, 7]] },
{ resting: [], matches: [[0, 2, 4, 6], [1, 3, 5, 7]] },
{ resting: [], matches: [[0, 3, 4, 7], [1, 2, 5, 6]] },
{ resting: [], matches: [[0, 4, 1, 5], [2, 6, 3, 7]] },
{ resting: [], matches: [[0, 5, 2, 7], [1, 4, 3, 6]] },
{ resting: [], matches: [[0, 6, 3, 5], [1, 7, 2, 4]] },
{ resting: [], matches: [[0, 7, 1, 6], [2, 5, 3, 4]] },
],
// 9 участников: 9 раундов
9: [
{ resting: [0], matches: [[1, 7, 3, 4], [2, 5, 6, 8]] },
{ resting: [1], matches: [[0, 6, 3, 5], [2, 4, 7, 8]] },
{ resting: [2], matches: [[0, 5, 1, 4], [3, 8, 6, 7]] },
{ resting: [3], matches: [[0, 1, 2, 8], [4, 7, 5, 6]] },
{ resting: [4], matches: [[0, 8, 5, 7], [1, 2, 3, 6]] },
{ resting: [5], matches: [[0, 2, 3, 7], [1, 8, 4, 6]] },
{ resting: [6], matches: [[0, 3, 4, 8], [1, 5, 2, 7]] },
{ resting: [7], matches: [[0, 4, 2, 6], [1, 3, 5, 8]] },
{ resting: [8], matches: [[0, 7, 1, 6], [2, 3, 4, 5]] },
],
// 10 участников: 9 раундов, точный оптимум (встречи 1–2, матчи 7–8, отдыхи 1–2)
10: [
{ resting: [1, 5], matches: [[0, 4, 7, 9], [2, 6, 3, 8]] },
{ resting: [0, 4], matches: [[1, 6, 2, 7], [3, 5, 9, 8]] },
{ resting: [6, 8], matches: [[0, 2, 9, 5], [1, 7, 4, 3]] },
{ resting: [2, 7], matches: [[0, 3, 4, 8], [1, 5, 9, 6]] },
{ resting: [3, 6], matches: [[0, 7, 5, 8], [1, 4, 9, 2]] },
{ resting: [4, 9], matches: [[0, 1, 6, 3], [2, 8, 5, 7]] },
{ resting: [0, 3], matches: [[1, 9, 7, 8], [2, 5, 6, 4]] },
{ resting: [1, 5], matches: [[0, 8, 2, 4], [3, 9, 7, 6]] },
{ resting: [2, 7], matches: [[0, 5, 1, 3], [4, 9, 6, 8]] },
],
// 11 участников: 11 раундов, точный оптимум (встречи 1–2, по 8 матчей и 3 отдыха)
11: [
{ resting: [2, 7, 10], matches: [[6, 9, 3, 8], [0, 1, 4, 5]] },
{ resting: [4, 5, 6], matches: [[3, 2, 1, 10], [8, 7, 0, 9]] },
{ resting: [1, 8, 9], matches: [[3, 7, 5, 2], [0, 4, 10, 6]] },
{ resting: [2, 5, 10], matches: [[0, 8, 4, 3], [7, 6, 1, 9]] },
{ resting: [0, 3, 6], matches: [[1, 2, 9, 8], [4, 10, 5, 7]] },
{ resting: [5, 7, 8], matches: [[4, 6, 10, 9], [0, 2, 1, 3]] },
{ resting: [1, 4, 9], matches: [[2, 8, 5, 6], [0, 3, 7, 10]] },
{ resting: [0, 3, 6], matches: [[1, 7, 8, 4], [2, 10, 5, 9]] },
{ resting: [1, 2, 10], matches: [[8, 6, 7, 0], [3, 5, 9, 4]] },
{ resting: [4, 7, 8], matches: [[6, 3, 5, 1], [0, 10, 2, 9]] },
{ resting: [0, 3, 9], matches: [[1, 8, 5, 10], [2, 6, 7, 4]] },
],
// 12 участников: 11 раундов — циклическое развёртывание первого раунда
// 12: [ [11, 0, 4, 5], [1, 10, 2, 8], [3, 7, 6, 9] ] и 11 сдвигов
12: [
{ resting: [], matches: [[11, 0, 4, 5], [1, 10, 2, 8], [3, 7, 6, 9]] },
{ resting: [], matches: [[11, 1, 5, 6], [2, 0, 3, 9], [4, 8, 7, 10]] },
{ resting: [], matches: [[11, 2, 6, 7], [3, 1, 4, 10], [5, 9, 8, 0]] },
{ resting: [], matches: [[11, 3, 7, 8], [4, 2, 5, 0], [6, 10, 9, 1]] },
{ resting: [], matches: [[11, 4, 8, 9], [5, 3, 6, 1], [7, 0, 10, 2]] },
{ resting: [], matches: [[11, 5, 9, 10], [6, 4, 7, 2], [8, 1, 0, 3]] },
{ resting: [], matches: [[11, 6, 10, 0], [7, 5, 8, 3], [9, 2, 1, 4]] },
{ resting: [], matches: [[11, 7, 0, 1], [8, 6, 9, 4], [10, 3, 2, 5]] },
{ resting: [], matches: [[11, 8, 1, 2], [9, 7, 10, 5], [0, 4, 3, 6]] },
{ resting: [], matches: [[11, 9, 2, 3], [10, 8, 0, 6], [1, 5, 4, 7]] },
{ resting: [], matches: [[11, 10, 3, 4], [0, 9, 1, 7], [2, 6, 5, 8]] },
],
// 13 участников: 13 раундов, циклическая конструкция
13: [
{ resting: [12], matches: [[0, 11, 4, 7], [1, 10, 2, 9], [3, 8, 5, 6]] },
{ resting: [0], matches: [[1, 12, 5, 8], [2, 11, 3, 10], [4, 9, 6, 7]] },
{ resting: [1], matches: [[2, 0, 6, 9], [3, 12, 4, 11], [5, 10, 7, 8]] },
{ resting: [2], matches: [[3, 1, 7, 10], [4, 0, 5, 12], [6, 11, 8, 9]] },
{ resting: [3], matches: [[4, 2, 8, 11], [5, 1, 6, 0], [7, 12, 9, 10]] },
{ resting: [4], matches: [[5, 3, 9, 12], [6, 2, 7, 1], [8, 0, 10, 11]] },
{ resting: [5], matches: [[6, 4, 10, 0], [7, 3, 8, 2], [9, 1, 11, 12]] },
{ resting: [6], matches: [[7, 5, 11, 1], [8, 4, 9, 3], [10, 2, 12, 0]] },
{ resting: [7], matches: [[8, 6, 12, 2], [9, 5, 10, 4], [11, 3, 0, 1]] },
{ resting: [8], matches: [[9, 7, 0, 3], [10, 6, 11, 5], [12, 4, 1, 2]] },
{ resting: [9], matches: [[10, 8, 1, 4], [11, 7, 12, 6], [0, 5, 2, 3]] },
{ resting: [10], matches: [[11, 9, 2, 5], [12, 8, 0, 7], [1, 6, 3, 4]] },
{ resting: [11], matches: [[12, 10, 3, 6], [0, 9, 1, 8], [2, 7, 4, 5]] },
], // 14 участников: 13 раундов, точный оптимум распределения встреч
// (whist-идеала «по два с каждым» для такого состава не существует: 65 пар
// встречаются дважды, 26 — один раз; найдено крупношаговым ремонтом сетки)
14: [
{ resting: [0, 11], matches: [[6, 10, 13, 12], [7, 9, 1, 8], [4, 3, 2, 5]] },
{ resting: [5, 7], matches: [[6, 3, 13, 2], [1, 10, 4, 0], [8, 9, 12, 11]] },
{ resting: [1, 6], matches: [[5, 12, 2, 7], [10, 11, 13, 3], [0, 8, 9, 4]] },
{ resting: [8, 9], matches: [[0, 1, 2, 12], [3, 10, 4, 6], [5, 11, 7, 13]] },
{ resting: [3, 10], matches: [[12, 9, 13, 0], [1, 6, 8, 5], [2, 4, 7, 11]] },
{ resting: [2, 4], matches: [[9, 11, 5, 10], [12, 8, 1, 13], [3, 0, 6, 7]] },
{ resting: [0, 1], matches: [[2, 11, 8, 10], [3, 7, 9, 13], [4, 5, 6, 12]] },
{ resting: [3, 8], matches: [[2, 0, 5, 13], [9, 6, 11, 4], [10, 7, 1, 12]] },
{ resting: [4, 12], matches: [[0, 9, 6, 13], [1, 11, 3, 5], [2, 10, 7, 8]] },
{ resting: [9, 10], matches: [[4, 13, 1, 2], [0, 5, 8, 3], [7, 12, 6, 11]] },
{ resting: [11, 13], matches: [[0, 10, 5, 7], [1, 9, 2, 6], [3, 12, 4, 8]] },
{ resting: [5, 7], matches: [[4, 1, 11, 13], [0, 6, 2, 8], [3, 9, 10, 12]] },
{ resting: [2, 6], matches: [[0, 12, 3, 11], [1, 5, 9, 10], [4, 7, 8, 13]] },
],
// 16 участников: 15 раундов — первый раунд
// [ [15, 0, 5, 10], [1, 2, 4, 8], [3, 11, 12, 14], [6, 9, 7, 13] ] и 15 сдвигов
16: [
{ resting: [], matches: [[15, 0, 5, 10], [1, 2, 4, 8], [3, 11, 12, 14], [6, 9, 7, 13]] },
{ resting: [], matches: [[15, 1, 6, 11], [2, 3, 5, 9], [4, 12, 13, 0], [7, 10, 8, 14]] },
{ resting: [], matches: [[15, 2, 7, 12], [3, 4, 6, 10], [5, 13, 14, 1], [8, 11, 9, 0]] },
{ resting: [], matches: [[15, 3, 8, 13], [4, 5, 7, 11], [6, 14, 0, 2], [9, 12, 10, 1]] },
{ resting: [], matches: [[15, 4, 9, 14], [5, 6, 8, 12], [7, 0, 1, 3], [10, 13, 11, 2]] },
{ resting: [], matches: [[15, 5, 10, 0], [6, 7, 9, 13], [8, 1, 2, 4], [11, 14, 12, 3]] },
{ resting: [], matches: [[15, 6, 11, 1], [7, 8, 10, 14], [9, 2, 3, 5], [12, 0, 13, 4]] },
{ resting: [], matches: [[15, 7, 12, 2], [8, 9, 11, 0], [10, 3, 4, 6], [13, 1, 14, 5]] },
{ resting: [], matches: [[15, 8, 13, 3], [9, 10, 12, 1], [11, 4, 5, 7], [14, 2, 0, 6]] },
{ resting: [], matches: [[15, 9, 14, 4], [10, 11, 13, 2], [12, 5, 6, 8], [0, 3, 1, 7]] },
{ resting: [], matches: [[15, 10, 0, 5], [11, 12, 14, 3], [13, 6, 7, 9], [1, 4, 2, 8]] },
{ resting: [], matches: [[15, 11, 1, 6], [12, 13, 0, 4], [14, 7, 8, 10], [2, 5, 3, 9]] },
{ resting: [], matches: [[15, 12, 2, 7], [13, 14, 1, 5], [0, 8, 9, 11], [3, 6, 4, 10]] },
{ resting: [], matches: [[15, 13, 3, 8], [14, 0, 2, 6], [1, 9, 10, 12], [4, 7, 5, 11]] },
{ resting: [], matches: [[15, 14, 4, 9], [0, 1, 3, 7], [2, 10, 11, 13], [5, 8, 6, 12]] },
],
// 17 участников: 17 раундов, циклическая конструкция. Базовый раунд
// [ [10, 7, 14, 15], [13, 1, 5, 12], [0, 4, 2, 11], [6, 8, 9, 3] ] и сдвиги по Z_17
17: [
{ resting: [16], matches: [[10, 7, 14, 15], [13, 1, 5, 12], [0, 4, 2, 11], [6, 8, 9, 3]] },
{ resting: [0], matches: [[11, 8, 15, 16], [14, 2, 6, 13], [1, 5, 3, 12], [7, 9, 10, 4]] },
{ resting: [1], matches: [[12, 9, 16, 0], [15, 3, 7, 14], [2, 6, 4, 13], [8, 10, 11, 5]] },
{ resting: [2], matches: [[13, 10, 0, 1], [16, 4, 8, 15], [3, 7, 5, 14], [9, 11, 12, 6]] },
{ resting: [3], matches: [[14, 11, 1, 2], [0, 5, 9, 16], [4, 8, 6, 15], [10, 12, 13, 7]] },
{ resting: [4], matches: [[15, 12, 2, 3], [1, 6, 10, 0], [5, 9, 7, 16], [11, 13, 14, 8]] },
{ resting: [5], matches: [[16, 13, 3, 4], [2, 7, 11, 1], [6, 10, 8, 0], [12, 14, 15, 9]] },
{ resting: [6], matches: [[0, 14, 4, 5], [3, 8, 12, 2], [7, 11, 9, 1], [13, 15, 16, 10]] },
{ resting: [7], matches: [[1, 15, 5, 6], [4, 9, 13, 3], [8, 12, 10, 2], [14, 16, 0, 11]] },
{ resting: [8], matches: [[2, 16, 6, 7], [5, 10, 14, 4], [9, 13, 11, 3], [15, 0, 1, 12]] },
{ resting: [9], matches: [[3, 0, 7, 8], [6, 11, 15, 5], [10, 14, 12, 4], [16, 1, 2, 13]] },
{ resting: [10], matches: [[4, 1, 8, 9], [7, 12, 16, 6], [11, 15, 13, 5], [0, 2, 3, 14]] },
{ resting: [11], matches: [[5, 2, 9, 10], [8, 13, 0, 7], [12, 16, 14, 6], [1, 3, 4, 15]] },
{ resting: [12], matches: [[6, 3, 10, 11], [9, 14, 1, 8], [13, 0, 15, 7], [2, 4, 5, 16]] },
{ resting: [13], matches: [[7, 4, 11, 12], [10, 15, 2, 9], [14, 1, 16, 8], [3, 5, 6, 0]] },
{ resting: [14], matches: [[8, 5, 12, 13], [11, 16, 3, 10], [15, 2, 0, 9], [4, 6, 7, 1]] },
{ resting: [15], matches: [[9, 6, 13, 14], [12, 0, 4, 11], [16, 3, 1, 10], [5, 7, 8, 2]] },
],
// 20 участников: 19 раундов — тот же приём: первый раунд и 19 сдвигов
20: [
{ resting: [], matches: [[19, 0, 11, 12], [3, 9, 16, 1], [4, 14, 13, 18], [6, 8, 5, 2], [7, 15, 10, 17]] },
{ resting: [], matches: [[19, 1, 12, 13], [4, 10, 17, 2], [5, 15, 14, 0], [7, 9, 6, 3], [8, 16, 11, 18]] },
{ resting: [], matches: [[19, 2, 13, 14], [5, 11, 18, 3], [6, 16, 15, 1], [8, 10, 7, 4], [9, 17, 12, 0]] },
{ resting: [], matches: [[19, 3, 14, 15], [6, 12, 0, 4], [7, 17, 16, 2], [9, 11, 8, 5], [10, 18, 13, 1]] },
{ resting: [], matches: [[19, 4, 15, 16], [7, 13, 1, 5], [8, 18, 17, 3], [10, 12, 9, 6], [11, 0, 14, 2]] },
{ resting: [], matches: [[19, 5, 16, 17], [8, 14, 2, 6], [9, 0, 18, 4], [11, 13, 10, 7], [12, 1, 15, 3]] },
{ resting: [], matches: [[19, 6, 17, 18], [9, 15, 3, 7], [10, 1, 0, 5], [12, 14, 11, 8], [13, 2, 16, 4]] },
{ resting: [], matches: [[19, 7, 18, 0], [10, 16, 4, 8], [11, 2, 1, 6], [13, 15, 12, 9], [14, 3, 17, 5]] },
{ resting: [], matches: [[19, 8, 0, 1], [11, 17, 5, 9], [12, 3, 2, 7], [14, 16, 13, 10], [15, 4, 18, 6]] },
{ resting: [], matches: [[19, 9, 1, 2], [12, 18, 6, 10], [13, 4, 3, 8], [15, 17, 14, 11], [16, 5, 0, 7]] },
{ resting: [], matches: [[19, 10, 2, 3], [13, 0, 7, 11], [14, 5, 4, 9], [16, 18, 15, 12], [17, 6, 1, 8]] },
{ resting: [], matches: [[19, 11, 3, 4], [14, 1, 8, 12], [15, 6, 5, 10], [17, 0, 16, 13], [18, 7, 2, 9]] },
{ resting: [], matches: [[19, 12, 4, 5], [15, 2, 9, 13], [16, 7, 6, 11], [18, 1, 17, 14], [0, 8, 3, 10]] },
{ resting: [], matches: [[19, 13, 5, 6], [16, 3, 10, 14], [17, 8, 7, 12], [0, 2, 18, 15], [1, 9, 4, 11]] },
{ resting: [], matches: [[19, 14, 6, 7], [17, 4, 11, 15], [18, 9, 8, 13], [1, 3, 0, 16], [2, 10, 5, 12]] },
{ resting: [], matches: [[19, 15, 7, 8], [18, 5, 12, 16], [0, 10, 9, 14], [2, 4, 1, 17], [3, 11, 6, 13]] },
{ resting: [], matches: [[19, 16, 8, 9], [0, 6, 13, 17], [1, 11, 10, 15], [3, 5, 2, 18], [4, 12, 7, 14]] },
{ resting: [], matches: [[19, 17, 9, 10], [1, 7, 14, 18], [2, 12, 11, 16], [4, 6, 3, 0], [5, 13, 8, 15]] },
{ resting: [], matches: [[19, 18, 10, 11], [2, 8, 15, 0], [3, 13, 12, 17], [5, 7, 4, 1], [6, 14, 9, 16]] },
],
// 21 участник: 21 раунд — лучшее известное (цена 82, оптимум 0 не найден).
// ВНИМАНИЕ: здесь есть пара, встречающаяся четырежды — продукт обещает не больше
// трёх, но взамен в этой сетке нет ни одной пары без встреч
21: [
{ resting: [0], matches: [[1, 20, 9, 12], [2, 19, 17, 4], [3, 18, 5, 16], [6, 15, 7, 14], [8, 13, 10, 11]] },
{ resting: [19], matches: [[0, 20, 16, 3], [1, 18, 5, 14], [2, 17, 7, 12], [4, 15, 6, 13], [8, 11, 9, 10]] },
{ resting: [17], matches: [[7, 10, 1, 16], [20, 18, 6, 11], [9, 8, 4, 13], [19, 0, 12, 5], [14, 3, 2, 15]] },
{ resting: [15], matches: [[0, 11, 14, 1], [2, 13, 7, 8], [3, 12, 10, 5], [4, 18, 16, 20], [6, 9, 17, 19]] },
{ resting: [13], matches: [[3, 0, 10, 17], [1, 12, 9, 4], [2, 11, 20, 14], [5, 8, 6, 7], [15, 19, 18, 16]] },
{ resting: [11], matches: [[0, 16, 17, 15], [1, 10, 18, 14], [2, 9, 5, 6], [3, 8, 7, 4], [12, 20, 19, 13]] },
{ resting: [9], matches: [[3, 6, 5, 4], [13, 17, 14, 16], [0, 8, 12, 18], [1, 15, 11, 19], [2, 7, 20, 10]] },
{ resting: [7], matches: [[0, 14, 20, 8], [1, 6, 16, 12], [2, 5, 15, 13], [3, 4, 11, 17], [9, 19, 18, 10]] },
{ resting: [5], matches: [[15, 11, 4, 1], [17, 9, 7, 19], [8, 18, 2, 3], [12, 14, 16, 10], [13, 20, 0, 6]] },
{ resting: [3], matches: [[0, 12, 15, 9], [1, 2, 16, 8], [4, 20, 14, 10], [5, 19, 13, 11], [6, 18, 7, 17]] },
{ resting: [1], matches: [[18, 0, 16, 6], [2, 20, 9, 13], [11, 4, 17, 5], [14, 8, 3, 19], [12, 10, 7, 15]] },
{ resting: [20], matches: [[3, 10, 19, 1], [2, 18, 11, 9], [4, 16, 7, 13], [5, 15, 0, 17], [6, 14, 12, 8]] },
{ resting: [18], matches: [[19, 20, 11, 7], [1, 17, 10, 8], [3, 15, 12, 6], [16, 2, 5, 13], [4, 14, 0, 9]] },
{ resting: [16], matches: [[0, 15, 9, 7], [1, 8, 17, 20], [2, 14, 12, 4], [3, 13, 18, 19], [5, 11, 6, 10]] },
{ resting: [14], matches: [[0, 7, 11, 3], [1, 13, 15, 20], [2, 12, 17, 18], [4, 10, 9, 5], [6, 8, 16, 19]] },
{ resting: [12], matches: [[0, 13, 1, 11], [2, 10, 6, 20], [3, 9, 17, 16], [4, 8, 18, 15], [5, 7, 14, 19]] },
{ resting: [10], matches: [[14, 17, 13, 18], [19, 12, 4, 6], [11, 20, 16, 15], [3, 7, 9, 1], [2, 8, 0, 5]] },
{ resting: [8], matches: [[13, 16, 4, 0], [2, 6, 1, 7], [3, 5, 9, 20], [19, 10, 14, 15], [17, 12, 11, 18]] },
{ resting: [6], matches: [[0, 10, 2, 4], [1, 5, 15, 12], [3, 17, 13, 14], [7, 20, 18, 9], [8, 19, 16, 11]] },
{ resting: [4], matches: [[16, 9, 11, 14], [13, 12, 1, 3], [5, 20, 8, 17], [19, 6, 2, 0], [7, 18, 10, 15]] },
{ resting: [2], matches: [[6, 17, 13, 10], [12, 11, 7, 16], [0, 1, 5, 18], [19, 4, 3, 20], [14, 9, 15, 8]] },
],
// 24 участника: 23 раунда — первый раунд и 23 сдвига
24: [
{ resting: [], matches: [[23, 0, 7, 10], [1, 8, 12, 22], [5, 6, 2, 11], [3, 9, 14, 18], [17, 19, 4, 16], [15, 20, 13, 21]] },
{ resting: [], matches: [[23, 1, 8, 11], [2, 9, 13, 0], [6, 7, 3, 12], [4, 10, 15, 19], [18, 20, 5, 17], [16, 21, 14, 22]] },
{ resting: [], matches: [[23, 2, 9, 12], [3, 10, 14, 1], [7, 8, 4, 13], [5, 11, 16, 20], [19, 21, 6, 18], [17, 22, 15, 0]] },
{ resting: [], matches: [[23, 3, 10, 13], [4, 11, 15, 2], [8, 9, 5, 14], [6, 12, 17, 21], [20, 22, 7, 19], [18, 0, 16, 1]] },
{ resting: [], matches: [[23, 4, 11, 14], [5, 12, 16, 3], [9, 10, 6, 15], [7, 13, 18, 22], [21, 0, 8, 20], [19, 1, 17, 2]] },
{ resting: [], matches: [[23, 5, 12, 15], [6, 13, 17, 4], [10, 11, 7, 16], [8, 14, 19, 0], [22, 1, 9, 21], [20, 2, 18, 3]] },
{ resting: [], matches: [[23, 6, 13, 16], [7, 14, 18, 5], [11, 12, 8, 17], [9, 15, 20, 1], [0, 2, 10, 22], [21, 3, 19, 4]] },
{ resting: [], matches: [[23, 7, 14, 17], [8, 15, 19, 6], [12, 13, 9, 18], [10, 16, 21, 2], [1, 3, 11, 0], [22, 4, 20, 5]] },
{ resting: [], matches: [[23, 8, 15, 18], [9, 16, 20, 7], [13, 14, 10, 19], [11, 17, 22, 3], [2, 4, 12, 1], [0, 5, 21, 6]] },
{ resting: [], matches: [[23, 9, 16, 19], [10, 17, 21, 8], [14, 15, 11, 20], [12, 18, 0, 4], [3, 5, 13, 2], [1, 6, 22, 7]] },
{ resting: [], matches: [[23, 10, 17, 20], [11, 18, 22, 9], [15, 16, 12, 21], [13, 19, 1, 5], [4, 6, 14, 3], [2, 7, 0, 8]] },
{ resting: [], matches: [[23, 11, 18, 21], [12, 19, 0, 10], [16, 17, 13, 22], [14, 20, 2, 6], [5, 7, 15, 4], [3, 8, 1, 9]] },
{ resting: [], matches: [[23, 12, 19, 22], [13, 20, 1, 11], [17, 18, 14, 0], [15, 21, 3, 7], [6, 8, 16, 5], [4, 9, 2, 10]] },
{ resting: [], matches: [[23, 13, 20, 0], [14, 21, 2, 12], [18, 19, 15, 1], [16, 22, 4, 8], [7, 9, 17, 6], [5, 10, 3, 11]] },
{ resting: [], matches: [[23, 14, 21, 1], [15, 22, 3, 13], [19, 20, 16, 2], [17, 0, 5, 9], [8, 10, 18, 7], [6, 11, 4, 12]] },
{ resting: [], matches: [[23, 15, 22, 2], [16, 0, 4, 14], [20, 21, 17, 3], [18, 1, 6, 10], [9, 11, 19, 8], [7, 12, 5, 13]] },
{ resting: [], matches: [[23, 16, 0, 3], [17, 1, 5, 15], [21, 22, 18, 4], [19, 2, 7, 11], [10, 12, 20, 9], [8, 13, 6, 14]] },
{ resting: [], matches: [[23, 17, 1, 4], [18, 2, 6, 16], [22, 0, 19, 5], [20, 3, 8, 12], [11, 13, 21, 10], [9, 14, 7, 15]] },
{ resting: [], matches: [[23, 18, 2, 5], [19, 3, 7, 17], [0, 1, 20, 6], [21, 4, 9, 13], [12, 14, 22, 11], [10, 15, 8, 16]] },
{ resting: [], matches: [[23, 19, 3, 6], [20, 4, 8, 18], [1, 2, 21, 7], [22, 5, 10, 14], [13, 15, 0, 12], [11, 16, 9, 17]] },
{ resting: [], matches: [[23, 20, 4, 7], [21, 5, 9, 19], [2, 3, 22, 8], [0, 6, 11, 15], [14, 16, 1, 13], [12, 17, 10, 18]] },
{ resting: [], matches: [[23, 21, 5, 8], [22, 6, 10, 20], [3, 4, 0, 9], [1, 7, 12, 16], [15, 17, 2, 14], [13, 18, 11, 19]] },
{ resting: [], matches: [[23, 22, 6, 9], [0, 7, 11, 21], [4, 5, 1, 10], [2, 8, 13, 17], [16, 18, 3, 15], [14, 19, 12, 20]] },
],
};
/** Проверенная эталонная сетка на такой состав; null — считаем поиском */
export function rotationDesign(participantsCount: number): DesignRound[] | null {
return ROTATION_DESIGNS[participantsCount] ?? null;
}Below are four approaches that actually worked and one dead end. Everything was validated by the checker at every step: without it, it is far too easy to mistake a beautiful but wrong rotation for a solution.
The main idea: for every player, the number of unmet meetings must fit exactly into the remaining matches — two opponents per match. Check it right after placing a match rather than at the end of a round, and almost every branch is cut at the entrance.
/** Баланс игрока: несведённые встречи = 2 × его оставшиеся матчи */
function playerBalanced(player: number, nextRound: number): boolean {
let need = 0;
for (let q = 0; q < n; q++) {
if (q === player) continue;
const count = opp[player * n + q];
if (count > 2) return false; // больше двух встреч не допускаем
need += 2 - count;
}
return need === 2 * matchesLeft(player, nextRound);
}
/**
* Раунды собираются по матчам в каноническом порядке: первый нерасставленный
* игрок обязательно попадает в матч. Пары напарников не повторяются, встречи
* соперников — не больше двух, а баланс проверяется сразу после расстановки
* матча (внутри раунда), а не в конце.
*/
function dfsRound(round: number, players: number[], matches: Match[]): boolean {
if (players.length === 0) {
if (round + 1 === totalRounds) return true;
return dfsRound(round + 1, playersOf(round + 1), []);
}
const first = players[0];
const rest = players.slice(1);
for (const partner of shuffle(rest)) {
if (partnersUsed[first * n + partner] === 1) continue;
const afterPartner = rest.filter((p) => p !== partner);
partnersUsed[first * n + partner] = 1;
for (let i = 0; i < afterPartner.length; i++) {
for (let j = i + 1; j < afterPartner.length; j++) {
const o1 = afterPartner[i];
const o2 = afterPartner[j];
if (partnersUsed[o1 * n + o2] === 1) continue;
const faces = [[first, o1], [first, o2], [partner, o1], [partner, o2]];
if (faces.some(([a, b]) => opp[a * n + b] >= 2)) continue;
partnersUsed[o1 * n + o2] = 1;
for (const [a, b] of faces) opp[a * n + b] += 1;
matches.push([first, partner, o1, o2]);
const left = afterPartner.filter((p) => p !== o1 && p !== o2);
const balanced = [first, partner, o1, o2].every((p) =>
playerBalanced(p, round + 1),
);
if (balanced && dfsRound(round, left, matches)) return true;
matches.pop();
for (const [a, b] of faces) opp[a * n + b] -= 1;
partnersUsed[o1 * n + o2] = 0;
}
}
partnersUsed[first * n + partner] = 0;
}
return false;
}For odd n, take one round and multiply it by shifts over Z_n, together with the resting player. The base is sampled randomly and validated by the checker: a full enumeration of bases is impossible, and good ones turned out to be about one in a few thousand.
/**
* Для нечётного n сетка строится сдвигами одного раунда по Z_n: отдыхающий
* сдвигается вместе с ним. Так нашлась сетка на 17 (для 13 база известна).
*/
function buildFromBase(base: Match[]): Round[] {
const inf = n - 1;
return Array.from({ length: n }, (_, shift) => ({
resting: [(inf + shift) % n],
matches: base.map((m) => m.map((v) => (v + shift) % n) as Match),
}));
}
// Полный перебор баз для 17 невозможен (сотни миллионов раскладок), поэтому
// берём случайные и проверяем чекером — удачных оказалось порядка одной на
// несколько тысяч.
while (Date.now() < deadline) {
const base = randomBase(); // случайное разбиение n−1 игроков на матчи
const report = checkRotation(ids, buildFromBase(base));
if (report.partnerRepeats === 0 && report.opponentsCost <= 1e-6) {
return buildFromBase(base); // идеальная сетка
}
}Free part of the rounds and rebuild them, accepting only improvements. This is what turned a “nearly ideal” rotation for 14 into an ideal one.
/**
* Крупношаговый ремонт (LNS). Берём готовую сетку, освобождаем k раундов и
* собираем их заново перебором, принимая только улучшения. Именно так был
* найден точный оптимум для 14: четыре пары встречались трижды вместо двух,
* и освобождение пяти раундов дало пересобрать их правильно.
*/
while (Date.now() < deadline) {
const indices = shuffle(allRounds).slice(0, k).sort();
openRounds(indices); // снять матчи и вернуть их пары в свободные
const found = dfs(0, playersOf(indices[0]), []);
const cost = found ? variance() + 500 * missingPairs() : Infinity;
if (found && cost < best) {
best = cost;
closeRounds(indices, schedule); // принять
saveDesign();
} else {
closeRounds(indices, savedMatches); // откатить
}
}A fast way to get a good rotation when no construction is known. Note the penalty for pairs with zero meetings, and that there are two kinds of alternating cycle: with only one of them, even fields have no valid move at all.
/**
* Энергия поиска: дисперсия распределения встреч плюс большой штраф за пары,
* которые не встретились ни разу. Штраф обязателен: без него поиск выравнивал
* разброс за счёт того, что какая-то пара не играла вовсе.
*/
function variance(): number {
let total = 0;
for (let i = 0; i < pairsCount; i++) total += (oppCount[i] - mean) ** 2;
return total;
}
function energy(): number {
return variance() + 500 * missingPairs();
}
/**
* Переключение по чередующемуся циклу — единственный ход, который меняет саму
* структуру напарников, не ломая её: рёбра цикла меняют раунд, а набор пар во
* всей сетке остаётся тем же. Цикл бывает двух видов, и проверять нужно оба —
* на этом я потерял много времени: с одним видом ходов для чётных составов
* просто не существовало.
*/
function cycleSwitch(roundA: Round, roundB: Round): boolean {
const start = Math.floor(random() * n);
const cycle = findAlternatingCycle(roundA, roundB, start);
if (!cycle) return false;
// a-b-d-c-a: во втором раунде стоят (a,c) и (b,d)
const caseB = partnerIn(roundB, a) === c && partnerIn(roundB, b) === d;
// a-b-c-d-a: во втором раунде стоят (b,c) и (d,a)
const caseA = partnerIn(roundB, b) === c && partnerIn(roundB, d) === a;
if (!caseA && !caseB) return false;
swapEdgesBetweenRounds(cycle); // набор пар сохраняется
return true;
}
/** Направленный спуск: перебираем раунды и ставим лучшую раскладку матчей */
function descentRound(index: number): void {
const pairs = partnerPairsOf(rounds[index]);
if (pairs.length < 4) return;
for (const id of roundOpponents(rounds[index])) oppCount[id] -= 1;
const base = energy();
let bestMatches = rounds[index].matches;
let bestTotal = base + 1e9;
for (const grouping of allGroupings(pairs)) {
const cost = base + groupingCost(grouping);
if (cost < bestTotal - 1e-9) {
bestTotal = cost;
bestMatches = groupingToMatches(grouping);
}
}
rounds[index].matches = bestMatches;
for (const id of roundOpponents(rounds[index])) oppCount[id] += 1;
}
// Основной цикл: спуск до локального минимума, затем серия переключений,
// чтобы из него выйти; иногда возвращаемся к лучшему найденному состоянию.
while (Date.now() < deadline) {
descentAllRounds();
if (energy() <= ideal) break;
for (let k = 0; k < 2 + Math.floor(random() * 6); k++) cycleSwitch(randomRound(), randomRound());
}/**
* Тупик, который стоит знать. Room square стороны k = n−1 содержит n символов
* и по n/2 пар в строке — ровно структура напарников раунда. Но перебор всех
* раскладок показал: для k = 11 (n = 12) идеальной раскладки у этой структуры
* не существует (43 100 узлов, пространство исчерпано). Проверено на заведомо
* рабочей структуре: у неё раскладка находится за 12 узлов, так что дело не в
* переборе, а в самой структуре.
*/
export const square = roomSquareFor(k); // строки — раунды, пары — напарники
for (const row of square) {
const pairs = row.filter((cell) => cell !== null);
// ...перебор раскладок внутри раунда
}A short checklist that will save time:
The product code is open with the rest of the repository: the checker is lib/tournament-rotation-check.ts, the generator and table are lib/tournament-rotation.ts and lib/tournament-rotation-designs.ts, the tests are e2e/tests/tournament-rotation.spec.ts.