A hanoi tornyai matematikai játék, illetve feladvány egy legendából származó ötleten alapszik. A legenda szerint egykor az indiai Benaresben egy Shiva-templom jelölte a világ közepét. Fo Hi uralkodása idején a templomban élő szerzetesek feladatot kaptak Shiva istennőtől. A templom közepén volt egy márványtábla, melyből három gyémántrúd állt ki. Az első rúdon 64 különböző méretű arany korong volt. Legalul volt a legnagyobb, majd rajta méret szerint csökkenő sorrendben a többi. A szerzetesek feladata az volt, hogy áthelyezzék az összes korongot az első rúdról a másodikra, a következő szabályok betartása mellett. A korongok nagyon sérülékenyek, ezért egyszerre csak egy korong mozdítható, valamint egy korong nem helyezhető olyan rúdra, ahol van nála kisebb korong. A korongok megszenteltek, ezért csak ezt a három megszentelt rudat lehet használni, máshová nem rakhatják le a korongokat. Amint minden korong átkerült a második rúdra, a templom összeomlik, és a világ véget ér. Ha igaz ez a legenda, akkor jó lenne tudnunk, hogy ez mikor is következik be. A játék leírása először 1883-ban jelent meg egy párizsi újságban, amit a Li-Sou-Stian egyetem egyik hallgatója, N. Claus de Siam publikált. Kiderült, hogy a szerző csak egy álnév, az igazi szerző nevének anagrammája. A cikk valódi írója a Lyce Saint-Louis egyetem professzora, Edouard Lucas D’Ameins volt. A hanoi tornyai egy tipikus esete az úgynevezett „oszd meg és uralkodj” típusú problémáknak. A név onnan származik, hogy a megoldást legkönnyebben úgy találhatjuk meg, ha a problémát egyszerűbb, az eredetihez hasonló részproblémákra osztjuk, majd ha szükséges, a részproblémákat tovább osztjuk. Jelen esetben a problémának van egy kulcsmozzanata: a legnagyobb korong áthelyezése. Ha az első rúdról szeretnénk áthelyezni a korongokat a másodikra rúdra, akkor először a többi korongot kell átraknunk a harmadik rúdra, ezután át tudjuk rakni a legnagyobb korongot a második rúdra, majd a harmadik rúdra átrakott korongokat vissza kell rakni a második rúdra. A részproblémákat most a többi korong átrakása jelenti, először a harmadik rúdra, majd onnan vissza a másodikra. Ezeket a részproblémákat hasonló gondolkodásmód szerint oldhatjuk meg. Könnyen bizonyítható, hogy ezzel előállíthatjuk az optimális megoldást, ami n korong esetén 2^n-1 lépést jelent (a bizonyítást lásd később). Ezek szerint 64 korong esetén minimum 264 – 1 = 18 446 744 073 709 551 615 lépésre van szükség. Ha a szerzetesek képesek lennénk egy korongot egyik rúdról a másikra egy másodperc alatt átrakni, a probléma megoldása még akkor is megközelítőleg 590 000 000 000 évet venne igénybe, úgyhogy egy ideig még nem kell félnünk a világ végétől akkor sem, ha a legenda igaz. Meg kell jegyeznünk, hogy az Univerzum jelen ismereteink szerint 13 700 000 000 éves. Szakdolgozatom célja, hogy a hanoi problémát különböző módokon megoldjam, és ezeknek a megoldásoknak a hatékonyságát összehasonlítsam. Egy hagyományos mesterséges intelligenciai problémát általában legegyszerűbben állapottér-reprezentációval és az ismertebb kereső algoritmusokkal lehet megoldani. Természetesen ez közel sem a leghatékonyabb megoldás. Sokkal jobb eredményeket lehet elérni, ha elemezzük a problémát, és probléma specifikus algoritmust készítünk. Dolgozatom első felében két állapottér-reprezentációt fogok elemezni, majd a továbbiakban a problémát mélyebben megvizsgálva, ismertebb programozási technikákkal készítek többféle megoldást, és mindezeket összehasonlítom. Az algoritmusokat az egyszerűség kedvéért Java nyelven írtam, mivel célom nem a lehető legnagyobb hatékonyság elérése, hanem a különböző megoldások összehasonlítása.