Ханојска кула

Ханојска кула (такође се назива Брахма кула или Лукасова кула, а понекад и плурализовано) је математичка игра или слагалица. Састоји се од три шипке и великог броја дискова различитих величина који могу да клизе на било коју шипку. Загонетка почиње уређивањем дискова у растућем редоследу на једној палици, где је најмањи на врху па даје изглед конусног облика

Модел ханојске куле (са 8 дискова)

Анимирано решење ханојске куле за T(4,3).

Ханојска кула се итерактивно приказује у Universum музеју у Мексику

Циљ ове слагалице је да се све са једног штапа премести на други штап, поштујући следећа правила:

1. Само један диск може да се помера истовремено.
2. Сваки потез се састоји од узимања горњег диска са једне гомиле и стављања тог истог диска на врх друге гомиле, односно диск може само да се помера ако је на последњем месту на штапу.
3. Ниједан диск не сме бити смештен на мањи диск на штапу.

Са три диска овај проблем може да се реши у седам корака. Најмањи број корака потребних да се реши овај проблем је 2ⁿ-1, где је н број дискова.

Порекло

Загонетку је измислио француски математичар Едуар Лукас 1883. Постоји прича о индијском храму у Каши Вишванату, који садржи велику собу са три поруке које су истрошене кроз време и које су окружене са 64 златна диска. Свештеници брамани, радећи у складу са старим пророчанством, померају ове дискове по непроменљивим правилима Брахме од тад. Загонетка је дакле такође и позната као Брахмина кула. Према легенди, свет ће се срушити када буде био завршен последњи потез слагалице. Није утврђено да ли је Лукас смислио ову легенду или је био надахнут њоме.

Ако је легенда истинита и ако су свештеници били у стању да померају дискове по стопи у секунди, користећи најмањи број потеза, требало би им око 2⁶⁴-1 по секунди или око 585 милијарди година или 18 446 744 073 709 551 615 окрета да заврше или око 127 пута тренутне старости Сунца.

Постоје многе варијације на ову легенду. На пример, у неким казивањима храм је манастир, а свештеници су монаси. Храм или манастир може се рећи да у различитим деловима света – укључујући Ханој у Вијетнаму може бити повезан са било којом религијом. У неким верзијама други елементи се уводе, као што је чињеница да је торањ настао на почетку света, или да свештеници или монаси чине само један потез дневно.

Решење

Загонетка се може играти са било којим бројем дискова, иако многе верзије ове игре користе од седам до девет дискова. Минималан број потеза потребних да се реши овај проблем је 2ⁿ – 1, где је н број дискова.

Итеративно решење

Итеративни алгоритам решавања проблема Ханојске куле са 6 дискова

Једноставно решење за овакву слагалицу:

Алтернативни покрети се крећу између најмањег дела и не-најмањег дела. Када померате најмањи комад, увек га померате на следећу позицију у истом смеру (са десне стране ако је почетни број паран или налево ако је полазни број комада непаран). Ако кула нема положај у одабраном смеру, померите комад на супротан крај, али онда наставите да померате у исправном смеру. На пример, ако сте почели са три комада, требало би да померите најмањи комад до супротног краја, а затим да наставите у левом правцу после тога. Када је ред на померање не- најмањег комада, постоји само један правилан потез. Уз помоћ овога, слагалица ће се завршити са најмањим бројем потеза.

Једноставнија изјава итеративног решења

Наизменично између најмањег и наредног најмањег, следити кораке за погодан положај.

За паран број дискова:

• Направи исправан потез између рупа А и Б
• Направи исправан потез између рупа А и C
• Направи исправан потез између рупа Б и C

Понављај док не завршиш

За непаран број дискова:

• Направи исправан потез између рупа А и C
• Направи исправан потез између рупа А и Б
• Направи исправан потез између рупа C и Б

Понављај док не завршиш

У сваком случају, укупно је направљено 2ⁿ-1 потеза.

Еквивалент итеративног решења

Други начин за генерисање јединствено оптималног итеративног решења:

Број дискова од 1 до н ( од најмањег до највећег).

• Ако је н непаран, први потез је од А до C
• Ако је н паран, први потез је од А до Б

