Методы подбора для решения "шейпмодов" и "стикермодов"

[DDT]

Среди бесчисленного количества головоломок, для меня всегда выделялся один большой класс.
С математической точки зрения, многие из них мне были хорошо известны, вплоть до интуитивного решения головоломки, но на практике возникали большие проблемы с пониманием головоломок из-за их внешнего вида и долгое время такие головоломки не поддавались моему решению.

При этом, весь мир разделился на три лагеря:

• Те, кто так же не могут решать такие головоломки;
• Те, для кого эти головоломки по какой-то причине просты (обладают хорошим пространственным мышлением, не сталкивались со сложными вариациями или по каким-то другим причинам);
• Те, кто не пробовали решать такие головоломки или не знают об их существовании.

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

В этой теме я хочу разобрать то, что из этого вышло и показать, что перебор возможных ситуаций — инструмент, который имеет место быть даже в сложных головоломках.

Ну а для начала небольшой вопрос-ответ.

Что такое "шейпмоды" и "стикермоды"?

Под этим будем подразумевать такую модификацию головоломки, при которой набор возможных перестановок оригинальной головоломки не увеличивается, но при этом меняется её внешний вид: геометрическая форма (шейпмод) или дизайн стикеров (стикермод).

Чаще всего не меняется даже внутреннее строение головоломки, только её внешний вид.

Например, вот несколько шейпмодов кубика Рубика 3x3x3 со стрелками на каждом стикере:

• Классический кубик Рубика, Void-куб;
  
  
• Мастермофикс, axis-куб;
  
  

Если число ситуаций головоломки превосходит количество атомов в обозримой вселенной, можно ли её решить подбором?

Полным перебором — нет, но о нём и не идёт речи.
Я предлагаю самые обычные методы с конечным количеством ситуаций. Просто на каждом этапе будет перебираться небольшой набор ситуаций.

Нужно ли уметь решать оригинальную головоломку, чтобы решать её шейпмод?

Необязательно, но лишним не будет. Достаточно понимать, как вращается головоломка и хотя бы немного знать её язык вращения.

Подходит ли такой метод для решения головоломок на скорость/количество ходов?

Такой подход сборки будет определённо медленнее, чем проанализировать головоломку, заучить расположение всех элементов и придумать хороший скоростной метод для неё.

Как понять, что головоломка A является шейпомодом головоломки B?

По одному внешнему виду — практически никак, бывает так, что две одинаково выглядещее головоломки являются принципиально разными.

Если головоломка находится в собранном виде, можно попытаться найти её в интернете и сравнить их вращение. Либо разобрать головоломку и сравнить внутренний механизм с известными.

Ещё один вариант — посчитать количество осей вращений, количество слоёв и элементов на них, найти головоломку со схожими характеристиками и сравнить их вращение.

[DDT]

Навигация по головоломкам, которые уже можно решить методом подбора (будет пополняться):

• Кубики Рубика: 2x2x2, 3x3x3, чётные кубы, нечётные кубы;
• Кубоиды: 2x2xN, 3x3xN, NxNxM;
• Мегаминксы: классический;
• Пирамидки Мефферта: классическая;
• Скьюбы: классический.

[DDT]

Начнём с кубика Рубика 2x2x2.


Максимальное количество возможных ситуаций: 8! * 3⁷ / 24 = 3 674 160
Типы элементов: 8 углов, которые могут быть расположены в любом порядке и иметь до трёх возможных ориентаций.

Наиболее популярный метод решения:

• Сборка углов нижнего слоя;
• Ориентация + расстановка углов верхнего слоя (в любом порядке).

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

Шаг 0. Выбор первой грани.


Первым делом, необходимо изучить каждую грань — часто после перемешивания, 2, 3 и даже 4 угла могут оказаться на своих местах.
После этого, головоломку необходимо перехватить так, чтобы выбранная грань стала передней.

Шаг 1. Сборка одной стороны/грани.


Теперь, мы будем искать элементы этой грани и ставить их на свои места.

Для поиска будем использовать такой алгоритм:

• Ищем угол на верхней грани: вращаем её 4 раза и проверяем, не объединился ли в пару какой-то угол передней грани и верхней грани.
  Если углы не объединились, то продолжаем перебор. Иначе, докручиваем верхнюю грань, при этом запоминая, куда ушёл найденный угол и завершаем подбор;
• Ищем угол на правой грани: вращаем её 4 раза и проверяем, не объединился ли в пару какой-то угол передней грани и верхней грани.
  Если углы не объединились, то продолжаем перебор. Иначе, докручиваем верхнюю грань, при этом запоминая, куда ушёл найденный угол и завершаем подбор;
• Ищем угол на нижней грани: вращаем её 4 раза и проверяем, не объединился ли в пару какой-то угол передней грани и верхней грани.
  Если углы не объединились, то продолжаем перебор. Иначе, докручиваем верхнюю грань, при этом запоминая, куда ушёл найденный угол и завершаем подбор;
