300px|thumb|Модел ханојске куле (са 8 дискова) 300px|thumb|Анимирано решење ханојске куле за T(4,3). thumb|300px|Ханојска кула се интерактивно приказује у Universum музеју у Мексику
Ханојска кула (такође се назива Брахма кула или Лукасова кула, а понекад и плурализовано) је математичка игра или слагалица. Састоји се од три шипке и великог броја дискова различитих величина који могу да клизе на било коју шипку. Загонетка почиње уређивањем дискова у растућем редоследу на једној палици, где је најмањи на врху па даје изглед конусног облика
Циљ ове слагалице је да се све са једног штапа премести на други штап, поштујући следећа правила: Само један диск може да се помера истовремено. Сваки потез се састоји од узимања горњег диска са једне гомиле и стављања тог истог диска на врх друге гомиле, односно диск може само да се помера ако је на последњем месту на штапу. Ниједан диск не сме бити смештен на мањи диск на штапу.
Са три диска овај проблем може да се реши у седам корака. Најмањи број корака потребних да се реши овај проблем је 2n-1, где је н број дискова.
Порекло
Загонетку је измислио француски математичар Едуар Лукас 1883. Постоји прича о индијском храму у Каши Вишванату, који садржи велику собу са три поруке које су истрошене кроз време и које су окружене са 64 златна диска. Свештеници брамани, радећи у складу са старим пророчанством, померају ове дискове по непроменљивим правилима Брахме од тад. Загонетка је дакле такође и позната као Брахмина кула. Према легенди, свет ће се срушити када буде био завршен последњи потез слагалице. Није утврђено да ли је Лукас смислио ову легенду или је био надахнут њоме.
Ако је легенда истинита и ако су свештеници били у стању да померају дискове по стопи у секунди, користећи најмањи број потеза, требало би им око 264-1 по секунди или око 585 милијарди година или 18 446 744 073 709 551 615 окрета да заврше или око 127 пута тренутне старости Сунца.
Постоје многе варијације на ову легенду. На пример, у неким казивањима храм је манастир, а свештеници су монаси. Храм или манастир може се рећи да у различитим деловима света – укључујући Ханој у Вијетнаму може бити повезан са било којом религијом. У неким верзијама други елементи се уводе, као што је чињеница да је торањ настао на почетку света, или да свештеници или монаси чине само један потез дневно.
Решење
Загонетка се може играти са било којим бројем дискова, иако многе верзије ове игре користе од седам до девет дискова. Минималан број потеза потребних да се реши овај проблем је 2n – 1, где је н број дискова.
Итеративно решење thumb|Итеративни алгоритам решавања проблема Ханојске куле са 6 дискова
Једноставно решење за овакву слагалицу:
Алтернативни покрети се крећу између најмањег дела и не-најмањег дела. Када померате најмањи комад, увек га померате на следећу позицију у истом смеру (са десне стране ако је почетни број паран или налево ако је полазни број комада непаран). Ако кула нема положај у одабраном смеру, померите комад на супротан крај, али онда наставите да померате у исправном смеру. На пример, ако сте почели са три комада, требало би да померите најмањи комад до супротног краја, а затим да наставите у левом правцу после тога. Када је ред на померање не- најмањег комада, постоји само један правилан потез. Уз помоћ овога, слагалица ће се завршити са најмањим бројем потеза.
Једноставнија изјава итеративног решења Наизменично између најмањег и наредног најмањег, следити кораке за погодан положај.
За паран број дискова: Направи исправан потез између рупа А и Б Направи исправан потез између рупа А и C Направи исправан потез између рупа Б и C Понављај док не завршиш
За непаран број дискова: Направи исправан потез између рупа А и C Направи исправан потез између рупа А и Б Направи исправан потез између рупа C и Б Понављај док не завршиш
У сваком случају, укупно је направљено 2n-1 потеза.
Еквивалент итеративног решења Други начин за генерисање јединствено оптималног итеративног решења:
Број дискова од 1 до н ( од најмањег до највећег). Ако је н непаран, први потез је од А до C Ако је н паран, први потез је од А до Б
Сада додајте ова ограничења: Ниједан непаран диск не може ићи директно на други непаран диск. Ниједан паран диск не може ићи директно на други паран диск Никада не поништавај свој претходни потез ( то јест не мрдај диск назад ка претходној позицији).
Имајући у виду та ограничења након првог потеза, постоји само један прави потез у сваком наредном случају.
Редослед ових јединствених потеза је оптимално решење за проблем који је еквивалентан итеративном решењу, горе описаном.
Рекурзивно решење
Кључ за решавање овог проблема је да се призна да се проблем може решити разбијањем на мање проблеме и даље разбијањем тих проблема у још ситније проблеме све док се не стигне до решења. На пример: Обележавањем клинова А, Б и C Нека је н укупан број дискова Број дискова од (најмањи, највиши) до н (највећи, најнижи)
Да бисте преместили н дискова са клина А на клин C: Премести н-1 диск са А на Б. Овај потез оставља н диск сам на клину А. Премести диск н са А на C Премести н-1 диск са Б на C, да се он налази на диску н
Наведено је рекурзивни алгоритам, да спроведе кораке 1 и 3, важи исти алгоритам и за н-1. Цела процедура је коначан број корака, јер у неком тренутку ће бити потребан алгоритам за н= 1. Овај корак, померања појединачног диска са клина А на клин C, је тривијалан. Овом приступу може се додати ригорозан математички формализам са теоријом динамичко програмирање, програмирања, и често се користи као пример рекурзије на часовима програмирања.
Логичка анализа рекурзивног решења
Као и у многим математичким загонеткама, проналажење решења олакшава решавање нешто општијих проблема: Како да померимо кулу Х (х је висина) дискова из почетног клина А (ф-форм) на клин Ц (то), Б је преостала трећна клина и под претпоставком да ф није исто што и т. Прво обратите пажњу да је проблем симетричан за пермутације имена клинова симетрична група С3. Ако је решење познато, померање почиње од клина А до клина Ц, затим преименовањем кочића, исто решење може користити за стартовање сваког другог избора и дестинације клина. Ако постоји само један диск (или чак ниједан), проблем је тривијалан. Ако је х=1, онда једноставно преместите диск са клина А на клин Ц. Ако је х>1, онда негде у редоследу потеза, највећи диск се мора преместити са клина А на неки други клин, пожељно на клин Ц. Једина ситуација која омогућава овај потез је када сви мањи х-1 дискови су на позицији Б. Дакле, прво сви н-1 мањи дискови морају ићи са клина А на клин Б. Након тога померите највећи диск и на крају померите х-1 диск са клина Б у клин Ц. Присуство највећег диска не омета било који потез од х-1 мањих дискова и тренутно се може игнорисати. Сада се проблем своди на померање х-1 дискова са једног клина на други, прво од А до Б, и накнадно од Б до Ц, али исти метод може да користи оба пута преименовањем клинова. Иста стратегија може да се користи да се смањи х-1 диск, до х-2 и х-3 и тако редом све док не остане само један диск. Ово се зове рекурзија. Овај алгоритам се може шематски приказати на следећи начин. Дефинишите дискове са повећањем величине, од нула па навише, не укључујући х. Тако да дискови иду од нула па до х-1.
У наставку је поступак за кретање торња од х дискова, од клина А до клина Ц, са Б који је преостала трећина клина: ПРВИ КОРАК: Ако је х>1 онда ову процедуру користите прво за померање х-1 мањих дискова са клина А на клин Б. ДРУГИ КОРАК: Сада највећи диск, односно диск х можете преместити са клина А на клин Ц. ТРЕЋИ КОРАК: Ако је х>1 онда онда опет користити овај поступак за за померање х-1 мањих дискова са клина Б на клин Ц.
Помоћу математичка индукција, лако је доказати да наведена процедура захтева минималан могући број потеза, као и да је произведено решење једино са минимални бројем потеза. Користећи понављање односа тачан број потеза које ово решење захтева може се израчунати на 2h-1. Овај резултат се добија уз напомену да кораци 1 и 3 троше Тh-1 покрета, а корак 2 троши један покрет, дајући Тh=2Тh-1+1.
Не-рекурзивно решење
Листа потеза за кулу спроводи се од једног клина на други, као да је произведен од рекурзивног алгоритма има много правилности. Када бројимо потезе почев од 1, редни број диска који се помера током потеза м, је број пута м који се може поделити са 2. Зато сваки непаран потез подразумева најмањи диск. Такође се може приметити да најмањи диск пролази кроз клинове ф, т, р, ф, т, р и слично за непарну висину торња и пролази кроз клинове ф, р, т, ф, р, т и слично за парну висину торња. Ово обезбеђује следећи алгоритам, који се лакше обавља ручно, од рекурзивног алгоритма.
У алтернативним потезима: Померити најмањи диск на клин са ког није скоро дошао Померити следећи диск легално (неће бити само једна могућност)
За први потез, најмањи диск иде на клин т ако је х непарно, или на клин п ако је х парно.
Такође приметити да: Дискови чији редни бројеви имају парну једнакост померају се у истом смислу као и најмањи диск. Дискови чији редни бројеви имају непарну једнакост померају се у обрнутом смислу. Ако је х парно, остала трећина клина при успешним померајима је т, р, ф, т, р, ф и тако даље Ако је х непарно, остала трећина клина при успешним померајима је т, р, ф, т, р, ф и тако даље.
Са овим знањем, сет дискова усред оптималног решења, може се обновити са не више него положајних информација, него о појединачној позицији сваког од њих: Позови потезе, горе наведене као дискови „Природни“ потез Испитати најмањи врхунски диск који није диск 0, а обратити пажњу који би њен једини (легални) потез могао да буде (ако не постоји такав диск онда смо на првом или последњем кораку) Ако је потез дисков „природан“ потез онда диск није померан од кад је диск 0 померен, и тај потез треба покренути Ако тај потез није дисков „природни“ потез онда помери диск 0
Бинарно решење Позиције дискова могу се одредити више директно из бинарних представљања броја покрета (базе два), почетно стање са као потез #0, са свим цифрама 0, и финално стање #2n−1 са свим цифрама 1, користећи следећа правила: Постоји једна бинарна цифра (бит) за сваки диск Најзначајнији скроз лево бит представља највећи диск. Вредност 0 указује на то да је највећи диск на почетном клину, док 1 указује на то да је на финалном клину ( десни клин ако је број дискова непаран или пак средњи клин). Битстринг се чита слева надесно и сваки бит се може користити за одређивање локације одговарајућег диска. Бит са истом вредношћу као и претходни значи да се одговарајући диск слаже на врх претходног диска на истом клину ( То јест: равно низ први или нулти значи да су одговарајући клинови сви на истом клину)
Бит са различитим вредностима са претходним значи да је одговарајући диск за једно место улево или удесно од претходне. Да ли је лево или десно је утврђено овим правилом: Претпоставимо да је почетни клин са леве стране Такође претпоставимо „прелом“, тако да прави клин се рачуна као један клин „лево“ левог клина, и обрнуто. Нека је н број већих дискова који се налазе на истом клину као и њихов први већи клин, и додајте један ако је највећи диск на левом клину. Ако је н парно, диск се налази један клин са леве стране (у случају парног броја дискова или пак другачије).
На пример : Ханојска кула са 8 дискова : Потез 0 = 00000000 Највећи диск је 0 па је лево (Иницијални) клин Сви остали дискови су 0 такође, тако да су наслагани на врх. Стога сви дискови су на почетном (иницијалном) клину. Потез 28-1 = 11111111 Највећи клин је један, и налази се на средњем или финалном клину. Сви остали дискови су један, тако да су наслагани на врху. Стога сви дискови су на коначном клину па је загонетка завршена. Потез 21610 = 11011000 Највећи диск је један и он је на средњем (финалном) клину Други диск је један такође један па је смештен на врх тог клина, у средини