Вообще это довольно интересное соревнование. Уже хотя бы потому что условные топ-10 на лб очень сильно вырываются вперед по сравнению с остальными участниками. А паблик решение уже почти дает медальку.
С другой стороны, в этом соревновании можно применять разные штуки: от алгоритмов поиска пути на графах, до обучения с подкреплением, до нахождения соотношений в группах. Кстати о них.
Многие знают, что преобразования стандартного кубика Рубика (кубика размеров 3х3х3), то есть всякие повороты граней и все такое, образуют группу с нехитрым названием: группа кубика Рубика. Аналогично обстоит дело с кубиками Рубика и других размеров: 2х2х2, 4х4х4, 128х128х128 и т.д. Все (известные мне) алгоритмы так или иначе опираются теорию групп.
В чем же прикол соревнования? Ведь, раз есть алгоритмы, наверняка есть их реализации, достаточно просто их применить и все, получим решение?
Ну вот оказывается, что среди представленных головоломок есть не только кубики Рубика (хотя их и большинство). В то же время, солверы кубика Рубика обычно дают не самое оптимальное решение даже для стандартного кубика 3х3х3. Хотя задачу они, конечно, как-то решают. Да и более того, для кубиков Рубика больших размеров даже не известно, за сколько ходов их точно можно собрать (God's number известен только для кубиков 2х2х2 и 3х3х3, для всего остального есть всякие оценки)
Ну вот. А можно ли, имея какое-то решение, как-то его упростить? Ответ: Да! Уж попытаться точно стоит.
Раз каждая головоломка определяет какую-то (конечную) группу, то давайте попробуем эту группу как-то изучить. Например, было бы здорово получить ее копредставление. Образующие нам известны -- это те самые повороты граней кубика. В других головоломках какие-то свои преобразования. Осталось получить соотношения: такие последовательности преобразований, которые никак не меняют состояние головоломки. Получив их, можно будет упрощать любое решение! А именно, если есть некоторое решение, то остается найти в нем эти соотношения и удалить их из него, получив новое решение. Так как соотношения никак не меняют состояние головоломки, то новое решение действительно будет решением, но так как какие-то преобразования из него удаляются, оно будет более оптимальным.
Остается лишь одна проблема: находить соотношения довольно сложно с вычислительной точки зрения. Особенно для каких-то очень больших групп: для одной из групп из соревнования копредставление у меня считалось более 13 часов, после чего я просто его прервал. Для более простых их найти несложно, однако для них известные решения итак оказываются (почти) оптимальными. Наверное тут можно использовать всякие нейронки для поиска соотношений (в духе работ, где применяют нейросети к математике, как эта, эта или эта), как и в целом для ускорения разных алгоритмов компьютерной алгебры.
Про это все я сделал целую тетрадку. Там все это детальнее описано. Такие дела.