Сада додајте ова ограничења:

• Ниједан непаран диск не може ићи директно на други непаран диск.
• Ниједан паран диск не може ићи директно на други паран диск
• Никада не поништавај свој претходни потез ( то јест не мрдај диск назад ка претходној позицији).

Имајући у виду та ограничења након првог потеза, постоји само један прави потез у сваком наредном случају.

Редослед ових јединствених потеза је оптимално решење за проблем који је еквивалентан итеративном решењу, горе описаном.

Рекурзивно решење

Интерактивна илустрација рекурзивног решења Ханојске куле са 4 диска. Кликните сиво дугме да откријете или сакријете фазу.

Кључ за решавање овог проблема је да се призна да се проблем може решити разбијањем на мање проблеме и даље разбијањем тих проблема у још ситније проблеме све док се не стигне до решења. На пример:

• Обележавањем клинова А, Б и C
• Нека је н укупан број дискова
• Број дискова од (најмањи, највиши) до н (највећи, најнижи)

Да бисте преместили н дискова са клина А на клин C:

1. Премести н-1 диск са А на Б. Овај потез оставља н диск сам на клину А.
2. Премести диск н са А на C
3. Премести н-1 диск са Б на C, да се он налази на диску н

Наведено је рекурзивни алгоритам, да спроведе кораке 1 и 3, важи исти алгоритам и за н-1. Цела процедура је коначан број корака, јер у неком тренутку ће бити потребан алгоритам за н= 1. Овај корак, померања појединачног диска са клина А на клин C, је тривијалан. Овом приступу може се додати ригорозан математички формализам са теоријом динамичко програмирање, програмирања, и често се користи као пример рекурзије на часовима програмирања.

Логичка анализа рекурзивног решења

Као и у многим математичким загонеткама, проналажење решења олакшава решавање нешто општијих проблема: Како да померимо кулу Х (х је висина) дискова изпочетног клина А (ф-форм) на клин Ц (то), Б је преостала трећна клина и под претпоставком да ф није исто што и т. Прво обратите пажњу да је проблем симетричан за пермутације имена клинова симетрична група С3. Ако је решење познато, померање почиње од клина А до клина Ц, затим преименовањем кочића, исто решење може користити за стартовање сваког другог избора и дестинације клина. Ако постоји само један диск (или чак ниједан), проблем је тривијалан. Ако је х=1, онда једноставно преместите диск са клина А на клин Ц. Ако је х>1, онда негде у редоследу потеза, највећи диск се мора преместити са клина А на неки други клин, пожељно на клин Ц. Једина ситуација која омогућава овај потез је када сви мањи х-1 дискови су на позицији Б. Дакле, прво сви н-1 мањи дискови морају ићи са клина А на клин Б. Након тога померите највећи диск и на крају померите х-1 диск са клина Б у клин Ц. Присуство највећег диска не омета било који потез од х-1 мањих дискова и тренутно се може игнорисати. Сада се проблем своди на померање х-1 дискова са једног клина на други, прво од А до Б, и накнадно од Б до Ц, али исти метод може да користи оба пута преименовањем клинова. Иста стратегија може да се користи да се смањи х-1 диск, до х-2 и х-3 и тако редом све док не остане само један диск. Ово се зове рекурзија. Овај алгоритам се може шематски приказати на следећи начин. Дефинишите дискове са повећањем величине, од нула па навише, неукључујући х. Тако да дискови иду од нула па до х-1.

У наставку је поступак за кретање торња од х дискова, од клина А до клина Ц, са Б који је преостала трећина клина:

• ПРВИ КОРАК: Ако је х>1 онда ову процедуру користите прво за померање х-1 мањих дискова са клина А на клин Б.
• ДРУГИ КОРАК: Сада највећи диск, односно диск х можете преместити са клина А на клин Ц.
• ТРЕЋИ КОРАК: Ако је х>1 онда онда опет користити овај поступак за за померање х-1 мањих дискова са клина Б на клин Ц.

