Как решать подобные задачи?
На графе чего?
Мы же не можем перемещать только одну точку забывая обо всех остальных.
Одна вершина графа - одно распределение чисел по доске.
Все вершины графа - все возможные распределения чисел по доске
Это множество определяется независимо от операций. Теоретически, могут быть состояния (вершины) которые будут недостижимы при некотором определении опеарций.
Можно как-то так реализовать рекурсивно поиск в ширину:
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:
- Вверху это не рекурсивный алгоритм, а просто цикл, но можно конечно рекурсивно без цикла
- Он не находут путь, а решает задачу достижимости. Для пути логика точно такая же, но вместо узлов надо хранить пути. Операции применяются к последнему узлу пути и возвращают более длинный путь
- Надо конечно проверять чтобы не попасть в уже пройденный узел. Например, хранить пройденные узлы а также избегать чтобы операция возвращала предыдущий узел (вращать в обратном направлении).
-
Это стандарный алгоритм поиска в ширину. Наверняка можно как-то оптимизировать, а иначе комп может загнуться