Способ вычисления полного тетрадного поворота кубика Рубика
Я работаю над реализацией алгоритма Thistlewaite для решения кубика Рубика, и теперь я столкнулся с проблемой тетрадных поворотов. Благодаря этому ответу я понимаю, что это такое и как они уменьшают количество состояний в фазе 3, но моя проблема заключается в том, чтобы найти способ вычислить общий тетрадный поворот куба только по его состоянию.
Я реализую этот алгоритм не с помощью поиска в ширину, и поэтому я не могу просто использовать более сильное условие, найденное здесь и здесь, чтобы узнать, закончил ли я этап 3, поскольку это бесполезно для меня. Я делаю это так, что предварительно вычисляю таблицы поиска и смотрю в них, чтобы узнать, как решить определенное состояние. По этой причине мне нужно полностью охарактеризовать информацию, необходимую для различения различных состояний стадии 3. У меня уже есть угловые тетрады, срезы краев и четность, последнее, что мне нужно, это способ выразить тетрадный поворот состояния (или любую аналогичную информацию). Лучше всего было бы просто указать значение между 0, 1 или 2 и использовать его для описания общего скручивания.
Надеюсь, мой вопрос ясен, а если нет, не стесняйтесь задавать вопросы в комментариях, я постараюсь объяснить его дальше.
Ответы
Достаточно сложно извлечь эту информацию непосредственно из текущего местоположения угловых элементов. Безусловно, самый простой способ - попытаться решить эти угловые части, используя только пол-оборота (игнорируя кромочные элементы), и посмотреть, как далеко вы продвинетесь.
Пока я предполагаю, что угловые части уже расположены на своих правильных тетрадных орбитах {UFR, UBL, DFL, DBR} и {UFL, UBR, DFR, DBL}. Вы можете собрать части одной тетрады очень легко, не более полуоборота на каждую фигуру, всего не более 3 ходов. Например, решите DBR, используя не более одного из {D2, B2, R2}, затем DFL, используя не более одного из {F2, L2}, и, наконец, UBL, используя {U2}, если необходимо, что также оставляет UFR решенным.
Затем вы решаете одну часть второй тетрады, например DBL, используя одну из последовательностей ходов {F2 L2 F2 U2, U2 F2 U2 L2, L2 U2 L2 F2}. Эти последовательности ходов выполняют двойную замену четырех частей второй тетрады и являются единственными возможными перестановками, при которых первая тетрада остается неизменной.
Остается три нерешенных части: {UFL, UBR, DFR}. Они могут быть в любой из 3! = 6 перестановок. Эти 6 возможностей представляют собой тетрадное скручивание в сочетании с перестановочной четностью, поэтому, если вы сопоставите эту перестановку с числом от 0 до 5, вы закодируете как перестановочную четность, так и тетрадное скручивание в одно число.
Для алгоритма Thistlethwaite вы, вероятно, захотите закодировать произвольную позицию третьего этапа алгоритма. Это должно быть сделано последовательно, под этим я подразумеваю, что если две разные позиции переводятся в четвертую стадию одной и той же последовательностью перемещений (т.е. после применения последовательности перемещений к этим позициям, они обе становятся решаемыми, используя только пол-оборота), тогда эти две позиции должны иметь одинаковую кодировку для этапа 3.
Предположительно ваша программа перечисляет угловые положения куба в определенном фиксированном порядке. Например, у вас может быть массив длиной 8, представляющий местоположения в порядке
UFR , UFL, UBL , UBR, DFR, DFL , DBL, DBR .
Я выделил жирным шрифтом те места, которые представляют одну из тетрад, с индексами 0, 2, 5, 7 в массиве. Возможно, вы выбрали другое соглашение об упорядочивании в своей программе, но метод тот же.
Предположим, теперь у вас есть произвольная позиция куба стадии 3, некоторая случайная перестановка этих 8 углов, например:
UBR, UBL , DBR , DFR, DFL , UFR , UFL, DBL.
Простой последовательный способ разделить части на две тетрады - буквально разделить два типа частей без изменения их относительного порядка:
UBL , DBR , DFL , UFR
UBR, DFR, UFL, DBL.
А затем поместите их в массив хранения по порядку, каждое в свой правильный набор тетрадных местоположений. Таким образом, первый набор входит в индексы 0,2,5,7, второй - в индексы 1,3,4,6.
УБЛ , УБР, ДБР, DFR, UFL, DFL , DBL, UFR .
Теперь вы можете применить технику решения, которую я объяснил в начале, чтобы получить последовательное кодирование позиций тетрадного поворота и четности.
Вышеупомянутое предполагает, что вы используете единый стандартизированный способ представления куба и применяете к нему движения. Вместо этого вы можете захотеть сохранить два отдельных списка тетрадных частей как упрощенное представление этой позиции и переставлять их напрямую по мере решения, чтобы извлечь кодировку twist + parity.
Вы можете взглянуть на некоторые программы на этом старом конкурсе программирования кубов , хотя я не уверен, что они будут ужасно полезными, поскольку они написаны для краткости, а не для разборчивости.