Hanojski stolpi

Hanojski stolpi oziroma problem Hanojskega stolpa je igra ali uganka s področja razvedrilne matematike. Za igro so potrebne tri palice (trije kupčki), na katere zlagamo (ali natikamo) okrogle ploščice različnih velikosti. Število ploščic je poljubno, vse pa morajo biti različnega premera.

Pribor za igro hanojskih stolpov z osmimi ploščicami

Rešitev za 4 ploščice

Igra se začne tako, da so ploščice v kupčku na začetnem stolpu urejene od vrha do tal v vrstnem redu od najmanjše do največje, tako da ima kup obliko stožca. Cilj igre je premakniti celotni kupček ploščic na drug kupček ploščic (končni stolp) z najmanjšim možnim številom potez, z upoštevanjem pravil:

• naenkrat lahko premaknemo samo eno ploščico in
• na vrh manjše ploščice ne smemo postaviti večje.

Izvor igre

Igro je izumil francoski matematik Édouard Lucas leta 1883 in o njej v reviji Science et Nature napisal članek, ki je izšel naslednje leto 1884. Obstaja legenda o indijskem templju, ki ima veliko sobo s tremi obrabljenimi drogovi, ki jih obkroža 64 zlatih ploščic. Brahmani premikajo te ploščice glede na pravila igre. Po legendi bo po zadnjem premiku ploščice konec sveta. Uganka je zaradi tega znana tudi kot brahmanski stolpi. Ni znano ali si je Lucas sam izmislil legendo ali ga je le navdahnila. To nalogo (igro) lahko rešujemo na več načinov. Najbolj znana rešitev je rekurzivna in je zato znana tudi kot šolski primer pri računalniškem programiranju.

Če bi bila legenda resnična in če bi lahko duhovniki premikali ploščice s hitrostjo 1 na sekundo, bi bil za najmanjše možno število potez ploščic potreben čas 2⁶⁴−1 sekund, oziroma približno 584,542 milijard let. Vesolje je trenutno staro okrog 13,7 milijard let.

Obstaja več različic legende. Po nekaterih je tempelj samostan, duhovniki pa so menihi. Tempelj ali samostan se lahko nahaja v različnih delih sveta, med njimi tudi v Hanoju v Vietnamu, in je lahko povezan s katerokoli religijo. V nekaterih različicah so vključeni še drugi elementi. Na primer dejstvo, da so bili stolpi narejeni na začetku sveta, ali pa da imajo duhovniki, oziroma menihi za potezo na razpolago le en dan.

Morda je na ime vplival 33,4 m visok stolp v Hanoju, zgrajen leta 1812, na katerem danes visi nacionalna vietnamska zastava.

Rešitev

Večina različic v obliki igrače ima 8 ploščic. Igra se nepoznavalcem zdi nemogoča, čeprav je rešljiva s preprostim algoritmom.

Rešitev z rekurzijo

Kakor v mnogih matematičnih ugankah je iskanje rešitve lažje z rešitvijo rahlo splošnejšega problema: kako premakniti ploščice stolpov višine h (height) z začetnega stolpa f (from) na končni stolp t (to), kjer je r preostali tretji stolp in velja še t ≠ f. Problem je simetričen za permutacije imen stolpov (simetrična grupa S₃). Če je znana rešitev za premike s stolpa f na stolp t, potem se lahko s preimenovanjem stolpov uporabi ista rešitev za vsako drugo izbiro začetnega in končnega stolpa. Če je stolp le en sam (ali, če ga sploh ni), je problem trivialen. Če je h=1, potem je poteza ena s stolpa f na stolp t. Če je h>1, moramo največjo ploščico enkrat v zaporedju potez premakniti s stolpa f na drug stolp, po možnosti na stolp t. Edino stanje, ki dovoljuje to potezo, je kadar so vse druge manjše ploščice na stolpu r. Zato mora vseh prvih h-1 manjših ploščic iti s stolpa f na r. Nato se premakne največja ploščica in nazadnje h-1 manjših ploščic s stolpa r na končni stolp t. Prisotnost največje ploščice ne ovira drugih premikov h-1 manjših ploščic in se ga lahko trenutno prezre. Sedaj se problem prevede na premik h-1 ploščic z enega stolpa na drug, najprej s stolpa f na r, in nato s stolpa r na t; enak postopek je moč izvesti tudi s preimenovanjem stolpov. Uporabi se lahko enaka strategija za prevedbo problema h-1 na h-2, h-3 in tako naprej, dokler ne preostane le ena ploščica. To je rekurzija. Ta algoritem je moč prikazati na naslednji način. Ploščice po naraščajočem vrstnem redu velikosti z naravnimi števili štejemo od 0. Tako je ploščica 0 najmanjša, ploščica h-1 pa največja. Poteze h ploščic z začetnega stolpa f na končni stolp t in pomožni stolp r so:

