Мне эта задачка напоминает NP-полную задачу... Как-то было про изменение строки, даны n операций (например перестановка, циклический сдвиг и т.п.), найти самую короткую комбинацию операций. Но извиняюсь, уже не помню.

А так - брутфорсим нафик. 10 позиций, 10 символов, каждый символ может оказаться на любой позиции, символы не повторяются - максимум 10! вариантов, 3.628.800, каждый вариант представляем десятичным числом. (вместо 10 будем 0 использовать), 10.000.000.000 вариантов в 64-х битный лонг запихнём. Даже все варианты в память влезут. Вообще ерунда :)

Начинаем строить словарь с уже полученными значениями (чтобы не зациклиться) и дерево переходов.

Начинаем с 0123456789. Добавили словарь. Добавляем переход - крутим по циклу А - 8023456791. Смотрим, есть ли такое словаре? Нету. Сравниваем с ожидаемым - не, не совпало? Добавили в словарь, добавили новый узекл, добавили переход с маркировкой "А". Повторяем для Б, потом для С и Д. Сделали для всех операций? Есть узел не этом же уровне? Переходим к нему. Нет? Спускаемся на уровень ниже, если можем. Если новое число совпало с каким-то из словаря - "отменяем ход", рисуем "стоп, сюда не ходи". В общем поиск в ширину.

Это 100% можно сделать умнее, каждая трансмутация меняет цифры только в определённых позициях, но оно надо? меньше 4 миллионов вариантов отщёлкает ну... за 30 секунд? Так как мы в ширину ищем, то первый найденный путь и будет самым коротким.

А вот если будет 20 вариантов, то тут уже приплыли :) Придётся искать какой-нить 4/3 алгоритм.

Кнопки - вижу.

Что они делают - непонятно.

Ну ладно - те что по центру , видимо, поворачивают на... 1, 2, 3... 5... 100 секторов

А как вторая пара должна фунциклировать?

меньше 4 миллионов вариантов отщёлкает ну... за 30 секунд?

Есть у меня некоторое сомнение, что блутфорсный алгоритм выдаст оптимальный результат.

Результат то нужно еще повторить ручками на "реальной модели". А если там будет шагов 50, допустим?

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

Возможно пойти по шагам.

https://habr.com/en/companies/ruvds/articles/529780/

Кнопки - вижу. Что они делают - непонятно.

Не совсем так. Вернее совсем не так. Тут надо искать точку в пространстве траекторий, где траектория имеет определенное начало, определенный конец, и минимальную длину. Для этого

1) кодируем как-то все точки на графе. Одно состояние фишек на досек - одно состоняие. Всего N узлов графа. Если N=10! то траекторий будет дофигища.

2) задаем сам граф в виде множетсва пар e=(исходное состоняие ∈ N, конечное состоняие ∈ N) - каждая такая пара (стрелка графа) соответствует одной из 4 операций. Можно например явно определить таблицу из 2 колонок с 4*N строк. Но в зависимости от алгоритма (или памяти мало) можно и функцию определить. С 4 стрелками из каждой точки число траекторий будет уже существенно меньше чем дофигища. Но все равно много.

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

Вроде нашел как можно решать

https://habr.com/en/articles/322900/

Но это явно очень далеко от того что мне обычно требуется делать.

Применяем любимый алгоритм поиска кратчайшего пути на графе

На графе чего?

Мы же не можем перемещать только одну точку забывая обо всех остальных.

На графе чего?
Мы же не можем перемещать только одну точку забывая обо всех остальных.

Одна вершина графа - одно распределение чисел по доске.

Все вершины графа - все возможные распределения чисел по доске

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

Можно как-то так реализовать рекурсивно поиск в ширину:

find_next_nodes(input_nodes) -> output_nodes

out_nodes = []

for in_node in input_nodes:

out1 = op1(node)

out2 = op2(node)

out3 = op3(node)

out4 = op4(node)

out_nodes.append([out1, out2, out3, out4])

return out_nodes // Все что достижимо из указанных узлов

while(not_found)

current_nodes = find_next_nodes(current_nodes)

if target_node in current_nodes

not_found = False

То же самое можно и на Прологе.

Функции операций знают как "вращать", т.е. двигать несколько фишек по достке одновременно. Например, из аргумента 0123456789 вернуть 9876543210

(это неправильно, но просто как пример входа и выхода такой функции).

upd:

- Вверху это не рекурсивный алгоритм, а просто цикл, но можно конечно рекурсивно без цикла

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

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

- Это стандарный алгоритм поиска в ширину. Наверняка можно как-то оптимизировать, а иначе комп может загнуться

Все вершины графа - все возможные распределения чисел по доске

но у графа есть еще и ребра. То есть вначале как то строим монстрика, а после ищем самый короткий путь?

Да, должно вроде работать.

Угу. А теперь сравниваем с моим предложением, где решение находится в процессе построения монстра (с высокой вероятностью что нам не придётся строить его до конца).

есть три круга

-----

ну да - рацию надо установить на броневичке.

Еще раз - постановка задачи все еще не понятна.

Примеры непонятностей

- результат нажатия каждой кнопки

- какого результата нужно достичь

На графе чего?

-----

Там один граф!

И это ни графина, ни графини - нету.

upd:

-----

Вполне достаточно сказать - альфа-алгоритм (перебор с возвратом)

https://habr.com/en/articles/322900/

там довольно заумно, лучше ищите на слова simulated annealing в GSL есть такие решатели

OFF: Если бы у вас были бы дети, которые участвуют в BWINF, они бы вам быстренько решили - там организаторы помешаны на таких задачах

А теперь сравниваем с моим предложением

Сорри, не могу. Не доходит пока принцип работы

Да и оба решения - не та информация которую было интересно узнать.

Примеры непонятностей- результат нажатия каждой кнопки
- какого результата нужно достичь

лучше ищите на слова simulated annealing

поискал, но не вижу ничего общего

https://www.baeldung.com/cs/simulated-annealing

1. This involves defining the energy function, i.e., the function to minimize or maximize

2. A perturbation function is defined to generate new candidate solutions. This function should generate solutions that are close to the current solution but not too similar

Какая может быть функция чтобы переместить одну единственную фишку, может еще и можно придумать.

А вот связать всё вместе...

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

тут? пока не нашел

https://bwinf.de/biber/archiv/aufgabensammlung/

не, это бибер - он очень простой, надо https://bwinf.de/bundeswettbewerb/

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