Алгоритм для кубика рубика

Как сложить кубик Рубика новичку по алгоритму бога? Дополненная реальность приходит на помощь

Несмотря на то, что кубику Рубика уже много десятков лет, эта головоломка продолжает оставаться популярной. Ставятся рекорды — как людьми, так и роботами, совершенствуется алгоритм решения головоломки. Причем сейчас компьютеры уже могут научить собирать Кубик человека с любым уровнем опыта (речь здесь идет о приложениях обучающих, коих немало). Правильно собрать все грани после пары дней обучения при помощи компьютера смогут даже те, кто взял игрушку в руки в первый раз.

К слову, чемпион мира по сборке кубика Рубика (да, есть и такие чемпионы) решает головоломку всего за 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

Алгоритм сборки Кубика Рубика 3х3

Авторский алгоритм Астратова Н.Д., г.Жлобин, Белоруссиия. Методика сборки кубика Рубика из 4 этапов с минимальным колличеством алгоритмов.

Идея алгоритма основана на статье «Алгоритм волшебного кубика» В. Дубровского в журнале «Квант», № 7, 1982 год.

Кубик Рубика имеет шесть граней. Каждая грань имеет свой цвет. Раскраска кубиков может отличаться в зависимости от производителя. За основу возьмем такую раскраску.

Достоинством метода является минимальное использование алгоритмов, чтобы выполнить полную сборку кубика (не более 10) для перемещения и разворотов бортовых (12) и угловых кубиков (8) и установка этих кубиков на свои места относительно центральных (6). Общее количество оборотов для сборки не превосходит 80, но на практике – 60-70. При скорости вращений граней кубика 1 об\сек – время полной сборки кубика занимает примерно одну минуту. Используемый метод будет полезным, как начинающих, так и для опытных любителей этой игрушки.

В настоящее время методы сборки кубика в основном сводятся к послойным методам.

Сборка «креста» и 1-го слоя обычно трудностей не представляет. Алгоритмы достаточно просты и не требуют особых трудозатрат для запоминания и выполнения.

Для сборки 2-х слоев необходимо 4 бортовых кубика установить на свои места. Выполнение такой операции требует уже знание алгоритмов (формул).

И, наконец, сборка последнего слоя (нижнего) – установка и разворот (ориентация) угловых и бортовых кубиков относительно центральных кубиков требует значительных трудозатрат и знания алгоритмов (формул). Таких операций известно достаточно много и их надо запоминать и затем механически выполнять при сборке. Например, расположение всех угловых и бортовых кубиков и их ориентация относительно центральных кубиков требуется знание и выполнение достаточно большого количества алгоритмов (более 70 – методика Джессики Фридрих) и требует знания и выполнения достаточно большого количества алгоритмов.

Основные положения метода сборки кубика Джессики Фридрих, который состоит из четырех этапов:

1. Сборка креста на начальной стороне, после чего его надо расположить снизу (повернуть кубик в пространстве).
2. Сборка первого слоя одновременно со вторым слоем (F2L). После собранного начального креста, чтобы собрать первые два слоя одновременно, нужно поставить 4 пары “сторона-угол” – угловой кусочек, содержащий белый цвет + боковой, соответствующий ему. Вариантов расположения этих двух кусочков для каждой пары не много не мало – 41. Придется выучить их все, если хотите собирать первый слой одновременно со вторым.
3. Ориентация последнего слоя (OLL). Сборка желтой шапки, шапки на последней стороне. “Шапка” означает, что вся последняя сторона должна собраться, не разрушив при этом собранных двух слоев. Пояс последней стороны нас сейчас не интересует, он будет на следующем шаге. В Fridrich методе желтая шапка решается за один шаг, но количество вариантов тут немаленькое -57. Можно не сразу учить все 57 алгоритмов, а ограничиться пока первыми семью, т.е. сначала делать желтый крест, а потом один из семи вариантов (шапка в 2 этапа).

4. Постановка последнего слоя (PLL). Перестановка в последнем слое, то есть, как из желтой шапки за один алгоритм получить собранный куб. Количество вариантов, которые вам придется выучить = 21.

Для начинающего изучать сборку кубика метод Джессики Фридрих достаточно сложно. Вначале надо хорошо освоить обычную послойную методику. Такие методы размещены в Интернете и их нетрудно найти.

Чтобы освоить метод Джессики Фридрих полностью, нужно выучить ни много, не мало 119 алгоритмов (формул). Это позволит собирать кубик примерно за 56 оборотов.

Примечание: При выполнении этапа 2 собранный крест находится снизу, что не очень удобно («крест» вне поля видимости), поэтому алгоритмы следует именно выучить (вариантов – 41). Иначе можно разрушить крест, который находится снизу и не находится в поле зрения. Кроме того, имеются, так называемые «Затычки». Кто владеет методом Джессики Фридрих, знает, о чем идет речь.

Язык для описания алгоритмов

F – front – фронтальная сторона
B – back – задняя сторона
L – left – левая сторона
R – right – правая сторона
U – up – верхняя сторона
D – down – нижняя сторона

Если после буквы ничего не стоит, то, значит, крутим эту сторону по часовой, как если бы мы смотрели на грань в лицо. Помните это особенно для нижней (D) грани.

Если после буквы стоят знаки ‘ и “:

без знаков – поворот грани на 90 градусов по часовой стрелке;
‘ – поворот грани против часовой стрелки на 90 градусов;
“ – поворот грани на 180 градусов.

Методика сборки кубика выполняется в четыре этапа:

первый этап: Сборка столбика 2х2х3;
второй этап: Разворот всех боковых кубиков;
третий этап: разворачивание и расстановка угловых кубиков;
четвертый этап: расстановка бортовых кубиков.

