Несмотря на то, что кубику Рубика уже много десятков лет, эта головоломка продолжает оставаться популярной. Ставятся рекорды — как людьми, так и роботами, совершенствуется алгоритм решения головоломки. Причем сейчас компьютеры уже могут научить собирать Кубик человека с любым уровнем опыта (речь здесь идет о приложениях обучающих, коих немало). Правильно собрать все грани после пары дней обучения при помощи компьютера смогут даже те, кто взял игрушку в руки в первый раз.
К слову, чемпион мира по сборке кубика Рубика (да, есть и такие чемпионы) решает головоломку всего за 4,9 секунды. Чемпиона зовут Лукас Эттер, это подросток из США. Аналогичный рекорд для роботизированной системы составляет уже 0,887 секунды (правда, этот результат еще не подтвержден). Но как научиться быстро собирать кубик Рубика самостоятельно? Можно тренироваться (на это могут уйти многие годы). А можно воспользоваться специальной программой, которая поможет собрать кубик в минимальное число ходов (так называемый алгоритм бога). Здесь никакие тренировки не нужны, приложение делает все само.
Вот так собирает кубик чемпион-человек:
А так — чемпион-компьютер:
Вообще говоря, существует множество алгоритмов для сборки головоломки. Для обычного человека среднее число ходов составляет около 40. Немногие чемпионы умеют собирать кубик по алгоритму бога. Если кратко, то так называют алгоритм, который требует для сборки любой начальной конфигурации минимальное количество ходов. Для кубика Рубика это число равно 20.
А теперь вернемся к дополненной реальности. Разработчик по имени Martin Španěl создал приложение Mistr Kostky, которое помогает собирать кубик Рубика человеку. Причем число ходов как раз то самое — ровно 20. Приложение может определять состояние 2-3 граней кубика одновременно, а для распознавания получаемых изображений используется библиотека OpenCV.
В дополненной реальности показывается, как нужно вращать грани головоломки, чтобы достичь оптимального количества ходов. Разработчик создал свою программу в рамках своей научной работы — он является студентом Карлова университета (Прага).
Работает программа в два этапа. На первом происходит распознавание состояния каждой грани. После того, как система завершает первый этап, начинается второй — приложение показывает пользователю, куда и как нужно вращать грани кубика для решения головоломки (иногда получается это сделать менее, чем за 20 ходов).
Интересно, что если владелец головоломки ошибается, то приложение приходится перезапускать — оно не в состоянии перестроиться «на лету». Отмечу, что приложения для решения кубика рубика появились не сейчас. Это одно из лучших, да, но еще в 2009 году в каталог приложений Apple была добавлена программа Cube Cheater. Она помогала пользователю найти решение по фотографии граней.
Изначально автор создавал свое приложение под Android, но обещал выпустить и версию под другие платформы. Вот ветка обсуждения Mistr Kostky на Reddit.
Автор: marks
