Генерация формулы для рассадки игроков

[MayRiv]

У нас есть n столов, за которыми помещаются n игроков одновременно.
Необходимо создать формулу рассадки n*n игроков за n столами на максимальное количество раундов так, в конечном итоге каждый игрок сыграет с другим игроком не больше одного раза.

Я пробовал расписывать на бумажке, получалось примерно следующее.
Для $n=3$
123 456 789
159 483 726
168 429 735
147 258 369
Так же сформировал для $n=4$
1234 vbcd абвг 6789
17вd v28г аb39 6бc4
1б8b v4в9 а2с7 63гd
1v6a 2бd9 3cв8 4bг7
1сг9 2bв6 3vб7 4da8

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

Мои мысли и попытки решения:
1)Думал о том, что мы каждого игркоа на новый раунд сдвигаем на какое-то количество мест. И нам необходимо, чтобы ни одна пара игроков не играла дважды, поэтому можно создать что-то вроде маски сдвигов по примеру[0, 1, 2 ,3], которую применять к игрокам каждого стола, и формировать эту маску на каждый раунд так, чтобы суммарный сдвиг(маршрут) игроков, которые выходят из одной точки, не равнялся, потому что они тогда "сойдутся" за одним столом. Но этого недостаточно, в рассадке на троих возможна комбинация 147 258 369, сформированная путём группировки игроков по "разрядам", а не сдвигом. Получается, игрок перемещается не только по столам, но и по "разрядам", то есть маску надо формировать двумерную, и в этот момент это стало слишком сложно для меня, к тому же вполне вероятно, что это тупиковый вариант.

2) Пробовал написать программу, которая формирует такие столы тупым перебором, но у меня проблема с алгоритмом. В случае нужны, код программы на С++ могу предоставить.
Я писал так: каждый раунд мы выбираем из оставшегося пула игроков того, кто ещё не "знаком" ни с кем из игроков, уже набранных для данного стола, когда укомплектовали - идём к следующему. Столкнулся с тем, что уже на 3 раунде для случая n=3 можно начать укомплектовывать первые два стола так, что на третьем столе "пасьянс" уже не сойдётся, так как все оставшиеся игроки будут друг с другом знакомы. А на этапе формирования первого стола у нас недостаточно информации для того чтобы заглянуть в "остаток" для третьего стола. Возможно нужно формировать что-то вроде дерева решений, формировать список игроков подходящих для первого стола, и "смотреть", что будет если взять каждого конкретного игрока из списка, но это становится уже сложнее, и я тут решил попросить помощи у вас. Так же в голове крутится мысль попробовать использовать Prolog, так как все эти возвраты и проверки логических правил в духе языка, правда моё знакомство с прологом весьма шапочное, интересно послушать ваш совет.

Вполне возможно, эта задача решается по щелчку пальцев, я просто туповат.

[Vince Diesel]

Идея: представить элементы как квадратную матрицу. Одно решение – горизонтали, еще одно – вертикали. А затем попробовать циклически переставлять строки начиная со второй и брать столбцы получившихся матриц. В надежде, что удастся подобрать простые формулы для длин сдвигов, чтобы получить все оставшиеся $n-1$ вариантов. Скажем, чтобы получить 3й вариант, сдвинем вторую строку циклически на 1, третью на 2 и т.д.

[MayRiv]

Vince Diesel в сообщении #1212951 писал(а):

Идея: представить элементы как квадратную матрицу. Одно решение – горизонтали, еще одно – вертикали. А затем попробовать циклически переставлять строки начиная со второй и брать столбцы получившихся матриц. В надежде, что удастся подобрать простые формулы для длин сдвигов, чтобы получить все оставшиеся $n-1$ вариантов. Скажем, чтобы получить 3й вариант, сдвинем вторую строку циклически на 1, третью на 2 и т.д.

Можете, пожалуйста, переформулировать, я не совсем понял идею? Начиная с "еще одно – вертикали". Можете продемонстрировать 1 шаг вашего алгоритма?

[Vince Diesel]

Возьмем $n=3$. Матрица:

$$\left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{array} \right) $$

Одно решение $\{\{1, 2, 3\}, \{4, 5, 6\}, \{7, 8, 9\}\}$, второе $\{\{1, 4, 7\}, \{2, 5, 8\}, \{3, 6, 9\}\}$. Теперь сдвинем вторую строку на 1, третью на 2, получим

$$ \left( \begin{array}{ccc} 1 & 2 & 3 \\ 6 & 4 & 5 \\ 8 & 9 & 7 \\ \end{array} \right) $$

Третье решение — $\{\{1, 6, 8\}, \{2, 4, 9\}, \{3, 5, 7\}\}$.

[slavav]

Эта задача - близкая родственница "Девушек из пансиона Киркмана" (Жак Арсак, Программирование игр и головомок). Автор признаётся что не построил никакой теории, зато придумал эвристики ускоряющие перебор.

[slavav]

Ещё одно рассмотрение этой задачи можно найти на странице 309 книги Уолтера Уильяма Роуза Болла, Математические эссе и развлечения.
Будьте осторожны, сложная математика.

[DeBill]

