Hanoi Kuleleri
Brahma’nın/Lucas’ın Kuleleri olarak da bilinen ve çoğunlukla Hanoi Kuleleri adıyla ün salmış olan bilmeceyi hiç duymuş muydunuz ? Algoritma derslerinin vazgeçilmez problemlerinden olan Hanoi Kuleleri’ne ait bilmeniz gereken her şey makalemizde.
Hanoi Kuleleri Nedir ?
Bizi Sosyal Medyadan Takip Edin
Efsaneye göre Hindistan’daki antik bir tapınakta (bazı kaynaklara göre Vietnam’ın başkenti Hanoi’deki bir tapınakta geçmektedir) geniş bir oda bulunmaktaydı ve bu odada 64 tane altın diskle çevrelenmiş 3 adet kule vardı. Yine efsaneye göre bu diskler, tapınaktaki rahipler tarafından sürekli olarak hareket ettirilmektedir. Son disk doğru yere yerleştirildiğinde bilmece tamamlanmış olacak ve dünyanın sonu gelmiş olacaktır.
Bu bilmece genellikle Brahma’nın Kulesi olarak da bilinir. Maymunlar Cehennemi: Başlangıç (Rise of the Planet of the Apes – 2011) filminde, maymunlara uygulanan bir zeka testi olarak karşımıza çıkmıştır. Bu bilmece, recursion (özyineleme) problemlerinde, parametrelerin nasıl uygulandığını ve recursive çözümlerin nasıl yapıldığını anlamak açısından pek çok dersin klasik problemi olmuştur.
Hanoi Kuleleri Bilmecesi Nasıl Çözülür ?
Klasik bir Hanoi Kulesi, 3 adet çubuk ve çubuklardan birine aşağıdan yukarıya doğru büyükten küçüğe sıralanmış n adet diskten oluşur. Bilmecenin 2 tane kuralı vardır:
1) Aynı anda sadece 1 disk hareket ettirilebilir.
2) Diskler yalnızca kendisinden daha büyük olan bir diskin üzerine yerleştirilebilir.
Bilmecenin çözümünü anlayabilmek için öncelikle recursion kavramını anlamamız gerekir.
Recursion (Özyineleme) Nedir ?
Bir fonksiyonun kendi kendini çağırmasına recursion denir. Recursion kavramını daha iyi anlayabilmek için Inception filmini düşünebiliriz. Bilmeyenler için, Inception filmindeki karakter sürekli olarak rüya içinde rüya görmekteydi. Bu döngüyü şöyle ifade edebiliriz:
Ruya()
print “Rüya Görülüyor.”
Ruya()
Recursion, aynı türden parçalara bölünebilen problemlerin çözümünde oldukça kullanışlıdır. Örneğin bir sayının faktöriyelini de recursive bir fonksiyon ile bulabiliriz. Kullanıcıdan alınan bir sayının faktöriyelini bulan programın pseudo-code’u aşağıdaki gibidir:
if n <= 1
else
return n*Factorial(n-1)
Hanoi Kuleleri Algoritması
Basit bir örnek olarak A çubuğuna dizilmiş 2 tane disk düşünelim. Amacımız bu diskleri kurallara uymak kaydıyla B çubuğuna taşımak olsun. Öncelikle 1. disk A çubuğundan C çubuğuna alınır. Sonra 2. disk A çubuğundan B çubuğuna alınır. Son olarak C’deki 1. disk, B’deki 2. diskin üzerine yerleştirilir ve puzzle çözülmüş olur. Bu çözüm 3 adımda yapılmaktadır.
A çubuğunda ilk başta 3 disk olduğunu düşünürsek, 3. diski (yani en büyük olanı) açığa çıkarmamız gerekir. Bunun için 1. ve 2. diskler C çubuğuna aktarılır. Daha sonra 3. disk B çubuğuna yerleştirilir. Son olarak da sırasıyla 1. disk A çubuğuna, 2. disk B çubuğuna ve 1. disk B çubuğuna yerleştirilerek puzzle çözülmüş olur. Bu kez adım sayısı 3+1+3 = 7 olur.
A çubuğunda ilk başta 4 disk varsa, problemi recursive bir şekilde çözmek için aşağıdaki adımlar izlenir:
1) 1., 2. ve 3. diskler A çubuğundan C çubuğuna aktarılır.
2) 4. disk A çubuğundan B çubuğuna aktarılır.
3) C çubuğundaki diskler (1,2,3) B çubuğuna aktarılır.
4 disk olduğunda 7+1+7 = 15 adımda çözüm yapılmış olur. Elde ettiğimiz sonuçlardan yola çıkarak, Hanoi Kulesi algoritmasını bir fonksiyonda şu şekilde ifade edebiliriz:
void HanoiTower(int n, char from, char aux, char to) {
if(n == 1) {
cout << “Disk 1, ” << from << ” çubuğundan ” << to << ” çubuğuna hareket ettirilmiştir.” << endl;
return;
}
else {
HanoiTower(n-1, from, to, aux);
cout << n << ” Diski, ” << from << ” çubuğundan” << to << ” çubuğuna hareket ettirilmiştir.” << endl;
HanoiTower(n-1, aux, from, to);
}
}
Bu kodda n, disk sayısını; from, diskin harekete başladığı ilk çubuğu; to, diskin hedef çubuğunu; aux ise diğer çubuğu ifade etmektedir. Tek disk olması durumu ayrı bir if komutu içinde belirtilmiştir. Birden fazla disk olması durumunda ise kod, tek bir disk kalana kadar recursive bir şekilde çözüm yapmaktadır. Bu kodu main’de şu şekilde çalıştırabiliriz:
void main() {
clrscr();
int n;
cout << “\n*****Hanoi Kulesi*****\n”;
cout << “Disk sayısını giriniz: ” << endl;
cin >> n;
HanoiTower(n, ‘A’,’ B’, ‘C’);
getch();
}
Hanoi Kuleleri - Matematiksel Açıklaması
Algoritmik çözümlerden yola çıkarak, N tane diskin bir çubuktan başka bir çubuğa geçirilmesi 2N – 1 adımda gerçekleştirilir. Tüm disklerin başka bir çubuğa en az sayıda hamleyle, buna a(N) diyeceğiz, geçirilmesi gerekmektedir. Recursive fonksiyona baktığımızda a(1) = 1, a(2) = 3 ve a(3) = 7 sonuçlarını görmekteyiz. N sayıda diskin başka bir çubuğa minimum hamlede geçmesini sağlamak için şu adımlar sırayla izlenir:
1) En üstteki N-1 tane disk son çubuğa geçirilir.
2) En alttaki disk ortanca (hedef) çubuğa geçirilir.
3) N-1 tane disk, son çubuktan ortanca çubuğa geçirilir.
Sonuç olarak aşağıdaki bağıntı elde edilir:
a(1) = 1
a(2) = 3
a(N) = 2a(N-1) + 1 ; N >= 2
Rahiplerin çok güçlü olduklarını ve her gün, her saniye 1 tane hamle yaptıklarını varsayarsak, 2^64 – 1 hamlede bilmeceyi çözmüş olacaklardır. Bu da 18,446,744,073,709,551,615 hamleye denk gelmektedir ve yaklaşık 580 milyar yıl sürecektir. Samanyolu galaksisinin 13.2 milyar yıl yaşında olduğunu ve gezegenimizin 5 milyar yıl yaşında olduğunu düşünürsek, efsanenin gerçekleşmesi için daha çok uzun bir zaman var. Yani güvendeyiz 🙂
Kaynak: https://www.hackerearth.com/blog/developers/tower-hanoi-recursion-game-algorithm-explained/