Помоћу математичка индукција, лако је доказати да наведена процедура захтева минималан могући број потеза, као и да је произведено решење једино са минимални бројем потеза. Користећи понављање односа тачан број потеза које ово решење захтева може се израчунати на 2^h-1. Овај резултат се добија уз напомену да кораци 1 и 3 троше Т_h-1 покрета, а корак 2 троши један покрет, дајући Т_h=2Т_h-1+1.

Не-рекурзивно решење

Листа потеза за кулу спроводи се од једног клина на други, као да је произведен од рекурзивног алгоритма има много правилности. Када бројимо потезе почев од 1, редни број диска који се помера током потеза м, је број пута м који се може поделити са 2. Зато сваки непаран потез подразумева најмањи диск. Такође се може приметити да најмањи диск пролази кроз клинове ф, т, р, ф, т, р и слично за непарну висину торња и пролази кроз клинове ф, р, т, ф, р, т и слично за парну висину торња. Ово обезбеђује следећи алгоритам, који се лакше обавља ручно, од рекурзивног алгоритма.

У алтернативним потезима:

• Померити најмањи диск на клин са ког није скоро дошао
• Померити следећи диск легално (неће бити само једна могућност)

За први потез, најмањи диск иде на клин т ако је х непарно, или на клин п ако је х парно.

Такође приметити да:

• Дискови чији редни бројеви имају парну једнакост померају се у истом смилсу као и најмањи диск.
• Дискови чији редни бројеви имају непарну једнакост померају се у обрнутом смислу.
• Ако је х парно, остала трећина клина при успешним померајима је т, р, ф, т, р, ф и тако даље
• Ако је х непарно, остала трећина клина при успешним померајима је т, р, ф, т, р, ф и тако даље.

Са овим знањем, сет дискова усред оптималног решења, може се обновити са не више него положајних информација, него о појединачној позицији сваког од њих:

• Позови потезе, горе наведене као дискови „Природни“ потез
• Испитати најмањи врхунски диск који није диск 0, а обратити пажњу који би њен једини (легални) потез могао да буде (ако не постоји такав диск онда смо на првом или последњем кораку)
• Ако је потез дисков „природан“ потез онда диск није померан од кад је диск 0 померен, и тај потез треба покренути
• Ако тај потез није дисков „природни“ потез онда помери диск 0

Бинарно решење

Позиције дискова могу се одредити више директно из бинарних представљања броја покрета (базе два), почетно стање са као потез #0, са свим цифрама 0, и финално стање #2ⁿ−1 са свим цифрама 1, користећи следећа правила:

• Постоји једна бинарна цифра (бит) за сваки диск
• Најзначајнији скроз лево бит представља највећи диск. Вредност 0 указује на то да је највећи диск на почетном клину, док 1 указује на то да је на финалном клину ( десни клин ако је број дискова непаран или пак средњи клин).
• Битстринг се чита слева надесно и сваки бит се може користити за одређивање локације одговарајућег диска.
• Бит са истом вредношћу као и претходни значи да се одговарајући диск слаже на врх претходног диска на истом клину ( То јест: равно низ први или нулти значи да су одговарајући клинови сви на истом клину)

Бит са различитим вредностима са претходним значи да је одговарајући диск за једно место улево или удесно од претходне. Да ли је лево или десно је утврђено овим правилом:

• Претпоставимо да је почетни клин са леве стране
• Такође претпоставимо „прелом“, тако да прави клин се рачуна као један клин „лево“ левог клина, и обрнуто.
• Нека је н број већих дискова који се налазе на истом клину као и њихов први већи клин, и додајте један ако је највећи диск на левом клину. Ако је н парно, диск се налази један клин са леве стране (у случају парног броја дискова или пак другачије).

На пример : Ханојска кула са 8 дискова :

• Потез 0 = 00000000
  • Највећи диск је 0 па је лево (Иницијални) клин
  • Сви остали дискови су 0 такође, тако да су наслагани на врх. Стога сви дискови су на почетном (иницијалном) клину.
• Потез 28-1 = 11111111
  • Највећи клин је један, и налази се на средњем или финалном клину.
  • Сви остали дискови су један, тако да су наслагани на врху. Стога сви дискови су на коначном клину па је загонетка завршена.
