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

Mechanické hlavolamy Solitéry

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.
The Canterbury Puzzles
The Canterbury Puzzles

Tento algoritmus vyžaduje celkem 2n–k+2k 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

Sdílejte