Эти хитрые матрицы квестов

Немного воскресной математики, или задача о квесте, которую с 2009 года никак не доходили руки решить.

Классическая ситуация — N команд, каждая проходит N "контрольных точек" в ходе N этапов. Разумеется, на каждом этапе на каждой точке должна находиться только одна команда, и каждая команда должна пройти все точки по одному разу — то есть в квадрате N на N на каждой горизонтали и на каждой вертикали каждая цифра (номер контрольной точки) должна встретиться только один раз.

Это сделать просто (см.левый квадрат). Но игротехники знают ещё одну условность. Если время выполнения задания начинает сбиваться, то команды начинают догонять друг друга — то есть, например, быстрая "красная" команда на своём третьем этапе догоняет замешкавшуюся на своём втором этапе "жёлтую" команду — и они обе оказываются на точке №3. Это-то ладно, подождут, но тут случается так называемый "паровоз", и команды дружно идут от точки №3 к точке №4 вместе — теперь они зависят друг от друга. Более того, если к ним присоединится ещё и самая медленная "зелёная" команда — получится совсем некрасиво. На левой схеме этот "паровоз" обведён красным, но то же самое может случиться с двумя или тремя командами и на остальных точках.

А теперь посмотрим на правый квадрат. Проблема паровозов на нём решена: для любой точки N соблюдается правило: у одной из команд эта точка последняя, остальные команды после этой точки идут каждая на свою. В реальности это означает, что даже если две команды, выполнявшие задания в разном темпе, пересеклись на одной точке - вслед за этим они гарантированно «разойдутся» в разных направлениях. Толпами ходить никто не будет.

Хорошо если команд 4. А если больше? Существует ли аналогичная «беспаровозная» матрица?

Утверждение. Для любого чётного N такая матрица существует.

Для нечётных N — наоборот, без паровозов не обойтись, попробуйте проделать это с тремя командами и тремя точками — тут всего 6 вариантов маршрутов (помните что такое "факториал"?). Но вернёмся к чётным числам и попробуем построить матрицу 6 х 6.

Получилось? Можно обратить внимание на закономерности — правая половина матрицы обратна левой — то есть три правых маршрута — это те же три левых, но в обратном порядке. Первый маршрут можно всегда прокладывать как "1, 2, ..., N" — если мы заменим его на любой другой, это эквивалентно простому переименованию контрольных точек.

Осталось понять, как строить подобные матрицы для больших значений N. Много лет назад, когда мы только начинали проектировать квесты, я дошёл до матрицы 8х8 (пусть составление матрицы 8х8 будет вашим домашним заданием!), но, учитывая что контрольные точки на местности — будь то исторический центр города или территория отеля — это ещё и рельеф, препятствия, переходы улиц и так далее, практического смысла в матрицах большего размера чем 6х6, мало. В следующих статьях я расскажу как проектируются маршруты квестов на N команд при жёстком лимите времени на M заданий. В самом деле, когда в игре участвует 40 команд, а время есть, предположим, лишь на 8-10 контрольных точек... впрочем, не будем забегать вперёд. Эта статья — про теорию.

В своё время матрица 10х10 не давалась мне никак. При всей любви к теории, попытки были оставлены; я понимал что стоит написать небольшой рекурсивный алгоритм, который будет перебирать комбинации, заполняя пустую матрицу клетка за клеткой и сразу отбрасывая «ветку», как перестанут выполняться три условия (кстати, перечислим их ещё раз)

1. В каждой строке каждое число присутствует по одному разу

2. В каждом столбце каждое число присутствует по одному разу

3. Для каждого числа N выполняется условие: в каждом столбце после него идут разные числа (и в одном столбце, разумеется, число N стоит в нижней строке, и после него ничего не идёт)

Я обкатал алгоритм на маленьких матрицах. Даже с учётом того, что обсчёту подлежит меньше половины клеток матрицы - остальные либо можно заполнить заранее, либо они зависят от обсчитываемых (см.рисунок), количество возможных вариантов при решении задачи простым перебором - для матрицы 6х6 - 1.68 миллиона (6 в восьмой степени), для матрицы 8х8 - уже 18 квадриллионов (8 в восемнадцатой степени), ну и для 10х10 уже единица с тридцатью двумя нулями.

Но нас спасает рекурсия. Посмотрим на примере матрицы 6х6. Какие цифры мы можем подставить в обведённую клетку (второй этап "жёлтой" команды)? 2 и 5 сразу отбрасываем: они уже присутствуют и в данной строке, и в столбце. Отбрасываем и 3: у "красной" команды после 2 уже идёт 3. Отбрасываем 1 по той же причине, так как после 2 идёт 1 у "фиолетовой". Остаётся всего два варианта: 4 и 6.

Подставив 4 и 1 соответственно во вторую и третью точку "жёлтого" маршрута, мы и без алгоритма видим, что остаётся единственный вариант - 2 4 1 6 3 5. Вот что-то подобное и делает описанный мною алгоритм, сразу отбрасывая огромное количество заведомо неверных вариантов. Иногда первые подобранные значения кажутся верными, но, пройдя ещё несколько уровней рекурсии (то есть пытаясь подобрать маршруты для следующих команд), оказывается что это невозможно, и приходится "откатываться" по дереву вариантов назад.

Начиная с матрицы 12х12, расчёт резко усложняется. Я добавил к программе счётчик итераций - в таблице приведено количество итераций, приводящее к решению:

Да, теперь у меня есть матрицы 10х10 и 12х12, хвала быстрым компьютерам и средствам быстрой разработки. Готов поделиться, после того как выполните домашнее задание с 8х8 ;-)

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

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

p.s. Пока я писал эту статью, прошло около 20 миллионов итераций построения "беспаровозной матрицы" 14х14. Решение пока не найдено :)