Hanojská věž s rozšířením na čtyři – Reveho hádanka

Varianta Hanojské věže (základní informace o tomto hlavolamu ZDE), v níž jsou čtyři věže namísto tří, se nazývá Reveho hádanka a byla poprvé publikována v roce 1907 v knize Canterburské hádanky (The Canterbury Puzzles) Henryho Dudeneyho. Na rozdíl od původní varianty není u Reveho hádanky dosud známo optimální řešení ani nejnižší nutný počet kroků pro libovolný počet kotoučů. Algoritmus pro její řešení se nazývá Frame-Stewartův:

•     Zvolme celé číslo k, které je větší nebo rovno 1 a menší než n.
•     Přesuneme n–k nejmenších kotoučů z počáteční věže na první odkládací věž rekurzívním voláním tohoto algoritmu.
•     Přesuneme k zbylých kotoučů z počáteční věže na cílovou pomocí algoritmu pro klasické Hanojské věže, přičemž využijeme jen druhou odkládací věž.
•     Přesuneme n–k nejmenších kotoučů z první odkládací věže na cílovou rekurzívním voláním tohoto algoritmu.

Tento algoritmus vyžaduje celkem 2^n–k+2^k kroků. Volba k by tedy měla být taková, aby tato hodnota byla nejmenší. Algoritmus je považován za optimální, ačkoli to není dokázáno.
Frame-Stewartův algoritmus lze zobecnit pro libovolný počet věží (označme ho r):

•     Zvolme celé číslo k, které je větší nebo rovno 1 a menší než n.
•     Přesuneme n–k nejmenších kotoučů z počáteční věže na r-tou věž rekurzívním voláním tohoto algoritmu.
•     Přesuneme k zbylých kotoučů z počáteční věže na cílovou s využitím jen r–1 věží rekurzívním voláním tohoto algoritmu. (Je-li r–1=3, pak využijeme klasický algoritmus pro tři Hanojské věže.)
•     Přesuneme n–k nejmenších kotoučů z r-té věže na cílovou rekurzívním voláním tohoto algoritmu.

Podívejte se na video s řešením Reveho hádanky