• Потез 21610 = 11011000
  • Највећи диск је један и он је на средњем (финалном) клину
  • Други диск је један такође један па је смештен на врх тог клина, у средини
  • Трећи диск је нула, па је смештен на другом клину. Пошто је н непарно (н=1) то је један клин са леве стране, односно леви клин.
  • Четврти диск је један, па је то други клин. Пошто је не непарно (н=1), то је један клин са леве стране, односно десни клин.
  • Пети диск је такође један, и смештен је на врх десног клина.
  • Шести диск је нула па је смештен на следећи клин. Пошто је н парно (н=2), диск је једно место надесно, односно на левом клину.
  • Седми и осми диск су такође нула, па су смештени на врх, на левом клину.

Изворни и одредишни клинови за mтх покрет се могу елегантно наћи из бинарне репрезентације м-а, користећи операције са битовима. Да би користили синтаксу у Ц програмском језику, померите м са клина (m&m-1)%3 на клин ((m|m-1)+1)%3, где дискови почињу од клина 0 и завршавају се клином 1 или 2, у зависности да ли је број дискова паран или непаран. Друга формулација је са клина (m-(m&-m))%3 на клин (m+(m&-m))%3.

Осим тога, диск да би се могао померати одређен је са бројем пута у покрету сабирања (м) и може бити подељен са два (односно, број од нула битова је на десној страни). Рачунајучи први потез као први и идетификовањем дискова по бројевима 0,1,2 итд према редоследу повећања величине. Ово омогућава веома брзо не рекурзивно рачунарско спровођење да би се пронашла позиција дискова после м потеза без позивања на било који претходни потез или дистрибуцију дискова.

ЦТЗ операција, која пребројава узастопне нуле на крајевима бинарних бројева, даје једноставно решење за проблем: дискови су нумерисани од нуле, а на покрет м, диск број ЦТЗ(м) се преселио на најмању могућу удаљеност са десне стране (кружи око како би се вратио налево ако би било потребно).

Решење Грејевог кода

Бинарни нумерички систем цифара Грејев код даје алтернативни начин решавања слагалице. У сивом систему бројеви су изражени бинарним комбинацијама јединице и нуле, али уместо да буде стандардни нумерички систем, Грејев код ради на претпоставци да се свака вредност разликује од свог претходника за само један ( и тачно један) бит промене. Број битова присутних у грејовом коду је важан, а водеће нуле нису опција, за разлику од позиционих система. Ако једно бројање у сивом коду битова по величини је једнако броју дискова у Ханојској кули, почиње од нуле и броји, онда бит мења сваки потез који одговара потезу диска где је најмањи бит у ствари најмањи диск, и највише значајан бит је највећи.

Бројање потеза од 1 и идентификовање дискова бројевима, почевши од 0 са повећањем величине, редни број диска који се преселио током покрета м је број пута м и може се поделити са два.

Ова техника идентификује који диск да се креће али не и где да га померите. За најмањи диск постоје увек две могућности. За остале дискове постоји увек само једна могућност, осим кад се сви дискови налазе на истом клину, али у том случају било да је најмањи диск он мора да се помери или је циљ већ постигнут. Срећом постоји правило које каже где да померите најмањи диск. Нека ф буде почетни клин, т одредиште клина и п преостала трећина клина. Ако је број дискова непаран, најмањи диск кружи дуж клинова у смеру ф→т→р→ф→т→р, итд. Ако је број дискова паран, ово мора бити обрнуто ф→р→т→ф→р→т итд.

Графичка репрезентација

Игра може бити представљена и уз помоћ индиректног графикона, чворови представљају дистрибуцију дискова а ивице представљају потезе. За један диск график је троугао:

Графикон за два диска чине три троугла респоређена у ширем троуглу:

Чворови на теменима најспољнијих троуглова представљају расподеле свих дискова на истом клину.

За х+1 дискове, узмите график х дискова, и замените сваки мали троугао са графикона са друга два троугла.

За три дискова график је:

• Назови клинове А, Б и C
• Листа позиције дискова слева надесно, по редоследу повећања величине.

Бокови најспољнијих троуглова представљају најкраће начине кретања кула са једног клина на други. Ивица усред стране највећег троугла представља кретање највећег диска. Ивица по средини сваке следеће стране мањег троугла представља потез сваког наредног мањег диска. Бокови најмањих троуглова представљају потезе најмањег диска.