MayRiv
Нда, ну Вы попали....
Подсчет числа ребер-знакомств (пребывание за одним столом) показывает, что уж если мы сумели организовать $n+1$ тур, то каждый сыграет с каждым, причем ровно один раз. Эт что-то напоминает....
Давайте считать игроков точками, а столы в каждом туре - прямыми. Тогда: через каждую пару точек проходит ровно одна прямая. А любые две прямые... Ан нет., не пересекаются. Ну тогда так: пусть в каждом туре есть еще распорядитель тура, и в процессе тура пусть он посидит за каждым из столов - познакомится с игроками (а после турнира все распорядители соберутся за круглым столом, и тоже познакомятся. Распорядителеей тоже обзовем точками, а круглый стол - прямой). Вот теперь стало все хорошо:
точек: $100+11 = 111$
прямых: прямых-столотуров - $110$, да еще прямая- круглый_стол
через любые две точки проходит ровно одна прямая (для пары игроков - тот столотур, в котором они встретились; для игрока и ТУРА - тот столотур в туре, за которым сидел игрок в туре, для двух туров - круглый_стол)
любые две прямые имеют единственную общую точку (Проверить!)
на каждой прямой - ровно $10+1$ точка, через каждую точку - ровно $10+1$ прямых (Проверить!)
Такая конфигурация прямых-точек называется геометрия конечного порядка (а число 10 -и есть ее порядок)
Можно погуглить по этим словам - задача эта известна. Чтото хорошо известно (типа, для любого нечетного $n$ такая геометрия есть, для $n=6$ -- ее нет . Вроде бы так). А вот для $n=10$ - в те времена, когда я услышал про эту задачу (т.е., очень давно) , это была открытая проблема. Для одного моего студента эта задача стала задачей-бзик: сколько сил он на нее угробил - уму непостижимо. Но...

-- 01.05.2017, 21:58 --

Про общую формулу: вроде бы, для нечетных $n$ есть циклические геометрии, которые хорошо устроены. А для четных --увы..

[slavav]

DeBill в сообщении #1213505 писал(а):

MayRiv
Нда, ну Вы попали....

Как вы думаете, имеет смысл искать решение на компьютере?

[DeBill]

slavav
Ну, можно попробовать искать циклические геометрии.
Они устроены так:
в геометрии должно быть $N = n^2+n+1$ точек, и столько же прямых.
Вся геометрия задается матрицей инцедентности:
если $i$-я точка лежит на $j-$й прямой, то в матрице на этом месте пишем 1, иначе - 0.
Так вот, в циклической геометрии, все строки (да и столбцы тоже) получаются из первой (го) сдвигами.
Так что, надо в первой строке (длины 111) отметить 11 единичек, так, чтобы при любом сдвиге (циклическом), полученная строка имела ровно одну общую единичку с исходной. Так что, проверка требует $111^2$ операций, и надо проверить $C^{11}_{111}$ вариантов. Грубо, всего требуется что-то порядка $10^{33}$ операций. Многовато, однако...
Но все же надо посмотреть в сети: мобыть, за последние 10-15 лет был прогресс в этой задаче, и отсутствие (в которое я верю) циклических десятого порядка таки установили.

-- 02.05.2017, 03:25 --

А, ну вот, даже в ВИКИ есть: "несуществование конечной геометрии порядка 10 доказано с помощью компьютера в 1989 году". Так что моя информация сильно устарела (давно не обновлялся....)

[MayRiv]

Цитата:

А, ну вот, даже в ВИКИ есть: "несуществование конечной геометрии порядка 10 доказано с помощью компьютера в 1989 году". Так что моя информация сильно устарела (давно не обновлялся....)

То есть задача эта не решается?

Пробую найти решение задачи с помощью брутфорса, написал программу, которая строит дерево решений и брутфорсит варианты, к сожалению, начиная с варианта на 9 игроков ресурсов компьютера не хватает для вычислений, может ли кто-то дать совет по оптимизации? код тут: https://github.com/MayRiv/Placing/blob/ ... h/main.cpp

-- 03.05.2017, 18:04 --

К слову, если сделать послабление, и разрешить людям играть до двух раз с другими людьми, то возможно решить задачу проще?

[slavav]

Первое что бросается в глаза - вы передаёте сложные структуры по значению. То есть они копируются при каждом вызове функции. Это так было предусмотрено?

-- 03.05.2017, 17:31 --

Второе - вы не удаляете экземпляры структуры Node.

-- 03.05.2017, 17:34 --

Третье - структура set<Node *> используется на по назначению. vector<Node *> будет работать быстрее и тратить меньше памяти.

-- 03.05.2017, 17:38 --

Четвёртое - верхний уровень вашего алгоритма - жадный. Даже если бы решение было, ваш алгоритм его может пропустить.

[DeBill]

MayRiv в сообщении #1213902 писал(а):

То есть задача эта не решается?

Как это - не решается. Она решена: такой рассадки игроков (для 10) нет.
Для случаев, когда $n$ - простое (или степень простого) рассадка есть, и - "красивая".
Для $n$, не представимого в виде суммы двух квадратов, и дающего при делении на 4 остаток 1 или 2, рассадки нет.
Т.е., для 3,4,5,7,8,9,11,13,... ответ: есть
Для 6 и 10 : нет
Для 12: неизвестно.

[Geen]

DeBill в сообщении #1213948 писал(а):

Она решена: такой рассадки игроков (для 10) нет.

Вроде бы вопрос был про максимально возможное количество раундов - т.е. не требовалось что бы все со всеми сыграли...

[MayRiv]

Geen в сообщении #1213952 писал(а):

DeBill в сообщении #1213948 писал(а):

Она решена: такой рассадки игроков (для 10) нет.

Вроде бы вопрос был про максимально возможное количество раундов - т.е. не требовалось что бы все со всеми сыграли...

Верно.

[DeBill]

MayRiv в сообщении #1214032 писал(а):

Верно.

А, ну да.
Но мне вот что интересно: неужели Ваш алгоритм (перебор, да?) для $n=9$нашел "максимальное" решение (из 10 туров)? А для $n=6$ - показал, что из 7 туров - нет?
Если - да, то это круто!