Hanojski stolpi

Hanojski stolpi 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 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šč na drug kupček plošč z najmanjšim možnim številom premikov, 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. 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 premikov 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 manihi. Tempelj ali samostan se lahko nahaja v različnih delih sveta, med njimi tudi v Hanoju v Vietnamu, in je lahko povezan s katerikoli 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 premik 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.

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 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 premiku m, enaka številu kolikokrat je m deljiv z 2. Zato se v vsakem lihem premiku 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 lih stolp in prek stolpov f, r, t, f, r, t, itd. za sod stolp. Ta ugotovitev da naslednji algoritem, ki je preprostejši za premislek od rekurzivnega.