Есть ли реализация на любом языке программирования немного изменённой головоломки «Ханойская башня»?

Question

[Валерий Макаров]

Нужна реализация на любом языке программирования немного изменённой головоломки "Ханойская башня". Единственное отличие от классики - перед перемещениями на первом стержне находятся все диски, но они при этом не упорядочены по диаметру, могуть быть в произвольном порядке. То есть необязательно выполняется условие "изначально меньшие диски расположены выше чем большие".

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

К сожалению в рунете ничего не обнаружил. Пробовал гуглить по иностранным сайтам, но ввиду моего слабого английского эти поиски успехом не увенчались. Своими силами составить программу тоже не получается. Кто подскажет, где найти?

Comments

[EvilMan]

Странное изменение. При таком изменении возможны ситуации, когда головоломка принципиально не может быть решена.

[EvilMan]

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

[jcmvbkbc]

@EvilMan Если ещё подумать, то обычный алгоритм существенно опирается на упорядоченность размеров в исходном состоянии. Но, да -- решение получается похожим.

[Валерий Макаров]

>>> Странное изменение. При таком изменении возможны ситуации, когда головоломка принципиально не может быть решена.

Строгого опровержения Вашего утверждения у меня нет. Я "поэкспериментировал" с различными вариантами (роль перемещаемых дисков выполняли несколько карт из колоды) и не встетил даже намёка на комбинации, которые невозможно упорядочить. Чисто эмпирически берусь утверждать, что любой набор дисков можно упорядочить.

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

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

Answer 1

[jcmvbkbc]

Я не уверен в оптимальности решения, но как минимум оно даёт корректные результаты: https://gist.github.com/jcmvbkbc/8050585

Answer 2

[Mrrl]

Назовем столбики A,B,C (A в начале непустой).
Введем операции:
А->С() - переложить один диск с А на С
top(A), top(C) - размер верхнего диска А или С. Если столбик пуст, то этот размер - MaxInt.
В->С(К) - переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхие диски А и С не меньше К)
swap() - переставить столбики В и С (или переименовать их- нам ведь все равно, где окажутся диски)
while(A) - цикл пока А не пуст.
Тогда работает такой алгоритм:

while(A){
  K=top(A);
  while(top(C) < K){
      B->C(top(C));
      swap();
  }
  A->C();
}
while(C){
  B->C(top(C));
  swap();
}