При выполнении этапов 1-3 будем считать кубик 3-х цветным:

первый цвет – белый, желтый;
второй цвет – красный, оранжевый;
третий цвет – синий, зеленый.

Пары цветов подобраны по расположению цветов центральных кубиков – свой цвет и цвет противоположной грани.

Первый этап: Сборка столбика 2х2х3

Расположим кубик в пространстве таким образом:

Примечание: расположение в пространстве кубика может быть и другим. В качестве фронтальной плоскости может быть использован любой цвет на ваш выбор. Для правильной расстановки всех кубиков в «столбике» особых хитростей не требуется.

Причем задача упрощается, если в грани фасада (F) могут присутствовать кубики и желтого цвета, как угловые, так и боковые. Фронтальный цвет (белый) и цвет противоположной грани – B (желтый). Пример – на Рис. 3 Бортовые кубики правой плоскости® должны иметь цвет совпадающие с центральным кубиком, либо цвет противоположной грани (синий, зеленый). На Рис. 4 эти кубики обозначены стрелками. Соответственно эти бортовые кубики на верхней грани (U) и на нижней грани (D) должны иметь красный или оранжевый цвет (цвета центральных кубиков на (D,U) – противоположных гранях). На этом этапе сборку столбика 2х3 можно считать законченной.

Этот этап удается выполнить примерно за 10 ходов.

Второй этап: Разворот бортовых кубиков в гранях (F) и®

На первом этапе мы поставили 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) – цвет центрального кубика – белый возможны три варианта расстановки угловых кубиков:

1. все четыре кубика (1,2,3 и 4) расположились на своих местах – (U). Пары угловых кубиков [(4,1) – (F)], [(1,2) – ®], [(2,3) – (B)] и [(4,3) – (L)] имеет одинаковые цвета.
2. все четыре кубика (1,2,3 и 4) расположились не на своих местах – (U). Все пары угловых кубиков [(4,1) – (F)], [(1,2) – ®], [(2,3) – (B)] и [(4,3) – (L)] имеет несовпадение по цвету – Рис. 20.
одна пара угловых кубиков на вертикальных грани (F) имеет одинаковый цвет – Рис. 23.

В случае, когда все угловые кубика верхней грани стоят не на своих местах Алгоритм: 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. Итак:

для расстановки кубиков для случая (Рис. 20) алгоритм Z7 применяем дважды;
для расстановки кубиков для случая (Рис. 23) алгоритм Z7 применяем один раз;
расстановка кубиков для случая (Рис. 25) алгоритмы не нужны.

Шаг 2 требует максимум 25 ходов (вариант, когда нужно разворачивать шесть угловых кубиков) На практике достаточно 16 поворотов. В результате, после выполнения трех этапов имеем следующий результат – Рис. 26:

все бортовые кубики развернуты, но могут находиться не на своих местах относительно центральных кубиков;
все угловые кубики расположены на своих местах и развернуты правильно относительно центральных кубиков.

Четвертый этап: расстановка бортовых кубиков.

Для расстановки бортовых кубиков на свои места относительно цвета центральных и угловых кубиков необходимо выполнять 2 правила:

Углы поворотов угловых кубиков не изменяются при поворотах четырех вертикальных граней (R L F B) на 180 градусов и при произвольных поворотах горизонтальных граней (U D).
Углы поворотов бортовых кубиков не изменяются при поворотах двух противоположных (R L F B) граней на 180 градусов и при произвольных поворотах остальных граней (U D).

На этапе 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 Сборка столбика 2х2х3 не вызывает особых трудностей и не требует знания каких-то алгоритмов.
Этап 2 Разворот боковых кубиков в гранях F и R . Алгоритмы Z1-Z3 настолько просты, что легко запоминаются для выполнения.
Этап 3 Разворачивание и расстановка угловых кубиков. Алгоритмы Z4 – Z7 необходимо запомнить, чтобы выполнять автоматически. Итого надо запомнить всего четыре алгоритма.
Этап 4 Расстановка бортовых кубиков. Алгоритмы Z8,Z9 настолько просты, что легко запоминаются для выполнения.

статьия написана при использовании материалов сайта Рубикс и журнала Квант

Возможно вас заинтересует:
Как собрать венгерский кубик рубика

+ 1 –

кубик рубика, головоломка, кубик рубика 3х3, схема сборки

Santal, 05.01.2010 12:00

Чемпионат России 2010 по Кубику Рубика → ← Таймер сборки Кубика Рубика

indada.ru

Как сложить кубик Рубика новичку по алгоритму бога? Дополненная реальность приходит на помощь

Вот так собирает кубик чемпион-человек:

А так — чемпион-компьютер:

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Метки:

кубик рубика
головоломки
логические игры
алгоритм бога

habr.com

Алгоритм для кубика рубика

Как сложить кубик Рубика новичку по алгоритму бога? Дополненная реальность приходит на помощь

Алгоритм сборки Кубика Рубика 3х3

Основные положения метода сборки кубика Джессики Фридрих, который состоит из четырех этапов:

Первый этап: Сборка столбика 2х2х3

Второй этап: Разворот бортовых кубиков в гранях (F) и®

Третий этап: разворачивание и расстановка угловых кубиков.

Четвертый этап: расстановка бортовых кубиков.

Возможно вас заинтересует: Как собрать венгерский кубик рубика

Как сложить кубик Рубика новичку по алгоритму бога? Дополненная реальность приходит на помощь

Смотрите также

Возможно вас заинтересует:
Как собрать венгерский кубик рубика