Кубик Рубика — одна из самых популярных и в то же время сложных головоломок, притягивающая внимание любителей логики и математики уже много десятилетий. Существуют сотни алгоритмов и программных проектов, направленных на автоматическое решение этой загадки, однако мало кто использует для этих целей язык программирования Haskell. Twentyseven 1.0 — это особенный проект, который уже более десяти лет развивается на базе Haskell, объединяя строгость математики и красоту функционального программирования. Основатель проекта начал работу над решателем Кубика Рубика Twentyseven в январе 2014 года.
Он впервые познакомился с Haskell в 2013 году в рамках курса по лямбда-исчислению, и уже тогда язык показался ему необычным и интересным из-за своей ленивой семантики и математической природы. Именно эти качества сделали Haskell идеальным инструментом для реализации проекта: программирование превратилось в форму математической практики, а решение Кубика Рубика стало возможностью применить сложные теории групп на практике. Twentyseven 1.0 — это не просто очередная версия, а скорее юбилейный релиз, отражающий одиннадцатилетнюю историю развития тестового проекта. Главной задачей при выпуске стало обеспечение совместимости с актуальной версией компилятора GHC 9.
12. Несмотря на значительный промежуток времени с момента первоначального запуска, оказалось, что код в целом остался практически без изменений, сохранив многие первоначальные архитектурные решения, включая использование небезопасного подхода с unsafePerformIO для загрузки предвычисленных таблиц в константы верхнего уровня. В основе работы Twentyseven лежит мощный алгоритм итеративного углубленного поиска с оценкой A* (IDA*). В отличие от стандартного алгоритма A*, который может потребовать огромных ресурсов памяти из-за размерности пространства состояний Кубика Рубика (порядка 43 квинтильона уникальных состояний), IDA* выполняет серию глубинных поисков с постепенным увеличением максимальной длины найденного пути. Это позволяет существенно снизить требования к памяти, используя её преимущественно для хранения текущего пути решения.
Для эффективной работы алгоритма необходимо оценивать, насколько далеко текущее состояние Кубика от решения. Здесь на помощь приходит идея проекции полного состояния на упрощённую модель. Например, можно рассматривать только перестановку углов Кубика, игнорируя их ориентацию, либо ориентировку ребер. Для каждой такой проекции заранее вычисляется таблица с минимальным количеством ходов, нужных для возвращения к исходному состоянию, что даёт нижнюю границу на количество ходов для полного решения головоломки. Комбинируя оценки из разных проекций, программа получает более точную эвристику, позволяющую ускорить поиск решения.
Стоит отметить, что несмотря на все усилия, Twentyseven в оптимальном режиме решения может занимать часы на случайных конфигурациях Кубика. Это связано со сложностью исходного метода и выбором эвристик. Для решения более практичных задач существует алгоритм Херберта Коцимбы — двухфазный метод, который жертвует оптимальностью, но значительно повышает скорость, позволяя решать кубы в доли секунды. Интересно, что основа программы Twentyseven была вдохновлена заметками самого Коцимбы о его проекте Cube Explorer — приложении, написанном изначально на Паскале. Реализация на Haskell показывает, как современный функциональный язык может использоваться для решения классических проблем из мира головоломок и комбинаторики.
Формат ввода в Twentyseven представляет собой строку из 54 символов, каждый из которых соответствует цвету одного из граней Кубика. Позиции символов следуют строгому порядку, основанному на условной разметке граней: верхняя, левая, фронтальная, правая, задняя и нижняя стороны, при этом символы перечисляются с верхнего левого угла по строкам вниз и вправо в каждой грани. Такой подход обеспечивает корректную интерпретацию состояния кубика и дальнейшую обработку алгоритмом. Вывод же формируется в виде последовательности ходов, необходимых для решения головоломки. Каждое движение обозначается стандартной нотацией, включая повороты граней в разные стороны и на различные углы (например, U, L, B', R2 и так далее).
Эта последовательность может быть применена непосредственно к физическому кубику для решения, что делает Twentyseven не только учебным, но и практичным инструментом. Проект продолжает оставаться интересным примером того, как теоретические знания можно воплотить в реальную программу, способную решать задачи в реальном мире с использованием нетривиальных подходов. Кроме того, Twentyseven демонстрирует, что функциональный язык программирования, обладающий специфической парадигмой, способен конкурировать с классическими инструментами, используемыми в области алгоритмического решения головоломок. Одним из основных достоинств Twentyseven является прозрачность и открытость кода, что позволяет разработчикам и энтузиастам глубже понять устройство алгоритмов поиска и эвристик. Также благодаря длительному времени разработки и обновлениям проект смог адаптироваться под современные версии компилятора и включить современные программные практики, несмотря на сохранение исторического характера кода.