Игра графика нивоа 7 показује повезаност са троуглом Сјерпињског.

Уопштено, за слагалице са н дискова, постоји 3ⁿ чворова у графикону; сваки чвор има три ивице до осталих чворова, осим три угаона чвора, који имају два; увек је могуће да померите најмањи диск на један од друга два клина а могуће је да се креће један диск између та два клина осим у ситуацији кад су сви дискови наслагани на један клин. Угаони чворови представљају три случаја у којима су сви дискови наслагани на један клин. Дијаграм за н+1 дискова се добија узимањем три примерка дијаграма н диска- сваки од њих представља положаје и потезе мањих дискова за једну одређену позицију новог највећег диска – и њихово спајање на угловима са новим ивицама које представљају само три могућности за кретање највећег диска. Добијена цифра има 3ⁿ⁺¹+1 чворова и идаље има три угла преостала са само две ивице.

Како се додаје више дискова, график представљања игре ће личити на фрактал, троугао Сјерпињског. Јасно је да велика већина места у слагалици никада неће бити постигнута када користите најмања могућа решења. Заиста, да су свештеници из легенде користили најдуже могуће решење (без поновног посећивања било које позиције) то би им потрошило око 3⁶⁴ − 1 потеза или више од 10²³ година.

Најдужи начин без понављања за три диска може се видети брисањем неискоришћених ивица.

Узгред, овакав најдужи пут без понављања може се добити забрањујући све

Хамилтонов циклус за три диска изгледа:

Графикон јасно показује да:

• Из сваке произвољне дистрибуције дискова, тачно је један најкраћи потез да се помере сви дискови на један од три клина
• Између сваког пара прозвољне расподеле дискова постоје један или два најкраћа пута.
• Из сваке произвољне дистрибуције дискова, постоје један или два дуга различита не-своја пута за кретање свих дискова на један од три клина.
• Између сваког пара произвољне расподеле дискова постоје један или два различита дуга начина преласка за кретање торња х дискова из једног клина на други. Затим:
  • N₁ = 2
  • N_h+1 = (N_h)² + (N_h)³.
  • Na primer: N₈ ≈ 1.5456×10⁷⁹⁵

Апликације

Ханојска кула се често користи у психолошким истраживањима у решавање проблема. Такође постоји варијанта овог задатка под називом Кула Лондона за неуропсихолошку дијагностику и лечење извршних функција.

Норман и Џанг (Когнитивна наука ) користи неколико изоморфних (еквивалентних) представа игре за проучавање утицаја репрезентације ефеката у дизајну задатка. Они су показали утицај на перформансе корисника на начин на који су правила представљена, користећи варијације у физичком дизајну компоненти игре. Ово знање је утицало на развој оквира за људске рачунарске интеракције.

Ханојска кула се користи као резервна шема ротације приликом обављања рачунарских резервних копија података где је укључено више трака тј медија.

Као што је већ поменуто, ханојска кула је популарна за наставу рекурзивних алгоритама за програмирање на почетку студирања. А пикторијал верзија ове слагалице је програмирана у емакс едитору којој се приступа куцањем М-Х ханој. Ту је узорак алгоритма писан у прологу. Ханојска кула се користи као тест за неуропсихијатриске покушаје да процене дефицит фронталног режња.

У 2011 години, истраживачи су објавили резултате експеримента које је утврдио да је мрав врста Линепитхема која је успешно могла да реши верзију 3 диска ханојске куле проблема кроз нелинеарну динамику или сигнале фермона.

Општи најкраћи путеви и број 466/885

Занимљива генерализација оригиналног циља слагалице је да се почне са датом конфигурацијом дискова, где сви дискови нису нужно на истом У принципу то може бити прилично тешко да израчунате најкраћи низ потеза да бисте решили овај проблем. Решење је предложио Андреас Хинз, а заснива се на посматрању да у најкраћем редоследу потеза, највећи диск који треба да се помера ( очигледно може игнорисати све од највећих дискова који ће се простирати на истом клину у обе почетне и финалне конфигурације ) ће се померити или тачно једном или два пута тачно.

