Как решить Ханойскую башню с 8 стержнями?

Question

[dimaQd]

как решить на python ханойскую башню с 8 стержнями. В интернете только 3 или 4, не более. Подскажите алгоритм
Необходимо вычислить, за какое минимальное количество итераций переместятся все диски на шпиндель номер 1 по следующим правилам:
а) За одну итерацию можно переместить не более одного диска
б) Диски можно класть только с большего на меньший
в) Со шпинделя номер 8 можно перекладывать диски только на шпиндели 7 и 6
г) Со шпинделя номер 1 можно перекладывать диски только на шпиндели номер 2 и 3
д) Со шпинделей от 2 по 7 можно перекладывать диски только на два соседних шпинделя.

Comments

[dimaQd]

Пишу gui процесса на pyqt, вот добрался до размещения дисков и шпинделях и завис)

[shurshur]

Эта задача не про рисование шпинделей, а про алгоритмы.

[mkone112]

shurshur, но визуализация все равно хорошая штука.

[hint000]

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

[Akina]

В интернете только 3 или 4, не более.

А какая собсно разница, сколько шпинделей в задаче? Если решение корректно, то в нём достаточно просто поменять 3 (или 4) на 8 и получить готовое решение... а рекурсивная процедура вообще не должна оперировать какими-либо явно заданными значениями - только переданными в переменных.

[Wataru]

Какие-то аццкие ограничения. Обычно такая задача дается, когда можно перекладывать на любой шпиндель. Особенно дикие ограничения для шпинделей 2-7. Там точно можно только на 2 соседних (по одному слева и справа) перекладывать?

В таком виде длинная цепь из промежуточных шпинделей вообще не влияет на алгоритм. Будь их хоть 100 - все, что вы можете с ними делать - это перекладывать диск с одного конца до другого, а там уже решать задачу для 3-х шпинделей.

[dimaQd]

Wataru, Точно такие адские ограничения :( Я правильно понял, что мне нужно сделать так, чтобы диски были на 3х шпинделях, а потом обычным алгоритмом для 3х дорешать?

[gareev08]

Здравствуйте, у вас случайно еще не сохранилось решение данной задачи (именно в графическом виде)?

Answer 1

[Wataru]

Подобно задаче о 4-х шпинделях. Чтобы переместить самый большой диск на последний шпиндель, сначала надо все меньшие диски куда-то деть. Можно их парковать на 2-ом шпинделе или на 8-ом. Потом подвигать последний диск до 7-ого шпинделя, потом перепарковать часть с 8-ого на 6-ой и подвигать последний диск. Потом назад с 6-ого на 8-ой и оставшиеся со 2-ого на 8-ой. И надо перебрать все варианты - сколько дисков куда пихать.

В итоге пишите следующию функцию: переместить n дисков с i-ого шпинделя на j-ый при возможно запрещенных шпинделях из заданной маски. Там перебираете, куда класть сколько-то верхних дисков и на какой шпиндель. рекурсивно считаете, сколько это займет шагов, плюс сколько шагов чтобы переместить оставшиеся диски в конец, плюс, сколько переместить верхние диски с временного шпинделя в конец. Если остался один диск, то над аккуратно смотреть, а можно ли его вообще переместить с заданными запрещенными шпинделями (иначе вренуть +бесконечность, или что-то очень большое).

Чтобы это работало быстро, надо делать мемоизацию и не считать функцию с одним и тем же набором параметров несколько раз.

Интересно, что ответ растет гораздо медленее, чем для 3-х шпинделей:

6
13
22
36
55
82
117
163
219
289
375
484
623
800
1024
1300
1651
2090
2643
3333

Comments

[dimaQd]

Благодарю, стало предельно понятно!