• Ищем угол на левой грани: вращаем её 4 раза и проверяем, не объединился ли в пару какой-то угол передней грани и верхней грани.
  Если углы не объединились, то продолжаем перебор. Иначе, докручиваем верхнюю грань, при этом запоминая, куда ушёл найденный угол и завершаем подбор;
• Если в процессе ни один угол не был найден и при этом передняя грань/сторона не собрана, то поворачиваем переднюю грань по часовой стрелке и начинаем перебор заново.

После того, как мы нашли угол передней грани, который расположен неправильно, возможно три ситуации:

• Угол стоит на своём месте, но повёрнут неправильно.
  В таком случае, нужно перехватить головоломку так, чтобы передняя грань оказалась справа снизу, а затем повторять [R, U], пока угол не будет ориентирован правильно (не более 4 раз);
• Угол находится на задней грани.
  В таком случае, нам нужно довернуть переднюю/заднюю грань так, чтобы нужный угол оказался позади того места, куда он должен встать, а затем перехватить головоломку так, чтобы передняя грань стала нижней, а место под угол оказалось справа и снизу. После чего, повторяем [R, U], пока угол не встанет на своё место (не более 5 раз);
  
• Угол находится на передней грани, но не на своём месте. В таком случае, нужно два раза проделать предыдущий алгоритм: сначала убрать угол с передней грани, а затем поставить его на своё место.

Данные действия нужно повторять до тех пор, пока все углы не станут на свои места.

Возможны ситуации, когда после перебора всех граней, передняя грань всё ещё остаётся разобранной — нужный угол находится на передней грани, но не на своём месте или неправильно ориентирован.
В таком случае, нужно переместить все углы передней грани, не стоящие на своих местах на заднюю грань, используя уже известный нам [R, U].

Приведу пару примеров сборки одной грани на классическом кубике Рубика 2x2x2: пример сборки красной грани, пример сборки белой стороны.

Шаг 1.1. Перестановка углов на передней грани.


Иногда, при сборке головоломок, может выпасть ситуация, когда углы передней грани расположены на ней, правильно ориентированы, находятся в неправильном порядке.
Их так же можно переставлять алгоритмом [R, U], но есть более короткие решения:

• Обмен левого и правого угла: моё решение, решение из метода Морозова;
• Обмен диагональных углов: моё решение, решение из метода Морозова.

Шаг 2. Ориентация углов.


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


Теперь, необходимо выбрать два угла, ориентированные неправильно (или один угол, ориентированный неправильно, а второй выглядящий одинаково, не зависимо от ориентации).
После этого, необходимо выполнить один из этих алгоритмов:

• Смена ориентации левого верхнего переднего и правого верхнего переднего угла: [[R': D2] [F: D2], U'];
• Смена ориентации правого верхнего переднего и левого верхнего заднего угла: [[R': D2] [F: D2], U2]

Где [R': D2] [F: D2] грязно меняет ориентацию одного угла на верхней грани, а U/U2/U' и отмена этого алгоритма меняет ориентацию второго угла.

Для того, чтобы проверить, что угол был ориентирован правильно, достаточно повернуть верхнюю грань 4 раза. Если в процессе количество углов, вставших на свои места увеличилось по сравнению с тем, которое было до выполнения алгоритма, то мы правильно ориентировали хотя бы ещё один угол.

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

Пример ориентации углов.

Шаг 3. Перестановка углов.


Этот этап решается всего одним алгоритмом — 3-циклом углов: [F2: (R2 D' L2 D)2] в разных комбинациях.

Тут я предлагаю воспользоваться методом Морозова и решать этот этап так:

• Вращаем верхнюю грань, пока как можно меньше углов не окажутся на своих местах (0 или 2);
• Если не на своих местах оказались 2 угла, то поворачиваем верхнюю грань по/против часовой стрелки;
• Используя алгоритм из пункта 1.1, решить пары несобранных углов. Обратите внимание на то, что алгоритм перемешивает элементы как верхнего, так и нижнего слоя, так что нужно обязательно выполнить его два раза, чтобы нижний слой собрался.

Теперь рассмотрим примеры сборок.

Сборка обычного кубика Рубика 2x2x2.

В будущем я пополню это сообщение другими примерами сборок.

[DDT]

Начнём с кубика Рубика 2x2x2.

Отмечу, что абсолютно все методы, описанные тут не требуют 100% следованию им. Если вы видите, что какую-то ситуацию можно решить проще, чем подбором, решайте её простым способом.
Так же можно придумать бесчисленное количество алгоритмов, которое может быть полезно в сборке, но не упомянуто в теме.

Например, когда на последнем слое не ориентировано 3-4 угла, можно применить такой алгоритм: [R: U] U [R, U2].
Или, использовать для обмена углов специальный алгоритм, например: (D' R2 U R2 U' R2) U' (D R2 U' R2 U R2).