Математичке везе са овим проблемом уопштено постају још занимљивије када се узме у обзир просечан број кретања у најкраћем редоследу потеза између две почетне и крајње конфигурације диска које су изабране насумично. Хинз и Џан Хат Тунг независно су открили (видите такође, Chapter 1. стр. 14) да је просечан број дискова у Х кули, даје следећим тачним формулама:

${\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{29}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{29}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.$

Имајте на уму да за велико довољно н, само први и други услови не конвергирају на нулу, тако да смо добили асимптотски израз : $466/885\cdot 2^{n}-1/3+o(1)$, as $n\to \infty$. Тако интуитивно, можемо инетпретирати фракцију $466/885\approx 52.6\%$ као представу односа снаге један мора да изврши када се иде из насумично изабране конфигурације на другу насумично изабрану конфигурацију, у односу на тешкоће морају да пређу " најтежи " пут дужине 2н - 1 који подразумева кретање свих дискова са једног клина на други. Алтернативно објашњење за појаву сталног 466/885, као и новог и донекле правилног алгоритма за израчунавање најкраће путање, дао је Ромик .

Варијације

Циклични ханој

У цикличном Ханоју, имамо три штипаљке ( А, Б, C), који су распоређене као круг са смером казаљке на сату и супротно од смера који се дефинише као - Б - C - А и А - C - Б - респективно. Правац кретања диска мора бити као казаљке на сату. Довољно је да представите низ дискова који се померају. Решење можете наћи коришћењем два међусобно рекурзивна поступка:

Да бисте преместили н дискове у смеру казаљке на сату у суседну циљани клин :

1. Померите н-1 дискове у смеру казаљке на сату на циљани клин
2. Померите #н диск један корак у смеру казаљке на сату
3. Померите н-1 дискове у смеру казаљке на сату на почетни клин
4. Померите #н диск један корак у смеру казаљке на сату
5. Померите н-1 дискове у смеру казаљке на сату на циљани клин

Да бисте преместили н дискове у смеру казаљке на сату у суседни циљани клин :

1. Померите н-1 дискове у смеру казаљке на сату на резервни клин
2. Померите #н диск један корак у смеру казаљке на сату
3. Померите н-1 дискове у смеру казаљке на сату на циљани клин

Нека C ( н) и А (н ) представљају кретање н дискова у смеру казаљке на сату и супротно, онда можемо записати обе формуле :

         C(н) = A(н-1) н A(н-1)    и      A(н) = A(н-1) н C(н-1) n A(н-1).

          Tako  C(1) = 1                  и      A(1) = 1 1,
                C(2) = 1 1 2 1 1          и      A(2) = 1 1 2 1 2 1 1.

Решење за цикличан Ханои има неке занимљиве особине :

1. Потез преноса торања дискова са клин на други клин су симетрични у односу на центар.
2. Најмањи диск је први и последњи за померање.
3. Групе најмањих дискова потезима се смењују са појединачним потезима других дискова
4. Број дискова потеза које је наведено под C(н) и А(н) је најмањи.

Са четири клина и више

Иако верзија три клина има једноставно рекурзивно решење као што је горе наведено, оптимално решење за Ханојску кулу проблема са четири клина ( тзв Реова пузла), а камоли више клинова, још увек је отворен проблем. Ово је добар пример како једноставан, решив проблем може драматично бити тежи отпуштањем једног од проблема ограничења.

Чињеница да је проблем са четири или више клинови отворен проблем не значи да не постоји алгоритам за проналажење ( свих ) оптималних решења. Једноставно представљају игру од стране графикона, чворови чине дистрибуцију дискова а ивице чине потезе и користећи претрагу у ширину прво траже да нађу једно (или све ) најкраћим путем (а ) прелазком на торањ од једног клина на другу. Међутим, чак и паметно спровођење на најбржи рачунар је сада доступно, овај алгоритам не даје никакав начин ефикасног рачунарског решења за велики број дискова; Програм ће захтевати више времена и меморије него што је на располагању. Дакле, чак и да познајемо алгоритам, остаје непознато колико потеза оптимално решење захтева и колико постоји оптималних решења за 1000 дискова и 10 клиновима.

Иако се не зна тачно колико потези се мора направити, постоје асимптотски резултати. Ту је и " претпоставка - оптималног решења" којој даје оквир Фрејм Стевартов алгоритам, откривен је независно од Фрејма и Стјуарта 1941. године. Одношење на Фрејм – Стевартово нагађање тврди да Рама - Стјуарт алгоритам увек даје оптимално решење. Оптималности оквира - Стевартовог алгоритма је рачунски утврдио за 4 клина са до 30 дискова.

За остале варијанте Ханојске куле са проблемом са четири куле, погледајте папир Паул Стоцкмеиерове анкете.

Фрејм-Стевартов алгоритам

Фраме - Стјуарт алгоритам, дајући оптимално решење за четири ( или чак и више ) клинова, описан је у наставку:

• Нека је н број дискова
• Нека је р број клинова
• Дефинишемо T(н, р) да је минимални број потеза потребних за пренос н дискова који користе р клинови

Алгоритам може бити описан рекурзивно :

1. а неко к, 1<=к<н, за пренос топ к дискова на један клин осим почетних или клинова дестинације, узимајући Т(к, р) потеза
2. Без нарушавања клин који сада садржи топ k дискове, преноси преостале н-k дискове до одредишта клина, користећи само преостале р-1 клинове, узимајући T(н-k, р-1) потезе.

Читав процес траје 2T(k, р)+T(н-k, р-1) потеза. Дакле, k треба бирати тако да је ова количина минимум. ( У четири клинском сценарију, идеално k је једнако корен из 2н+1 заобљено минус 1. )

Ханојска кула са више гомила

Патент број 7.566.057 издаје Виктор Масцоло открива загонетку Ханојске куле са две или више гомиле и дупло више клинова као гомила. Након почетка на одређеном клину, сваки гомила се помера и бива расељена од стране гомиле друге боје на другом клину када се решава слагалице. Дискови једне боје и још један клин који искључује све остале боје, тако да постоје три штипаљке на располагању за сваки диск боје, два се деле са другим бојама, и онај који се не дели. На заједничким клиновима, диск не може бити постављен на други диск друге боје исте величине, могућност да се не појављује у стандардној слагалице.

Најједноставнија игра са више гомила ( 2 × 4 ), има две гомиле и четири клинови, и захтева 3[Т(н)] потеза да реше где је Т(н) број потеза потребан да реши појединачан клин са н дискова. Игра се наставља са све дужим и дужим низом потеза који варирају између боја. У њему се закључује у обрнутом начину са све краћим и краћим таквим серијама потеза. Почевши од друге серије од три потеза, алтернативни низ потеза се удвостручује по дужини за прву половину утакмице, а дужине су преполовљене како се игра закључује. Решење укључује алгоритам погодан за Ханосјку кулу у алгоритму који указује на пребацивање између боја. Када постоје к гомиле н дискова по комаду у игри, и к>2, то захтева К[Т(н)]+Т(н-1)+1 потеза да их премести.

Додавање у централни део универзалног клина отвореног за дискове са свих клинова претвара ову загонетке Ханојске куле са више гомила у Реову загонетку са више гомила као што је описано у претходном одељку. У овим играма свака гомила може да се креће између четири клина, иста комбинација за три у игри 2 × 4 плус централни универзални клин. Најједноставнији игра ове врсте ( 2 × 5 ) има две гомиле и пет клинове. Решење је претпостављено да буде оптимално решење 2 × 4 слагалице са претпостављеним оптималним решењем за Реову загонетку. Потребно је Р(н)+2Р(н-1)+2 потеза, где је Р(н) број потеза у претпостављеном оптималном решењу Реове загонетке за гомилу н дискова.

Магнетни Ханој

У магнетној ханојској кули, сваки диск има две одвојене стране Северну и Јужну ( обично у боји "црвено" и " плаво" ). Дискови не морају бити постављене са сличним половима заједно - магнети за сваки диск спречавају овај нелегални потез. И сваки диск се мора окренути, као што се помера.

Почетна конфигурација Ханојске куле са две боје (н=4)

Кула са две боје

Ова варијација чувене слагалице Ханојске куле је понуђена ученицима разреда 3-6 на 2ème Championnat de France des Jeux Mathématiques et Logiques одржане у јулу 1988. године.

Крајња конфигурација Ханојске куле са две боје (н=4)

Правила слагалице су у суштини иста : дискови се преносе између клинова један по један. Ни у једном тренутку не може већи диск бити постављен на врх једног мањег. Разлика је у томе што сада за сваку величину постоје два диска : један црни и један бели. Такође, сада постоје две куле дискова наизменичних боја. Циљ слагалице је да се створе једнобојни торњеви ( исте боје). За највеће дискове на дну куле се претпоставља да мењају позиције.

Детаљно рекурзивно решење овакве куле се расправља овде : http://rmm.ludus-opuscula.org/PDF_Files/Chaugule_BicolorHanoi_37_48(4_2015)_low.pdf

Ханојска кула у популарној култури

У причи научне фантастике "Сада Удахните ", Ерик Франк Русселл, човек је заробљеник на планети где је локални обичај да затвореник игра игру све док не победи или изгуби пре његовог погубљења. Главни јунак зна да спасилачки брод може потрајати годину или више да стигне, па он бира да игра Ханојску кулу са 64 дискова. (Ова прича помиње легенде о будистичким монасима који играју утакмицу до краја света.)1966 године прича доктора Хуа, Небески Тоимакер, епонимски зликовац приморава доктора да играју десето комадни 1.023 - потезе игре Ханојске куле познате под називом Трилоџик игра са комадима који формирају облик пирамиде када се слажу.

У 2007. години, концепт проблема Ханојске куле је коришћен код професора Лаитон и Диаболичкој кутији из загонетке 6, 83, и 84, али су дискови били замењени са палачинкама. Загонетка је заснована на дилеми где је кувар ресторана морао хрпу палачинки са једне плоче премести на другу са основним принципима оригиналне пузле ( тј три плоче на којима би се палачинке могле померити, нису били у стању да ставе већу палачинку на мању, итд )

У филму Планета мајмуна: Почетак (2011), ове куле, називане у филму "Лукасова кула", се користе као тест за проучавање интелигенције мајмуна.

Загонетка се редовно појављује у авантурама и слагалицама. Будући да је лако спровести и лако препознати, пошто је добро прилагођена за коришћење као слагалице у већим графичким играма ратови звезда и Mass Effect ). Неке имплементације користе праве дискове, али друге прикривају слагалицу у некој другој форми. Постоји верзија аркада за Сега / Андамиро.