• korak 1: če je h>1, potem prestavimo h-1 manjših ploščic s stolpa f na stolp r,
• korak 2: sedaj se lahko največja ploščica h-1 prestavi s stolpa f na stolp t,
• korak 3; če je h>1, potem ponovimo postopek in premaknemo h-1 manjših ploščic s stolpa r na stolp t.

S pomočjo matematične indukcije se lahko preprosto pokaže, da zgornji postopek, imenovan direktna metoda, vsebuje najmanjše število možnih potez, in da je to tudi enolična rešitev s tem najmanjšim številom potez. Strogo so to trditev dokazali šele leta 1981. Z rekurenčno enačbo se lahko izračuna natančno število potez rešitve: $2^{h}-1$. Pri tem koraka 1 in 3 potrebujeta $T_{h-1}$ potez, korak 2 pa eno, kar da $T_{h}=2T_{h-1}+1$.

Algoritem je moč lepo zapisati v različnih programskih jezikih kot so: Scheme, Haskell, SML, C, Java, Python ali PL/I.

Java

Rešitev hanojskih stolpov rekurzivno v jeziku Java:

// Hanoi.java
public class Hanoi {
   public static void main(String[] args) {
      int n = 3;
      hanoi(n,'A','B','C');  // prestavljamo z A na C; B je pomozna palica
   }

   private static void hanoi(int n, char a, char b, char c) {
      if (n==1) {
         System.out.println("Premakni obroc s palice "+a+" na palico "+c);
      } else {
         hanoi(n-1,a,c,b);
         hanoi(1,a,b,c);
         hanoi(n-1,b,a,c);
      }
   }
}

Rešitev s poljubnega začetnega položaja

V C:

int conf[HEIGHT]; /* Element conf[d] da trenutni položaj ploščice d. */

void move(int d, int t) {
   /* premik ploščice d na stolp t */
   conf[d] = t;
}

void hanoi(int h, int t) {
   if (h > 0) {
      int f = conf[h-1];
      if (f != t) {
         int r = 3 - f - t ;
         hanoi(h-1, r);
         move(h-1, t);
      }
      hanoi(h-1, t);
   }
}

V paskalu:

procedure Hanoi(n: integer; from, to, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', from, ' to ', to)
    else begin
        Hanoi(n-1, from, by, to);
        Hanoi(1, from, to, by);
        Hanoi(n-1, by, to, from);
    end;
End;

Rešitev z iteracijo

Java

Rešitev hanojskih stolpov iterativno v jeziku Java:

// Hanoi.java
import java.util.*;

class Zahtevek {
   public int n;
   public char a,b,c;

   public Zahtevek(int n, char a, char b, char c) {
      this.n=n;
      this.a=a;
      this.b=b;
      this.c=c;
   }
}

public class Hanoi {
   public static void main(String[] args) {
      hanoi(3,'A','B','C');  // prestavljamo z A na C; B je pomozna palica
   }

   private static void izpisiSklad(Stack s) {
      Iterator i = s.iterator();	
      System.out.println("SKLAD:");
      while (i.hasNext()) {
         Zahtevek z = (Zahtevek) i.next();
         System.out.printf("%d %s %s %s\n", z.n, z.a, z.b, z.c);
      }
      System.out.println();
   }

   private static void hanoi(int n, char a, char b, char c) {
      Stack s=new Stack(); 

      s.push(new Zahtevek(n,a,b,c));
      while (!s.empty()) {
         izpisiSklad(s);  	  	
         Zahtevek z=(Zahtevek)s.pop(); // Eksplicitna pretvorba v zahtevek
         n=z.n;
         a=z.a;
         b=z.b;
         c=z.c;
         if (n==1) {
            System.out.println("Premakni obroc s palice "+a+" na palico "+c);
         } else  { // Zahtevki v obratnem vrstnem redu obdelovanja
            s.push(new Zahtevek(n-1,b,a,c));
            s.push(new Zahtevek(1,a,b,c));
            s.push(new Zahtevek(n-1,a,c,b));
         }
      }
   }
}

Nerekurzivna rešitev

Seznam premikov ploščic, ki jih da rekurzivni algoritem, kaže več značilnosti. Če štejemo premike od 1, je številka ploščice, ki jo je treba premakniti v potezi m, enaka številu kolikokrat je m deljiv z 2. Zato se v vsaki lihi potezi prestavi najmanjša ploščica (označena z 1). Videti se tudi da, da se najmanjša ploščica premika prek stolpov f, t, r, f, t, r, itd. za liho višino stolpa in prek stolpov f, r, t, f, r, t, itd. za sodo višino stolpa. Ta ugotovitev da naslednji algoritem, ki je preprostejši za premislek od rekurzivnega.

Viri

• Klavžar, Sandi (2007). »Požrešno zaporedje brez ponavljanj in problem Hanojskega stolpa«. Obzornik mat, fiz. Zv. 54, št. 5. str. str. 145-150. {{navedi revijo}}: templatestyles stripmarker v |author= na mestu 1 (pomoč)