Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Кратко, о чем речь
Речь идет о головоломках по типу кубика Рубика (за подробностями - в первую статью серии).
Алгоритмом Бога на пазле (от англ. "puzzle" - головоломка) - это кратчайший путь от состояния А до В
Антипод - самое запутанное состояние пазла (одно из множества)
Число Бога (далее ЧБ) - это (всё эквивалентные формулировки):
=максимальная длина худшего Алгоритма Бога (далее АБ)
=минимальное число, за которое гарантировано можно собрать пазл
=дальность антиподов "по прямой"
Прелюдия
В 11 классе во время подготовки к ЕГЭ я был вдохновлен неравенствами с параметром. На столько вдохновлен, что подумал: а можно ли как-то прикрутить это к моему хобби? Так в моем мозгу возникло желание создать "алгебру для куба, так, чтобы формулы можно было упрощать по тем же законам коммутативности, ассоциативности и дистрибутивности". Сам того не понимая, я взялся за задачу, эквивалентную задачи поиска АБ...
И вот, буквально пару дней тому во время очередного 50-километрового похода мне удалось придумать окончательную стратегию его поиска. Только представьте: я могу найти АБ!! (при некоторых условиях, о чем ниже). Открыт вопрос (поступает от читателей), является ли АБ задачей равенства классов полиномиальный и неполиномиальных задач...
Обрисую некоторые понятия, которые нам пригодятся
0.Конфигурация - набор элементов.
1.Пазл (от англ. «puzzle» - головоломка) - конструкция из элементов, образующих слои (конфигурация) и перемещаемых доступными перестановками.
2.Бандажиг (процесс) - конструирование пазла путем ограничения другого.
3.Бандаж (спарадический результат бандажинга) - пазл, раз от раза, момент от момента, состояние от состояния имеющий разный перечень доступных перестановок.
4.Блок - склейка элементов пазла (конфигурация) для конструирования бандажа (те блок - один из видов его ограничения).
5.Элемент пазла - минимальная единица не бандажного пазла.
5.1 Свободный элемент - элемент бандажного пазла, не являющийся блоком.
6.Состояние элемента - совокупность его положения на пазле и ориентации на своем месте (я не смог выдумать более атомарное определение положению и ориентации).
7.Слой - множество элементов, смещаемых перестановкой только вместе.
8.Скрамбл, замес, паттерн (узор) - разобранное состояния пазла.
9.Алгоритм, формула, комбинация (не путать с «количеством комбинаций (состояний) на пазле» и «Алгоритмом Бога») - композиция из перестановок, определенных на пазле.
10.Доступная перестановка - перестановка, не разрушающая ни одного блока и не нарушающая ни одного другого ограничения на бандаже. На небандажах любая перестановка в любой момент времени является доступной, что можно считать определением небандажа.
11.Запрещенная перестановка - перестановка, разрушающая блок или нарушающая ограничение пазла-бандажа.
12.Перехват - один из видов перестановки - смещающей одновременно все элементы и лишь меняющая ориентацию пазла в пространстве. При этом состояние пазла до перехвата и после считаются не одинаковыми, так как могут быть получены путем нескольких параллельных перестановок. Перехват является всегда доступной перестановкой.
13.Метрика перестановок - некоторые вариации определений перестановок и их подсчета. Так, например, можно задаться вопросом, является ли одним поворотом поворот грани кубика Рубика на 180 градусов, или двум? Или является ли поворот среднего слоя куба 3х3х3 одним поворотом, или двум боковых с последующим перехватом в обратную сторону. Или, в конце концов, разрешены ли как перестановка перехваты?
14.Метод - набор комбинаций (алгоритмов), которые, будучи применяемыми из разных состояний пазла, покрывают все его состояния (в этом случае можно сказать «метод полон»). То есть, если есть такое состояние пазла, из которого его невозможно собрать данным набором алгоритмов, методу нужна, как минимум, еще одна формула.
15.Вид элемента - множество взаимозаменяемых элементов путем алгоритмов. Каждый элемент одного вида можно поставить с другим этого же вида, и ни один элемент другого вида нельзя поставить на место элемента данного вида.
16.Чистая/грязная комбинация: комбинация для данного множества элементов, преобразующая их и только их, является чистой. Если комбинация меняет состояние элементов, не входящих в данное множество, она является грязной. Однако, чистота является субъективным, относительным, не абсолютным понятием - зависящем от внешних факторов и условностей или определений: так, просто поменяв множество элементов, включив в него те, которые относились к лишним, «грязным» элементам, формула станет чистой.
17.Флип(для 3д-ребер)/твист(для 3д-углов)/другой [многомерный] переворот - результат выполнения чистой комбинации, при котором некоторое число элементов одного и того же вида меняют ориентацию на своем месте. Если в результате при этом присутствуют прочие изменения, можно сказать «грязный флип/твист/…»
18.Х-цикл («Икс-цикл») - перестановка Х элементов одного и того же вида в N группах (например, трех парах - трижды-два-цикл). Опционально рассматриваются Х-циклы с попутными переворотами. 1*N-цикл можно считать переворотом N элементов на своем месте. Пример (трижды два) цикла с переворотом (две штуки): 3*2+1*2-цикл. Подчеркиваю: числа нельзя сокращать! 3 и 2 в первом произведении имеют разный тип! Как и 1 и 2 во втором.
19.Минпер (минимальная перестановка) - перестановка, меняющая минимальную группу элементов одного вида. Минперы могут быть 3-циклами (чистой перестановкой 3ех элементов одного вида), 2+2-циклом (чистой перестановкой двух пар элементов одинакового вида в каждой паре) или другими циклами (например 2+2+2-цикл на 4д-кубе, так как помимо ребер и углов там возникает еще один вид угла - 4д-угол)
20.Паритет - состояние, непокрываемое данным методом.
21.Алгоритм Бога (АБ, одна из абсолютных (неизменных, не зависящих ни от чего, кроме пазла) концепций) - кротчайший путь от состояния А некоего пазла до его состояния В. Состояниями А и В могут в данном случае быть абсолютно любые состояния: как собранные, так и разобранные. Таким образом возникает три вариации:
-Замес → собранное состояние
-Собранное состояние → паттерн
-Паттерн1→ паттерн2
22.Антипод (одна из абсолютных концепций) - самое далекое состояние от некоего другого. По умолчанию от собранного (то есть по умолчанию антипод - это «самое замешанное», «самое сложное» состояние).
23.Псевдо-антипод (относительная концепция, зависящая не только от пазла, но и от временной условности - метода его сборки) - наисложнейшее, наиневыгоднейшее состояние пазла для данного метода.
24.Число Бога (ЧБ, одна из абсолютных концепций):
=длина худшего Алгоритма Бога
=минимальное число, за которое гарантировано можно собрать пазл
=дальность антипода
25.Перечень Бога (ПБ, одна из абсолютных концепций) - множество всех Алгоритмов Бога от состояния А до состояния В. Например, один из антиподов - суперфлип (паттерн) - в силу того, что имеет очень много симметрий, очевидным образом, имеет и много АБ.
26.Метод Бога (МБ, одна из абсолютных концепций) - метод, имеющий формулами все Алгоритмы Бога. Иначе говоря, Метод Бога - это алгоритм поиска всех Перечней Бога.
27.Блок-билдинг - метод-приближение к Методу Бога, имеющий основной идеей сборку максимального числа элементов максимально интуитивно (без формул) как можно меньшим числом ходов (перестановок), а далее минимально возможными по длине алгоритмами.
28.Сборка бандажа в форму - установка всех его блоков (для блочного бандажа) в состояния, в котором они находились с собранном состоянии пазла. Оставшиеся при этом единичные элементы называются свободными. Сборка блочного бандажа в форму является, как правило, первым этапом его решения. Сборка свободных элементов формулами (в т.ч. коммутаторами и конжугатами) - вторым.
29.Аксиоматика пазла - набор утверждений, полностью его описывающих: перечень слоев (конфигураций), образующихся элементами (1-конигурациями), перечень блоков (/ограничений - тоже конфигураций) и доступных перестановок.
30.Аксиоматическая функция - функция, задающая аксиоматику некоторого пазла.
31.Шаблонная теорема - теорема, отвечающая на один и тот же вопрос в разных аксиоматиках.
Пример теоремы: «на кубике Рубика 3х3х3 за два перехвата в метрике stm можно переориентировать куб в любую из 24 ориентаций в пространстве».
Другой пример: «за 3 поворота в метрике qtm можно грязно преобразовать состояние любого ребра кубика Рубика 3х3х3 любыми образом. Проще говоря, за три хода можно грязно поставить любое ребро на любое положение в любой ориентации»
Первая теорема - о связи абсолютных концепций кубинга
Можно найти (абсолютные) антиподы пазла или части пазла (например, белого креста - первого этапа сборки по методу Джессики Фидрих, или, другой пример, - для блок-билдинга) путем создания метода, имеющего псевдо-антиподами, собственно, антиподы. Полагается, что к этому моменты мы уже создали и проверили метод поиска псевдо-антиподов (чистая комбинаторика). В результате это значит, что и сам метод должен быть абсолютным, а значит он должен быть Методом Бога.
Обратное суждение: найдя Метод Бога, мы тут же найдем и антиподы.
Также имеет место то, что длина любого АБ из любого ПБ из Метода Бога = ЧБ. Таким образом, найдя АБ - находим антиподы и ЧБ
Однако не все так просто. Забегая вперед, для создания АБ нам заведомо нужно ЧБ. То есть метод подсчета ЧБ по первой теореме заведомо бесполезен, и нам нужен другой метод. И помимо этого, нам нужен некоторый мостик между ЧБ и АБ.
АБ для всего куба (треха или другое) предполагается находить следующим методом:
1.Найти все грязные Алги Бога для каждой минимальной самостоятельной конфигурации (свободные элементы или блоки)
2.Сшить их наиболее оптимальным образом.
Следующий вираж: как научиться сшивать наиболее оптимально?
Для этого нам помогут аксиоматические функции. Суть следующая: каждый пазл задает свою аксиоматику, состоящую из 3ех пунктов:
1.Слои - конфигурации элементов, смещаемых только вместе группой
2.Доступные перестановки
3.Блоки/ограничители
После задания аксиоматики - развиваем эту математику, вычисляя теоремы шаблонным образом. Так, например, теоремы, которые мне удалось вычислить устно:
-ЧБ на перехватах для переориентации трехи любым образом в метрике stm = 2
-ЧБ для смены состояния любого ребра трехи любым образом в метрике qtm = 3
+ Теоремы, уже известные человечеству:
-ЧБ для креста трехи (Фридрих) = 8
-ЧБ для трехи = 20
-ЧБ для двушки = 11
Таким образом, теоремы как бы отвечают нам на одни и те же вопросы в разных аксиоматиках (например, для меги, икосаэдра или октаэдра FTO значения теорем могут сильно разниться). Вопросы, на которые отвечают теоремы, в основном следующие:
-ЧБ
-число сосnояний
-число псевдо-антиподов и, по возможности (при достаточных мощностях вычислительного аппарата), сами их конфигурации
При этом теоремы будут развиваться "пластами": например, на первом пласте:
-ЧБ для смены состояния ребра (привел выше)
может базироваться следующий пласт:
-а каково ЧБ для смены взаимного состояния двух ребер?
-Следующие пласты: трех?
-И, наконец, 4ех то бишь креста.
Последним пластом может стать универсальный вопрос:
-Каково ЧБ соединения данной конфигурации из N элементов, разбросанных по пазлу любым образом? (этой конфигурацией могут быть как два ребра, так и крест по Фридрих или вообще весь куб).
Но для этого необходимо уметь находить ЧБ в теоремах. Как это сделать?
Вторая теорема - о стратегии поиска абсолютных концепций кубинга
Итак, давайте немного притормозим и подведем порядок:
Человек -> аксиоматическая функция -> аксиоматика -> теоремы -> ЧБ -> АБ -> ПБ -> МБ -> антиподы
Итого, нам нужна прослойка между аксиоматикой и ЧБ, который ищется в теоремах. ЧБ будем искать методом перебора. Но перебора не тупо всех состояний куба, разумеется. Наш метод будет куда оптимальнее. Обратим внимание вот, на какой факт:
множество конфигураций, из которых можно собрать то, для чего мы ищем ЧБ (скажем, креста или переориентаций однушки)
== (совпадает с)
множеством всех состояний пазла, которые можно получить, сделав ровно ЧБ ходов
(пояснение на два абзаца ниже)
Здесь очень! важным нюансом является то, что мы ищем не числа - а множества. Ведь и правда, даже если числа совпадают, не факт, что множества - тоже. Я очень надеюсь, что не бывает таких пазлов, где это так. Во всяком случае, привычных нам пазлов даже при всей математической точки зрения (например, можно попытаться выдумать "кубик Шредингера", у которого >=2 ЧБ) Доказать невозможность несовпадения множеств при совпадении чисел для привычных же пазлов можно попытаться от обратного.
Также важный нюанс: мы можем ускорить перебор чисел-кандидатов на ЧБ, устранив минимальные очевидно не могущие быть ЧБом числа. Например, думаю, всем очевидно, что ни 1, ни 2, ни 3 не может быть Числом Бога для трешки. Однако стоит вопрос о четкой оценке невозомжного минимума, а не по типу "всем и так очевидно".
Как говорил Ньютон, "примеры важнее правил" и как говорит один мой знакомый, "давайте доведем ситуацию до абсурда - и поймем её смысл". Ударимся в самые основы - кубик 1х1х1. Я не шучу, перед тем, как писать эту статью мы с друзьями пытались посчитать ЧБ для однушки, и у нас не получалось! На самом деле, мы изначально и так знали, что ЧБ=2, это и так интуитивно понятно, но мы полдня пытались посчитать до этих 2ух :D
Hidden text
Только математики так могут!
Первое число для однушки = число исходных конфигураций, из которых мы идем к собранному кубу 1х1х1 == число его ориентаций в пространстве == 24 (6*4 - 6 граней на первом месте и еще 4 возможные после фиксации в пространстве первой)
Второе число = число возможных ситуаций на дальности в 2 хода. И вот тут начнется самое интересное: интуитивная логика говорит, что, чтобы получить второе число, достаточно возвести число перестановок в степень хода: 9 перестановок (декартово произведение: [x,y,z] х [по часовой, против, на 180]) ^ 2 хода == 81
Но погодите. Если ЧБ действительно = 2, то 81 должно быть = 24. Что-то не так. Мы потратили почти целый день и расписали все вот в такой выкладке:
Hidden text
6 ситуаций (эквивалент одному недвойному перехвату):{x = x2 x '= x' x2x' = x2 x = x x2y = y2 y' = ...y' = y2 y =z = z2 z' =z' = z2 z =
} //6*2 = 12 комбинаций
3 ситуации (эквивалент одному двойному перехвату):
{
x2 = xx = x'x' = y2 z2 = z2 y2
y2 = yy = y'y' = ...
z2 = zz = z'z' =
} //3*4 = 12 комбинаций
1 ситуация (самоотмена)
{0 = xx' = x'x = x2x2 = yy'...} //1*9 комбинаций
8 ситуаций (эквиваленты вращению вокруг угла):
{
xy = yz = zx
//еще 7 углов
} //8*3 = 24 комбинаций
6 ситуаций (эквиваленты диагональному перехвату):
{
x2 y = y' x2 = z2 y' = y z2
//и еще 5 диагоналей
} //6*4 = 24 комбинаций
6+3+1+8+6=24
(6*2 = 12) + (3*4 = 12) + (1*9 = 9) + (8*3 = 24) = (6*4 = 24) = 81
Какие выводы мы можем заключить из этого примера?:
1) 57 лишних ситуаций образовались там, где одно и то же состояние получаемо >1 формулой
2) Для того, чтобы их исключить алгоритмически (мы же помним, что все теоремы обязаны быть шаблонными, а не "ручными", как в этом примере), надо исключить все циклы и самоотмены (по типу xx')
3) С самоотменами все ясно - их можно исключить, просто глядя на формулу, для этого не нужно много ресурса
4) С циклами все интереснее. Нам не надо считать все циклы на длине предполагаемого ЧБ! Нам достаточно посмотреть на последний ход, и спросить себя: "не замыкает ли он цикл?.."
5) Для этого нам надо /-знать-/ (не считать, а именно /-знать-/) все состояния на N-1ом ходу. Для оптимизации нам надо как-то уйти от поиска конфигураций к поиску чисел.
6) Для этого воспользуемся следующей леммой:
Лемма - о поиске числа итераций любого цикла (циклической комбы)
Пусть у нас есть некая комбинация и пусть она определена на пазле с (внимание!) конечным числом состояний (можно рассмотреть и иные - как говорится, бумага все стерпит). Тогда, выполняя её много-много раз, мы, очевидным образом придем в начальное состояние.
Многие новички делают из этого неверный вывод, что, если крутить куб одинаково долго-долго - он соберется. Нет, он соберется только в то же состояние, с которого вы начинали. Если это было разобранное состояние - то в него и попадет. Да, вы можете попытаться вычислить такую длиннющую комбинацию, чтобы она проходила по разу каждое положение. Такая комбинация носит название Алга Дьявола, и на трешке отсутствует.
Лемма отвечает на следующий вопрос: сколько раз надо выполнять комбинацию, чтобы она полностью замкнулась? Ответ: считаем число циклов для возврата в начальное состояние для каждого отдельно взятого элемента и находим НОК всех чисел.
Возвращаясь к ЧБ, нам надо исключить циклы, а их теперь можно найти, чисто визуально глядя на формулу, и почти ничего не представляя в голове:
Вычерпываем из комбинации максимальную часть, максимально похожую на цикл. Например: URFUUR - цикл URFU. Доделываем ходы FU. Невооруженным взглядом видно: комбинация замкнулась, но полностью ли? Считаем полный цикл комбинации URFU по Лемме выше. Сверяем цикл с числом повторений в исходной формуле. Если != - значит, не цикл.
Последним нюансом всей нашей линии вычисления будет следующее (это моя большая, к великому сожалению, уже неоправдавшаяся надежда): нет циклов с числом полных итераций == 1. Иначе говоря, все прочие циклы имеют некоторую симметрию относительно своей середины. Если же есть асимметричные циклы, это значит, что фактически любая комбинация может быть циклом. Напоминаю, что для цикла нам надо посчитать НОК, а значит, просчитать движение каждого элемента. Это долго. Но если мы считаем лишь "похожее на цикл", это уже меньше. Если же циклом может быть все, нам снова нужно просчитывать весь граф состояний. Увы и ах. А контрпримером к этой маленькой надежде является тот же самые пресловутый куб 1х1х1, а именно цикл x2 y2 z2 и иже с ним.
Итог!
Еще раз опишу подробно всю схему:
1.Выбор пазла
2.Задание аксиоматики аксиоматическими функциями
3.Простраивание теорем
3.1 Подсчет числа исходных конфигураций
3.2 Перебор всех конфигураций на ЧБ ходов от забора до заката от минимально возможного числа до тех пор, пока не найдется
3.2.1 Для этого исключаем самоотмены
3.2.2 А также циклы
3.2.2.1 Для исключения циклов считаем НОК (перебор на кубе - затратная операция, которой надо по возможности максимально избегать) и оцениваем полноту завершения цикла чисто визуально (легкая операция)
3.3 Сравнение чисел из пп. 3.1 и 3.2
3.4 Если не равны, вернуться на п. 3.2
3.5 Если равны - вуаля, мы нашли ЧБ
4.Зная ЧБ для чего-то простого, пытаемся, в рамках теорем, развить следующие пласты
5.Зная все пласты теорем, находим АБ путем сшивания грязных АБ для атомарных конфигураций
6.ПБ
7.МБ
8.Антиподы.
9.Решаем задача Звезды и, возможно, Анти-Звезды Смерти (название исторически сложившееся).
О последней задаче читайте в ссылках
Ссылки
Первый мой выпуск о Первой теореме кубинга
Второй выпуск на канале о Второй теореме-стратегии кубинга
Выпуск о задаче Звезды и Анти-Звезды Смерти
