Головоломка Арнольда: от комбинаторной геометрии к браузерной игрушке
Представьте игру, в которой выполняются простые правила:
1. На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.
2. Линии разбивают плоскость на области, раскрашенные в шахматном порядке.
3. Вы можете перестраивать разбиение, «схлопывая» и «выворачивая» треугольники.
4. Ваша цель — получить максимально возможное количество темных областей.
Я уже запрограммировал браузерную игрушку по этим правилам. В простейшем случае 5 линий процесс игры выглядит так:
Пример прохождения уровня из 5 линий
Пользовательский опыт
При небольшом количестве линий решить головоломку можно случайным перебором. Нужно помнить, что иногда надо «пожертвовать» счетом (количеством темных областей), так как не всегда есть «прямая дорога» к цели, на которой счет только увеличивается.
Я довольно быстро «прошел» все уровни до 19 линий. 21 линию (на скриншоте в начале) собрал часа за полтора. Правда, я знал, что существует центрально-симметричная конфигурация (поворот на 120° переводит ее в себя), и специально делал ее симметричной. 23 линии пытался собрать дважды, и оба раза не получилось набрать последнее очко.
С увеличением уровня сложность игры растет не только количественно (нужно дольше идти к цели), но и качественно: приходится придумывать новые приемы и подходы, так как старых становится недостаточно.
По ощущениям игра похожа на паззл, каждый кусочек которого подходит к любому другому кусочку, но общая картина из них всё никак не складывается.
Игра полностью отвлекает от происходящего вокруг, подходит для убивания времени в метро.
Математическая основа
Эта головоломка навеяна одной из задач из сборника «Задачи Арнольда» (В.И. Арнольд, № 1983–4, изд. Фазис, 2000):
На плоскости проведены N прямых. Найти максимальную разность между числом черных и белых областей шахматной раскраски дополнения.
Это открытая математическая проблема. Она является частным случаем 16-й проблемы Гильберта для многочленов специального вида — произведения линейных сомножителей ax+by+c.
Таким образом, переворачивая треугольники в игрушке, вы на самом деле решаете в частном случае задачу Арнольда! :)
Для преобразования конфигураций в головоломке именно схлопывание треугольников выбрано не случайно. Оказывается, с помощью таких схлопываний можно перевести произвольную конфигурацию в любую другую конфигурацию. Действительно, линии на плоскости, описанные в правилах, называются конфигурацией (псевдо)прямых. Они представляют элемент из группы кос. Суть теоремы Артина об образующих группы кос как раз и состоит в возможности перевода конфигураций друг в друга последовательностью преобразований треугольников.
Также задача Арнольда тесно связана с задачей о треугольниках Кобона.
Как я написал выше, задача Арнольда для произвольного количества прямых не решена. Вместе со мной Денис Уткин и Сергей Белёв потратили немало времени на попытки решения. Результаты нашего исследования — в многостраничном pdf-отчете. Я хочу выразить благодарность Денису и Сергею за совместный интерес, без которого в конечном итоге не появилась бы эта головоломка. Бонус для внимательных читателей: в отчете есть примеры конфигураций, на которых достигается цель головоломки.
Вычислительная модель игры
В основе визуализации — математическое моделирование некоторой «механической» системы. В этой системе массивные точки соединены ломаными линиями, отталкиваются друг от друга, испытывают сопротивление среды. В узлах ломаных — распрямляющие «пружинки». Концы ломаных прибиты внешними зафиксированными точками. Для расчетов движения точек по законам механики применяется метод Рунге — Кутты четвертого порядка с оценкой ошибок и плавающим шагом. Преподаватели вычматов были бы довольны :) Код, как обычно, открыт на гитхабе.
На этом пока всё. Могу подробнее рассказать о процессе разработки игрушки и о нашем исследовании задачи Арнольда, включая десятки тысяч часов процессорного времени, потраченного на поиск оптимальных конфигураций оптимизированным перебором. Пишите в комментариях, интересны ли эти вопросы.
