Несмотря на то, что кубику Рубика уже много десятков лет, эта головоломка продолжает оставаться популярной. Ставятся рекорды — как людьми, так и роботами, совершенствуется алгоритм решения головоломки. Причем сейчас компьютеры уже могут научить собирать Кубик человека с любым уровнем опыта (речь здесь идет о приложениях обучающих, коих немало). Правильно собрать все грани после пары дней обучения при помощи компьютера смогут даже те, кто взял игрушку в руки в первый раз.
К слову, чемпион мира по сборке кубика Рубика (да, есть и такие чемпионы) решает головоломку всего за 4,9 секунды. Чемпиона зовут Лукас Эттер, это подросток из США. Аналогичный рекорд для роботизированной системы составляет уже 0,887 секунды (правда, этот результат еще не подтвержден). Но как научиться быстро собирать кубик Рубика самостоятельно? Можно тренироваться (на это могут уйти многие годы). А можно воспользоваться специальной программой, которая поможет собрать кубик в минимальное число ходов (так называемый алгоритм бога). Здесь никакие тренировки не нужны, приложение делает все само.
Вот так собирает кубик чемпион-человек:А так — чемпион-компьютер:
Вообще говоря, существует множество алгоритмов для сборки головоломки. Для обычного человека среднее число ходов составляет около 40. Немногие чемпионы умеют собирать кубик по алгоритму бога. Если кратко, то так называют алгоритм, который требует для сборки любой начальной конфигурации минимальное количество ходов. Для кубика Рубика это число равно 20.
А теперь вернемся к дополненной реальности. Разработчик по имени Martin Španěl создал приложение Mistr Kostky, которое помогает собирать кубик Рубика человеку. Причем число ходов как раз то самое — ровно 20. Приложение может определять состояние 2-3 граней кубика одновременно, а для распознавания получаемых изображений используется библиотека OpenCV.
В дополненной реальности показывается, как нужно вращать грани головоломки, чтобы достичь оптимального количества ходов. Разработчик создал свою программу в рамках научной работы — он является студентом Карлова университета (Прага). Работает программа в два этапа. На первом происходит распознавание состояния каждой грани. После того, как система завершает первый этап, начинается второй — приложение показывает пользователю, куда и как нужно вращать грани кубика для решения головоломки (иногда получается это сделать менее, чем за 20 ходов).Интересно, что если владелец головоломки ошибается, то приложение приходится перезапускать — оно не в состоянии перестроиться «на лету». Отмечу, что приложения для решения кубика рубика появились не сейчас. Это одно из лучших, да, но еще в 2009 году в каталог приложений Apple была добавлена программа Cube Cheater. Она помогала пользователю найти решение по фотографии граней.
Изначально автор создавал свое приложение под Android, но обещал выпустить и версию под другие платформы. Вот ветка обсуждения Mistr Kostky на Reddit.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Метки:geektimes.com
Авторский алгоритм Астратова Н.Д., г.Жлобин, Белоруссиия. Методика сборки кубика Рубика из 4 этапов с минимальным колличеством алгоритмов.
Идея алгоритма основана на статье «Алгоритм волшебного кубика» В. Дубровского в журнале «Квант», № 7, 1982 год.
Кубик Рубика имеет шесть граней. Каждая грань имеет свой цвет. Раскраска кубиков может отличаться в зависимости от производителя. За основу возьмем такую раскраску.
Достоинством метода является минимальное использование алгоритмов, чтобы выполнить полную сборку кубика (не более 10) для перемещения и разворотов бортовых (12) и угловых кубиков (8) и установка этих кубиков на свои места относительно центральных (6). Общее количество оборотов для сборки не превосходит 80, но на практике – 60-70. При скорости вращений граней кубика 1 об\сек – время полной сборки кубика занимает примерно одну минуту. Используемый метод будет полезным, как начинающих, так и для опытных любителей этой игрушки.
В настоящее время методы сборки кубика в основном сводятся к послойным методам.
Сборка «креста» и 1-го слоя обычно трудностей не представляет. Алгоритмы достаточно просты и не требуют особых трудозатрат для запоминания и выполнения.
Для сборки 2-х слоев необходимо 4 бортовых кубика установить на свои места. Выполнение такой операции требует уже знание алгоритмов (формул).
И, наконец, сборка последнего слоя (нижнего) – установка и разворот (ориентация) угловых и бортовых кубиков относительно центральных кубиков требует значительных трудозатрат и знания алгоритмов (формул). Таких операций известно достаточно много и их надо запоминать и затем механически выполнять при сборке. Например, расположение всех угловых и бортовых кубиков и их ориентация относительно центральных кубиков требуется знание и выполнение достаточно большого количества алгоритмов (более 70 – методика Джессики Фридрих) и требует знания и выполнения достаточно большого количества алгоритмов.
Для начинающего изучать сборку кубика метод Джессики Фридрих достаточно сложно. Вначале надо хорошо освоить обычную послойную методику. Такие методы размещены в Интернете и их нетрудно найти.
Чтобы освоить метод Джессики Фридрих полностью, нужно выучить ни много, не мало 119 алгоритмов (формул). Это позволит собирать кубик примерно за 56 оборотов.
Примечание: При выполнении этапа 2 собранный крест находится снизу, что не очень удобно («крест» вне поля видимости), поэтому алгоритмы следует именно выучить (вариантов – 41). Иначе можно разрушить крест, который находится снизу и не находится в поле зрения. Кроме того, имеются, так называемые «Затычки». Кто владеет методом Джессики Фридрих, знает, о чем идет речь.
Язык для описания алгоритмов
Если после буквы ничего не стоит, то, значит, крутим эту сторону по часовой, как если бы мы смотрели на грань в лицо. Помните это особенно для нижней (D) грани.
Если после буквы стоят знаки ‘ и “:
Методика сборки кубика выполняется в четыре этапа:
При выполнении этапов 1-3 будем считать кубик 3-х цветным:
Пары цветов подобраны по расположению цветов центральных кубиков – свой цвет и цвет противоположной грани.
Расположим кубик в пространстве таким образом:
Примечание: расположение в пространстве кубика может быть и другим. В качестве фронтальной плоскости может быть использован любой цвет на ваш выбор. Для правильной расстановки всех кубиков в «столбике» особых хитростей не требуется.
Причем задача упрощается, если в грани фасада (F) могут присутствовать кубики и желтого цвета, как угловые, так и боковые. Фронтальный цвет (белый) и цвет противоположной грани – B (желтый). Пример – на Рис. 3 Бортовые кубики правой плоскости® должны иметь цвет совпадающие с центральным кубиком, либо цвет противоположной грани (синий, зеленый). На Рис. 4 эти кубики обозначены стрелками. Соответственно эти бортовые кубики на верхней грани (U) и на нижней грани (D) должны иметь красный или оранжевый цвет (цвета центральных кубиков на (D,U) – противоположных гранях). На этом этапе сборку столбика 2х3 можно считать законченной.
Этот этап удается выполнить примерно за 10 ходов.
На первом этапе мы поставили 5 бортовых кубика в пространстве «правильно» (Рис. 4). Три бортовых кубика грани (F) и два бортовых кубика грани®.
Термин «правильно» говорит о том, что вплоть до окончательной сборки эти 5 кубиков могут только менять свое расположение и разворачивать их в гнездах, в которые они будут переходить по ходу сборки уже не понадобиться. Говоря точнее, эти пять бортовых кубика будут нуждаться только в перестановках в дальнейшем. Операции разворота этих кубиков уже не понадобятся. Остается еще 7 бортовых кубиков, которые необходимо развернуть. Эти кубики расположены в гранях (F,R). Всего бортовых кубиков 12, это означает, что среди семи оставшихся бортовых кубиков могут встретиться 2,4 или 6 кубиков, которые надо развернуть.
Примеры:
На Рис. 5 два бортовых кубика стоят «неправильно» (обозначены красными стрелками). Кубик 1 имеет на грани (U) синий цвет, на грани® – красный. Цвет не совпадает с центральными кубиками (U,R). Цвета граней бортовых кубиков должны совпадать с цветами центральных кубиков расположенными рядом, либо с цветом центрального кубика противоположной грани. Верхняя грань бортового кубика 1 должна иметь красный цвет (U), либо оранжевый (D).
Кубик 2 на (F) имеет оранжевый цвет, а должен быть желтого или белого цвета. Все остальные бортовые) кубики (F,R,U) расположены «правильно».
Для нашего случая, когда кубик 1 расположен на грани® вверху, а кубик 2 расположен на другой грани (F) необходимо кубик 2 разместить на (F) в нижнее положение (Рис. 6) выполнив поворот фронтальной грани против часовой стрелки – F’. Если же бортовой кубик расположен вверху или справа на (F), его надо перевести в нижнее положение (операция F”, F) Алгоритм Z1 разворачивает два бортовых кубика (1 и 3) – Рис. 6.
Алгоритм: Z1 = D R” D’
Результат выполнения Z1 на Рис. 7. Все бортовые кубики развернуты в пространстве. В этом легко можно убедиться, вращая в произвольных направлениях грани (F) и®. Заметим, что любые повороты граней (F) и® не разрушают столбик 2Х3 и не меняют ориентации всех бортовых кубиков. Алгоритм Z2 разворачивает два бортовых кубика, если они расположены на местах 1,2 фронтальной грани – Рис. 8.
Алгоритм: Z2 = D R’ D’
Алгоритм Z3 разворачивает четыре бортовых кубика, если они расположены на местах 1,2,3.4 – Рис. 9 Алгоритм: Z3 = D U’ F’ D’ U В случае если бортовые кубики расположены на других местах граней (F и R) расположить их на указанные места не составляет труда вращая только грани (F и R).
Наконец, в случае когда «неправильно» расположенных бортовых кубиков шесть используем алгоритмы для 4-хи 2-х кубиков в любом порядке.
Пример «правильно» расположенных кубиков на Рис. 7. Это легко проверить, вращая фронтальную и правую грани в любых направлениях. Напоминаем, что такое вращение не «разрушает» кубик. Не меняется расположение бортовых кубиков в столбике 2х3 и бортовые кубики не меняют своей ориентации. Таким образом, все 12 бортовых кубиков «правильно» ориентированы относительно центральных. К расстановке бортовых кубиков вернемся на этапе 4. Выполнение 2-го и 3-го этапов не затронут правильную ориентацию боковых кубиков.
Заключительной частью второго этапа необходимо собрать средний слой между гранями (F) и (B) – бортовые кубики 1,2 и 3) – рис. 10
В среднем слое бортовой кубик 1 и нижний кубик грани (L) столбика 2Х3 установлены верно на этапе 1, а вот кубики 4 и 5 надо переставить на место 2 и 3 – Рис. 10.
Это достигается вращением левой и фронтальной граней. Для этого случая можно выполнить: F R” F” R или R’ Направление последнего поворота R или R’ не имеет принципиального значения. Результат на Рис. 11.
Для других случаев перестановки боковых граней алгоритмы аналогичны и несложны. Результат на Рис. 11. теперь все цвета бортовых кубиков имеют цвет, совпадающий с цветом своего центрального, либо цвет, совпадающий с цветом центрального кубика противоположной грани. Поворачиваем кубик в пространстве таким образом, чтобы верхняя грань (центральный кубик) имела белый или желтый цвет – пример на Рис. 12. На верхней грани (U) получаем «крест» из желтых или белых бортовых кубиков. На противоположной нижней грани (D) такой же результат – «крест» из желтых или белых кубиков.
Для получения такого результата и понадобилась сборка среднего слоя между гранями (F) и (B) -бортовые кубики 1,2 и 3) – рис. 10.
Второй этап требует не более 10 оборотов.
На этапе 3 необходимо правильно развернуть и расставить на свои места относительно центральных кубиков 6 угловых кубиков. Два угловых кубика имеющие одну из сторон белую и желтую развернуты «правильно» на начальном этапе «столбик 2х3» (Рис. 3,4).
Шаг 1. Разворачивание угловых кубиков а) Если таких кубиков больше двух. (Рис.13) Например, на Рис. 13 таких кубиков три (1,2,3 на верхней грани (U)). Замечаем, что для разворота угловых кубика (1,2, 3), чтобы получить на грани (U) для этих кубиков желтый или белый цвет, нужно развернуть их против часовой стрелки.
Алгоритм: Z4 = L’ B U” B’ L B L’ U” L B’ Разворачивает кубики 1,2,3 – Рис.13 против часовой стрелки. Хотя для этого случая можно выполнить дважды алгоритм Z5 – разворот угловых кубиков по часовой стрелке. Выполнив алгоритм Z4, верхняя грань (U) примет следующий вид – Рис. 14. Все кубики (U) имеют желтый или белый цвет (цвет центрального кубика на грани (U) или цвет противоположного (D) центрального кубика).
Алгоритм: Z5 = U L U’ R’ U L’ U’ R
Разворачивает кубики 1,2,3 – Рис.15 по часовой стрелкеб) Если таких кубиков – 2. (Рис.16)
Эти два кубика могут быть расположены на:
Цвет угловых кубиков 1, 2 на грани (U и R) не совпадает с центральными кубиками (желтый, белый). Левая грань углового кубика 1 имеет желтый или белый цвет. Грань кубика 2 – белая. (Рис. 16) Угловой кубик 1 необходимо развернуть по часовой стрелке, кубик 2 против часовой стрелки. Алгоритм Z6 = (R F’D” F R’ U”) х 2 Развернет два угловых кубика (1,2) и кубик примет вид – Рис.17. На грани (U) имеем только желтый и белый цвет (цвет центрального кубика – желтый и белый цвет центрального кубика грани (D)). Если угловые кубики 1 и 2 находится не на местах (1,2), а на других необходимо привести их к виду – рис. 16. При этом грани (U,D) можно вращать на 90, 180 градусов в любых направлениях, а вертикальные грани (B,F,R,L) только на 180 градусов. Выполнение этого правила не разворачивает бортовые кубики и остальные угловые кубики относительно центральных (не меняет их ориентации).
Комбинируя алгоритмы Z4-Z6 можно развернуть все угловые кубики, а их может быть не более 6. Хотя на практике чаще всего встречаются комбинации из 2-х или 3-х таких кубиков.
Таким образом, разворачивание всех угловых кубиков (шаг 1) завершено. Шаг 1 требует примерно 25 ходов (вариант, когда нужно разворачивать все шесть угловых кубиков) На практике достаточно 20 поворотов. Шаг 2. Расстановка угловых кубиков.
Нас интересуют только угловые кубики. Для наглядности закрасим бортовые кубики в серый цвет. Допустим, после выполнения сборки до шага 1 мы получили такой результат (рис. 18):
Соберем верхнюю грань (желтый цвет) с правильной расстановкой угловых кубиков (Рис. 19). (U) – желтый цвет, (D) – белый. На верхней грани (U) только два угловых кубика желтого цвета (1 и 3). Два угловых кубика желтого цвета расположены на нижней грани (D).
Для правильной расстановки 4-х угловых кубиков желтого цвета в верхней грани (U) не требуется специальных алгоритмов.
Для расстановки надо выполнять такое правило: Расположение кубика в пространстве (U) – желтый цвет, (D) – белый. Верхнюю (U) и нижнюю (D) грани можно вращать на 90 или 180 градусов в любом направлении. Боковые грани (L F B R) можно поворачивать только на 180 градусов также в любом направлении. При таких вращениях ориентация всех бортовых и угловых кубиков сохраняется. Соблюдая это правило не трудно получить результат, представленный на Рис.19. Для удобства расстановки угловых кубиков нижней грани (D) повернем весь кубик вокруг горизонтальной оси, чтобы центральный белый кубик был сверху (рис.20). Угловые кубики (1,4) Рис. 20 на (F) имеют разный цвет – красный и оранжевый. В свою очередь угловые кубики (1,2) на грани® также цвета не совпадают – синий, зеленый. На верхней грани (U) – цвет центрального кубика – белый возможны три варианта расстановки угловых кубиков:
В случае, когда все угловые кубика верхней грани стоят не на своих местах Алгоритм: Z7 = F” R” F L F’ R” F L’ F Перемещает три угловых кубика (1,2 и 4) против часовой стрелки и кубик принимает вид (Рис. 22). Поворачиваем кубик в пространстве по вертикальной оси таким образом, чтобы на фронтальной грани (F) на месте 1 и 4 оказались два угловых кубика одного цвета
Угловые кубики на тыльной стороне (2 и 3) раскрашены в разные цвета. (Рис. 23).
Повторим алгоритм Z7 и получим кубик – Рис. 24. Повернув верхнюю грань (U) на 90 градусов можно убедиться, что все угловые кубики стоят на своих местах и правильно сориентированы в пространстве относительно центральных. – Рис. 25. Итак:
Шаг 2 требует максимум 25 ходов (вариант, когда нужно разворачивать шесть угловых кубиков) На практике достаточно 16 поворотов. В результате, после выполнения трех этапов имеем следующий результат – Рис. 26:
Для расстановки бортовых кубиков на свои места относительно цвета центральных и угловых кубиков необходимо выполнять 2 правила:
На этапе 4 установим все бортовые кубики (всего – 7) – Рис. 26-27.
Рис. 27 получен после поворота кубика в пространстве ось Y против часовой стрелки. Бортовой кубик 6 имеет на грани (B) красный цвет. Бортовые кубики 4 и 5 не совпадают по цвету своего центрального кубика или центрального кубика противоположной стороны (F) и® Для перестановки бортовых кубиков (4,5) соответственно цветам центральных кубиков выполним поворот D’ Рис. 28
Алгоритм: Z8 = R’ L F” R L’ U”
Выполнит перестановку кубиков – 4,5,6. Результат все угловые и бортовые кубики имеют свой цвет или противоположной грани – рис. 29. Для наглядности можно выполнить поворот – D.Алгоритм: Z9 = U” R” U” R” U” R” Переставляет сразу две пары бортовых кубиков кубика (1,2) грани® и (3,4) грани (U) – Рис. 30. Если бортовые кубики (1,2) расположены в левой грани, поворот R” в алгоритме Z9 заменить на поворот (L”). И наконец, если бортовые кубики (1,2) расположены на грани (D) поворот R” в алгоритме Z9 заменить на поворот (F”). На каких бы местах не располагались бортовые кубики одним или двумя поворотами граней, соблюдая правило 1,2 всегда можно привести к случаям для алгоритмов Z8,Z9.
Комбинируя алгоритмы (Z8,Z9) все бортовые кубики можно расставить свои места.
Этап 4 требует примерно 20 ходов.
На этом сборка кубика Рубика закончена.
Подведем итог:
статьия написана при использовании материалов сайта Рубикс и журнала Квант
+ 1 –
кубик рубика, головоломка, кубик рубика 3х3, схема сборки
Santal, 05.01.2010 12:00
Чемпионат России 2010 по Кубику Рубика → ← Таймер сборки Кубика Рубикаindada.ru
Несмотря на то, что кубику Рубика уже много десятков лет, эта головоломка продолжает оставаться популярной. Ставятся рекорды — как людьми, так и роботами, совершенствуется алгоритм решения головоломки. Причем сейчас компьютеры уже могут научить собирать Кубик человека с любым уровнем опыта (речь здесь идет о приложениях обучающих, коих немало). Правильно собрать все грани после пары дней обучения при помощи компьютера смогут даже те, кто взял игрушку в руки в первый раз.
К слову, чемпион мира по сборке кубика Рубика (да, есть и такие чемпионы) решает головоломку всего за 4,9 секунды. Чемпиона зовут Лукас Эттер, это подросток из США. Аналогичный рекорд для роботизированной системы составляет уже 0,887 секунды (правда, этот результат еще не подтвержден). Но как научиться быстро собирать кубик Рубика самостоятельно? Можно тренироваться (на это могут уйти многие годы). А можно воспользоваться специальной программой, которая поможет собрать кубик в минимальное число ходов (так называемый алгоритм бога). Здесь никакие тренировки не нужны, приложение делает все само.
Вот так собирает кубик чемпион-человек:А так — чемпион-компьютер:
Вообще говоря, существует множество алгоритмов для сборки головоломки. Для обычного человека среднее число ходов составляет около 40. Немногие чемпионы умеют собирать кубик по алгоритму бога. Если кратко, то так называют алгоритм, который требует для сборки любой начальной конфигурации минимальное количество ходов. Для кубика Рубика это число равно 20.
А теперь вернемся к дополненной реальности. Разработчик по имени Martin Španěl создал приложение Mistr Kostky, которое помогает собирать кубик Рубика человеку. Причем число ходов как раз то самое — ровно 20. Приложение может определять состояние 2-3 граней кубика одновременно, а для распознавания получаемых изображений используется библиотека OpenCV.
В дополненной реальности показывается, как нужно вращать грани головоломки, чтобы достичь оптимального количества ходов. Разработчик создал свою программу в рамках научной работы — он является студентом Карлова университета (Прага). Работает программа в два этапа. На первом происходит распознавание состояния каждой грани. После того, как система завершает первый этап, начинается второй — приложение показывает пользователю, куда и как нужно вращать грани кубика для решения головоломки (иногда получается это сделать менее, чем за 20 ходов).Интересно, что если владелец головоломки ошибается, то приложение приходится перезапускать — оно не в состоянии перестроиться «на лету». Отмечу, что приложения для решения кубика рубика появились не сейчас. Это одно из лучших, да, но еще в 2009 году в каталог приложений Apple была добавлена программа Cube Cheater. Она помогала пользователю найти решение по фотографии граней.
Изначально автор создавал свое приложение под Android, но обещал выпустить и версию под другие платформы. Вот ветка обсуждения Mistr Kostky на Reddit.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Метки:habr.com