хочу рассказать об очень крутом проекте
TWSearch (Twizzle Search — Twisty puzzle search library) автор Tomas Rokicki.
эта программа ищет алгоритмы для комбинаторных вращательных головоломок. и самое главное ей поддаются плоские головоломки с кругами, а также аналоги венгерских колец.
страница проекта на гит:
https://github.com/cubing/twsearchскомпилированные файлы под линукс и виндовс:
https://sourceforge.net/projects/geraniumspot/files/TWSearch/по какой-то причине автор не распространяет исполняемые файлы.
форк проекта откуда взял скомпилированные файлы
https://github.com/b10101101/twsearchна странице проекта есть достаточно подробная документация, а в папке Samples много примеров файлов с описанием структуры головоломок. но разобраться сходу достаточно сложно. к тому же утилита консольная, надо запускать с командной строки, и правильно подготовить исследуемые вами файлы головоломок.
на данный момент здесь есть arecibo, eliac, vertushka.
https://github.com/cubing/twsearch/tree/main/samples/mainа на зарубежном форуме можно почитать статьи как с помощью twsearch решили две сложные головоломки :
Arecibo:
https://twistypuzzles.com/forum/viewtopic.php?t=40276Fomalhaut:
https://twistypuzzles.com/forum/viewtopic.php?t=40379--------------------------------------------------------------------------------------------------------
приведу пример анализа для одной несложной головоломки: возьму за основу Double Five от Володи Ярославского
значимыми для решения являются только большие треугольники. их всего 10 штук. но есть сложность - каждый надо поставить на свое место, а также надо учитывать ориентацию
чтобы запустить решатель, вам надо задать в файле описание вашей головоломки.
суть описания в том, чтобы задать все типы частей, указать их количество и возможную ориентацию.
а также задать какие части перемещаются и как ориентируются при разных поворотах.
утилита вычисляет все возможные орбиты и может найти много полезного для решения.
1. число бога головоломки, 2. набор формул для простых комутаторов (2 и 3 циклы, 2*2 перестановки),
3. если вы зададите ей определенное состояние, то она найдет для него оптимальное решение,
4. а если зададите ей вашу формулу, то она ее оптимизирует и найдет кратчайший вариант для этой перестановки.
умея получать от программы этот базовый набор, вы сможете решить почти любую головоломку. давайте все это рассмотрим:
для начала я объясню как делать файл с описанием головоломки без учета ориентации деталей.
для большинства головоломок с кругами ориентация частей не нужна.
это нужно для 3д головоломок, а также для головоломок с маркерами, как здесь.
используем файл для поиска простых формул, не учитывающих ориентацию частей. формулы для разворота частей будем искать потом.
сделаем простой текстовый файл с описание структуры: doublefive.tws
Name doublefive
Set Triangles 10 1
Solved
Triangles
1 2 3 4 5 6 7 8 9 10
End
Move L
Triangles
3 2 6 1 5 9 4 8 7 10
End
Move R
Triangles
1 4 3 7 2 6 10 5 9 8
End
объясню по порядку его дерективы
Name doublefive : задаем имя головоломки
Set Triangles 10 1 : задаем вид частей: название, количество и количество возможных ориентаций (0 - не учитывается, 1 и более - количество ориентаций). этих секций может быть несколько - для каждого вида частей.
Set Triangles 10 3 : если мы делаем описание головоломки с ориентацией частей, тогда вместо 1 надо будет указать 3
многострочные секции:
Solved / End : тут содержится поблочно описание частей в решенном состоянии
далее идет блок с описанием состояний каждого вида частей. в блоке будет 2 или 3 строки.
Triangles / 1 2 3 4 5 6 7 8 9 10 - имя части (указано выше), а также номера частей начиная с 1 (нумерация в каждом блоке начинается с 1). обратите внимание: я указываю для каждой части уникальный номер - это нужно для маркированных головоломок.
если же головоломка цветная, без маркеров - тогда описать ее можно более просто.
Triangles / 1 1 1 1 1 6 6 6 6 6 - те мы говорим, что на заданных местах будут блоки из одинаковых частей, сгруппированные по цвету. те решение будет проще.
но если у нас есть маркеры, которые имеют ориентацию (например цифры), то у нас будет не только 10 уникальных частей, но еще надо задать их ориентацию.
Triangles / 1 2 3 4 5 6 7 8 9 10 / 0 0 0 0 0 0 0 0 0 0 - в таком случае в блок надо добавить третью строку, где каждому номеру части стоит соответствующий индекс ориентации. если у нас количество ориентаций выше указано 3, то индексы будут от 0 до 2.
следующие секции:
Move / End - эта секция будет задавать вращения групп частей - их может быть несколько
Move Group - задается имя группы. оно потом будет использовано в найденных формулах
Triangles / 3 2 6 1 5 9 4 8 7 10 - задаем положение всех частей после заданного поворота.
Triangles / 3 2 6 1 5 9 4 8 7 10 / 1 0 1 1 0 1 1 0 1 0 - если у нас есть ориентации частей, то добавим строку с индексом ориентации.
вот тут указаны номера частей после поворота левого круга. стоит отметить, что не нужно задавать настройки для поворотов против часовой стрелки или двойных поворотов.
вот пример файла, с настроенными ориентациями частей
Name doublefive
Set Triangles 10 3
Solved
Triangles
1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0
End
Move L
Triangles
3 2 6 1 5 9 4 8 7 10
1 0 1 1 0 1 1 0 1 0
End
Move R
Triangles
1 4 3 7 2 6 10 5 9 8
0 1 0 1 1 0 1 1 0 1
End
----------------------------------------------------------------------------------------------------------------
пришло время запустить нашу утилиту и посмотреть что она может.
учтите: у программы много параметров (все они описаны на главной странице в гит). многие параметры зависят от регистра! те -А и -а это разные команды. не перепутайте!
для начала запустим ее для поиска число бога у данной головоломки. к сожалению здесь не все так просто, это очень ресурсоемкая процедура. например для версии без ориентации частей - она нашла число бога 12. а вот с версией с ориентацией она пока не справилась, нужно очень много памяти! возможно попозже я смогу найти компьютер помощнее. (спойлер: смотрите следующее собщение)
нужно запустить нашу программу с такими параметрами:
twsearch.exe -g -M 10000 -a 1 doublefive.tws - параметр -g это запуск поиска числа бога, -M тут мы указываем сколько памяти выделяется под процесс (по умолчанию 8гб), -a сколько вывести найденных вариантов.
программа выдает вот такой результат. тут видимо количество состояний после каждого поворота. мы видим что она остановилась на 12 поворотах - это и есть число бога. также она нашла 2088 максимально отдаленных от решенного состояний.
Dist 0 cnt 1 tot 1 in 0.016
Dist 1 cnt 10 tot 11 in 0
Dist 2 cnt 50 tot 61 in 0
Dist 3 cnt 250 tot 311 in 0
Dist 4 cnt 1234 tot 1545 in 0
Dist 5 cnt 5634 tot 7179 in 0
Dist 6 cnt 24768 tot 31947 in 0.015
Dist 7 cnt 102066 tot 134013 in 0.016
Dist 8 cnt 374966 tot 508979 in 0.094
Dist 9 cnt 1095994 tot 1604973 in 0.328
Dist 10 cnt 1631368 tot 3236341 in 0.937
Dist 11 cnt 390371 tot 3626712 in 0.344
Dist 12 cnt 2088 tot 3628800 in 0.016
Showing 1 antipodes.
Scramble noname
Triangles
3 2 1 4 5 6 7 8 9 10
End
но самое здесь интересное это найденные максимально далекие состояния
Scramble noname
Triangles
3 2 1 4 5 6 7 8 9 10
Endк тому же они сразу указаны в формате который понимает программа. если вы сохраните эти 4 строчки в отдельный файл, например "max.scr" и запустите:
twsearch.exe doublefive.tws max.scr - то программа найдет нашу первую формулу, которая ведет к заданному состоянию:
L R2 L' R2 L3 R2' L' R2 L R L3 R2
Found 1 solution max depth 12 probes 60665 nodes 60457 in 0.032 rate 1.89578
одна из перестановок 2-х частей
---------------------------------------------------------------------------------------------------------------
а теперь давайте перейдем к самому интересному и важному - к функции автоматического поиска различных формул
twsearch.exe -A doublefive.tws - просто запустите утилиту с такими параметрами. и наслаждайтесь тем что она находит для вас
Triangles/3p 16 (L R L2 R')4 (1:3 3:1 4:1) 12
Triangles/2p 60 (L R L3 R2')15 (2:1 3:1 5:1) 30
Triangles/2p 60 (L R L2' R3)15 (2:1 3:1 5:1) 30
Triangles/3p 16 (L R L' R2)4 (1:3 3:1 4:1) 12
Triangles/4p 4 (L R L' R')1 (1:6 2:2) 2
Triangles/2p 60 (L R2 L3 R3)15 (2:1 3:1 5:1) 30
....
Triangles/3p 8 (L R2 L' R2 L R2 L' R2)
Triangles/3p 8 (L R2' L' R2' L R2' L' R2')
Triangles/3p 8 (L2 R L2 R' L2 R L2 R')
...
Triangles/2p 10 (L R L2 R' L2' R2 L3 R' L R')
Triangles/2p 10 (L R L2' R L3 R2' L2 R L3 R')
Triangles/2p 10 (L R L2' R2 L2 R3 L2' R2' L R')
вот примеры работы некоторых формул:
1) трицикл - (L2 R L2 R' L2 R L2 R'); 2) двацикл - (L R L2' R2 L2 R3 L2' R2' L R')
как видим утилита вначале выдает очень длинные не оптимальные формулы. но потом постепенно начинает выдавать оптимальные алгоритмы.
стоит учитывать, что данные формулы могут менять ориентацию остальных частей, тк в файле не заданы ориентации.
если вы хотите сразу чистые формулы. то запускайте для анализа сразу второй файл. тогда будут затрагиваться только указанные части. но формулы будут немного длинее.
давайте посмотрим как можно оптимизировать наши формулы.
вот например я нашел вручную формулу, которая делает чистый трицикл, не нарушая ориентации остальных частей. но она достаточно длинная.
twsearch.exe doublefive.tws tri.scr - создаем файл "tri.scr" и запускаем анализатор, указав описание головоломки с ориентациями
ScrambleAlg TRI
L R L2 R3 L' R L R' R3 L2' R' L' R L2 R3 R L' R' L R3 L2' R'
End
получаем на выходе более короткий алгоритм!
L2 R' L2' R2 L R' L R' L' R L R L2' R'
Found 1 solution max depth 14 probes 332062 nodes 332055 in 0.688 rate 0.482648
а теперь давайте найдем этот же трицикл, просто указав в файле искомое состояние
обратите внимание, что я указываю ориентацию всех частей - 0. но на деле я могу задавать и нужные ориентации для каждой части
twsearch.exe doublefive.tws tri.scr - запускаем поиск и получаем новый алгоритм
R3 L2 R2 L' R2 L R2 L' R2 L' R3
Found 1 solution max depth 11 probes 48568 nodes 48563 in 0.062 rate 0.783355
а теперь давайте попробуем найти формулу для поворота двух частей на месте, без перемещения деталей.
Scramble TRI
Triangles
1 2 3 4 5 6 7 8 9 10
1 2 0 0 0 0 0 0 0 0
End
обратите внимание что части вращаются парами +/-
twsearch.exe doublefive.tws tri.scr - задаем в файле только изменение ориентации частей.
L2 R' L2' R2 L R' L R' L' R L R L2' R'
Found 1 solution max depth 14 probes 332062 nodes 332055 in 0.656 rate 0.506192
на этом статью заканчиваю. весь базовый и необходимый функционал рассмотрели. желаю вам интересных экспериментов!
