Построить алгоритм и граф решения задачи "Ханойские башни" при числе шпилей 4

на любом языке программирования.

С четырьмя и более стержнями

Хотя вариант с тремя стержнями имеет простое рекурсивное решение,
оптимальное решение Ханойской башни с четырьмя стержнями является нерешённой проблемой.
Из этого не следует, что в случае четырёх и более стержней не существует алгоритма
для нахождения оптимальных решений.
Достаточно представить головоломку в виде неориентированного графа,
сопоставив размещениям дисков вершины, а ходам — рёбра, и использовать любой алгоритм поиска
(например, поиск в ширину) для нахождения оптимального решения.
Однако эффективной стратегии определения оптимального решения для большого числа дисков нет:
количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками,
остаётся неизвестным.
Существует предположительно оптимальный алгоритм Фрейма — Стюарта, разработанный в 1941 году.
Связанная гипотеза Фрейма — Стюарта утверждает, что алгоритм Фрейма — Стюарта всегда
находит оптимальное решение.
Оптимальность алгоритма Фрейма — Стюарта была экспериментально проверена вплоть
до 30 дисков на 4 стержнях[5].

Алгоритм Фрейма — Стюарта, дающий предположительно оптимальное решение
для четырёх (или более) стержней, описывается следующим образом:
Пусть n — количество дисков.
Пусть r — число стержней.
Определим T(n,r) как наименьшее число ходов, необходимое для переноса n дисков
с использованием r стержней.
Алгоритм может быть описан рекурсивно:
Для некоторого k, 1<=k<n, перенести верхние k на стержень i,
не являющийся ни начальным, ни конечным стержнем, затратив на это T(k,r) ходов.
Не используя стержень i, содержащий теперь верхние k дисков,
перенести оставшиеся n-k дисков на конечный стержень, используя только
оставшиеся r-1 стержней и затратив на это T(n-k,r-1) ходов.
Наконец, переместить верхние k дисков на конечный стержень, затратив на это T(k,r) ходов.
На весь процесс требуется 2T(k,r)+T(n-k,r-1) ходов.
Значение k выбирается таким образом, чтобы значение этого выражения было минимальным.