Проблем је представљен као део награда изазов у 2011. у епизоди америчке верзије Сурвивор ТВ серија. Оба играча ( Оззи Лустх и Бењамин " Тренер " Ваде) борила су се да схвате како да реше загонетку и уз помоћ својих колега чланова племена.

У науци и материјалима

3Д АФМ Топографска слика вишеслојног паладијума, са структуром Ханојске куле.

У 2014, научници синтетише вишеслојна паладијум наносхеет са структуром попут Ханојске куле. Ово је први пут да се слична структура посматра у природи.

Види још

• Шема ротације, ТОХ апликација
• Baguenaudier
• Рекурзија (наука о рачунарима)

Литература

• Warren, Henry S. (2003). „Section 5-4: Counting Trailing 0's.”. Hacker's delight (1st изд.). Boston MA: Addison-Wesley. ISBN 978-0-201-91465-8. 
• Sniedovich, Moshe (2010). Dynamic Programming: Foundations and Principles. Taylor & Francis. ISBN 978-0-8247-4099-3. Архивирано из оригинала 24. 09. 2015. г. Приступљено 29. 10. 2015. 
• Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. стр. 197. ISBN 978-0-8218-4814-2. 
• Moscovich, Ivan (2001). 1000 playthinks: puzzles, paradoxes, illusions & games. Workman. ISBN 978-0-7611-1826-8. 
• Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. стр. 137. ISBN 978-0-03-084693-9. 
• Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN 978-0-465-04540-2. 

Спољашње везе

• Weisstein, Eric W. „Tower of Hanoi”. MathWorld. 
• Tower of Hanoi animation