Turoj de Hanojo

La turoj de Hanojo estas logika enigmo. Ĝi postulas transmeti konuso-forman turon el rondaj diskoj al alia loko sub jenaj kondiĉoj:

• ekzistas krom la komenca kaj fina lokoj de la turo nur unu libera loko, kie eblas "parki" diskojn
• en ĉiu movo eblas transmeti nur la plej supran diskon de iu turo
• eblas meti diskon nur sur pli grandan diskon

La ludon inventis verŝajne la franca matematikisto Edouard Lucas en 1883. Li prezentis la (fikcian) historion, ke barataj monaĥoj en Benares laboras pri la transmetado de 64-diska turo laŭ tiuj reguloj; post sukcesa transmeto la mondo finiĝos. La ironio de la historio estas, ke la transmetado de n-diska turo postulas 2ⁿ−1 movojn. 64-diska turo do postulas 18.446.744.073.709.551.615 movojn. Farante unu movon en sekundo oni bezonus preskaŭ 585 miliardojn da jaroj. (Oni taksas la ĝisnunan aĝon de la universo je 13–20 miliardoj da jaroj.)

La algoritmo por transmetado estas simpla: Por transmeti turon de unu disko oni simple transmetas tiun diskon. Por transmeti n-diskan turon oni transmetas ĝian (n−1)-diskan supron al la inter-loko, la bazan diskon al la fina loko kaj la "parkitan" turon sur tiun bazan diskon. El tio sekvas, ke ĉe turo el para nombro da diskoj necesas meti la unuan (supran) diskon sur la inter-lokon, ĉe malpara nombro sur la finan lokon.

Laŭ tiu algoritmo rezultas, ke (ĝis tur-alto de tri) disko ripozas ĉiam sur la senpere pli granda disko aŭ sur iu bazloko. Kvankam oni emas supozi, ke per devio de tiu "regulo" eblas plirapidigi la procezon, ne estas tiel. (Se ekzistas pli ol unu libera inter-loko, la problemo komplikiĝas.) Ekzemplo de turo kun tri diskoj (sep movoj):

     X
    XXX
   XXXXX
  -------___-------___-------

    XXX
   XXXXX                  X
  -------___-------___-------

   XXXXX      XXX        X
  -------___-------___-------

               X
   XXXXX      XXX
  -------___-------___-------

               X
              XXX      XXXXX
  -------___-------___-------

     X        XXX      XXXXX
  -------___-------___-------

                        XXX
     X                 XXXXX
  -------___-------___-------

                         X
                        XXX
                       XXXXX
  -------___-------___-------

Vivaj ekzemploj

Turo el tri diskoj

Turo el kvar diskoj