Yazan : Şadi Evren ŞEKER

Bu yazının amacı, oldukça meşhur bir veri yapıları (data structures) problemi olan Hanoi Kulelerini (Towers of hanoi) anlatmak ve çözüm algoritmalarını açıklamaktır.

Oyun basitçe 3 direk üzerinden oynanmaktadır. Diğer bir deyişle belirli bir sayıda diskimiz ve bu diskleri yerleştirebileceğimiz 3 adet direk bulunmaktadır. Oyun kuralları aşağıdaki şekildedir:

  1. Küçük bir diskin üzerine büyük bir disk yerleştirilemez.

  2. Aynı anda sadece tek bir disk oynatılabilir.

  3. Oyun, disklerin tamamı, başlangıç durumunda olduğu gibi (küçükten büyüğe doğru), başlangıç direğinden farklı bir direğe taşındığı zaman biter.

Yukarıdaki kurallar gereği, oyunun oynanması sırasında çözüm için iki alternatif bulunur.

  1. Bütün ihtimallerin denendiği kaba kuvvet algoritması (brute force algorithm)

  2. Çözüme yönelik, adımları belirli bir algoritmanın geliştirilmesi.

İlk alternatif için de iki ihtimal bulunmaktadır, bütün ihtimalleri rast gele deneyen bir algoritma yazmak ve ya biterse demek (ki ben denedim bitmiyor : ) ) ya da geri izleme algoritması (backtracking algorithm) uygulamak.

Geri izleme algoritmasında, yapılan adımlar bir yığında (stack) tutulup, başarısızlık durumuyla karşılaşıldığında, belirli bazı adımlar geri alınarak oyun oynanabilir. Ancak bu işlemler aslında çok sayıdaki denemeyi gerektirir.

Bu yazı kapsamında, problemi çözen belirgin bir algoritma anlatılacak ve nasıl kodlanacağı tartışılacaktır.

Algoritmamız için öncelikle bir yön belirlenir. İster sağa ister sola kabul edebilirsiniz. Ancak tek bir yön belirlememiz gerekiyor. Bu yön, aslında başlangıç durumundaki direğe göre oyunun hangi direkte biteceğini belirler. Diyelim ki aşağıdaki şekilde direkler bulunsun.

Şayet sağa doğru gitmeye karar verirsek oyun 2. direkte bitecektir. Şayet sola doğru gitmeye karar verirsek oyun 3. direkte bitecektir.

Yön seçtikten hemen sonra belirtilmelidir ki, direkleri bir daireye yerleştirilmiş gibi düşünmek gerekir. Yani 1. direğin solunda 3. direk var kabulünü yapacağız.

Algoritma aşağıdaki iki basit adımdan oluşur:

  1. Disklerden 1 numaralı (en küçük diski) seçilen yöndeki ilk oynanabilecek direğe taşı

  2. Disklerden o andaki 1’den sonra gelen en küçük diski, seçili yönde oynanabilecek ilk direğe taşı ( bu adımda aslında oynanabilecek tek ihtimal vardır)

Yukarıdaki iki adım, oyun bitene kadar tekrar eder.

Örnek bir çalışmayı aşağıda anlatmaya çalışalım:

Örneğimizde, yön olarak sağ istikameti seçiyoruz. Bu durumda oyunun Direk 2’de bütün diskler toplanınca biteceğini tahmin edebiliriz. Şimdi adım adım algoritmamızı uygulayalım.

  1. adımda en küçük disk olan 1 numaralı diski sağ isitmaketteki ilk direğe taşıyoruz:

  1. adımda, bir numaralı en küçük diskten sonra gelen ilk diski sağ istikamette oynanabilecek ilk direğe oynatıyoruz. 2 numaralı direğe oynatamayız çünkü orada bulunan küçük diskin üzerine daha büyük bir disk gelmesi oyun kurallarını ihlal etmektedir. Geriye kalan tek ihtimal olan 3 numaralı direğe, 2 numaralı diski oynatıyoruz:

Algoritmamızın iki adımını da tamamladık. Oyun henüz bitmediği için algoritmanın ilk adımından devam ediyoruz ve 1 numaralı, en küçük diski tekrar seçmiş olduğumuz yön olan sağ isitmakette oynanabilecek ilk direğe oynatıyoruz:

Sıra algoritmanın ikinci adımında. Şu anda 1 numaralı diski saymazsak, oynatabileceğimiz en küçük disk, 3 numaralı ve direk 1’de bulunan disktir. Bu diski seçtiğiiz istimaketteki ilk boş direğe oynatıyoruz (aslında 1 numaralı en küçük diski saymazsak yapabileceğimiz yegane oynatma hareketini yapıyoruz)

Oyun henüz bitmiş değil. Algoritmayı baştan çalıştırmamız gerekiyor. İlk adım ile devam edelim ve en küçük diski seçtiğimiz istikametteki ilk direğe oynatalım. 1 numaralı en küçük disk şu anda direk 3’te bulunuyor. Bu direğin sağına gitmemiz gerekiyor ancak şekilde sağında direk olmadığı görülebilir. Daha önce de anlatıldığı üzere direk 3’ün sağında direk 1 var kabulü yapılarak 1 numaralı diski, 1 numaralı direğe oynatıyoruz:

Gelelim algoritmanın ikinci adımı olan, 1 numaralı en küçük diskten soran yapılabilecek tek adımı yapmaya. Şu anda 1 numaralı diski oynatmazsak, yapabileceğimiz tek hamle, direk 3’te bulunan 2 numaralı diski, direk 2’de bulunan 3 numaralı diskin üzerine taşımaktır.

Oyun henüz bitmediği için algoritmamızın ilk adımına dönerek yeniden çalıştırıyoruz ve algoritmanın ilk adımı olan 1 numaralı diski oynatmayı deniyoruz. İstikametimiz yine sağ taraf.

Sonuçta, oyunu tamamladık ve zaten başka hamle yapmamız mümkün değil.

Yukarıda da anlatıldığı üzere, şayet oyun oynanırken sağ yerine sol istikamet seçilseydi (ki okuyucu bunu kendisi de deneyebilir), oyun 3 numaraıl direkte bütün diskler toplandıktan sonra bitecekti.

Yukarıda adım adım anlatılan bu çözümü kodlaması aşağıda verilmiştir. Kodlama sırasında veri yapısı olarak yığın kullandım ve mümkün olduğunca basit bir yığın kodlaması yaptım. Sadece int tipinde veri tutan yığını daha karmaşık kodlamalar için değiştirmek okuyucunun elindedir.

Yukarıdaki kodda, basit bir yığın kodlaması bulunmaktadır. Basitçe her yığın elemanının, bir sayacı ve verileri tutan bir dizisi bulunmakta, dizi en fazla 3 disk alacağı için 3 boyutunda tanımlanmaktadır. Ayrıca kodda, push fonskiyonu, dizinin içerisine veri koymak için ve pop fonksiyonu dizinin en sonundaki elemanı okumak için kodlanmışıtr. Top fonksiyonumuz, dizinin en üstündeki elemanı döndürür ancak diziden silmez.

Yukarıdaki kod kısmında ise oyunun oynanışı ile ilgili gerekli fonksiyonlar bulunmaktadır. 20. satırda bulunan birincidisk fonksiyonu, 1 numaaralı, en küçük diskin hangi direkte olduğunu bulmaktadır. 25. satırda başlayan enkucuk dis fonksiyonu ise 29. satırda bulunan if koşulu gereği, 1 numaralı en küçük diskten sonraki en küçük diski bulmaktadır.

oynarmi fonksiyonu (satır 35), verilen iki direk arasında disk hareketinin mümkün olup olmadığına bakar. Oynamanın iki ihtimali vardır, ya hedef direkte hiç disk yoktur ya da hedef direkteki disk, oynatmak istediğimiz direkteki diskten küçüktür.

Oyunbittimi fonksiyonu ise, oyunun başlangıcında disklerin bulunduğu 0 numaralı direkte hiç disk kalmaması ve diğer iki direkten birisinde 3 diskin de bulunması durumunu kontrol eder.

Print fonksiyonu, ekran çıktısı olarak gösterilen disk durumlarını ve adım sayısını basan fonksiyondur.

Oyna fonksiynu ise, bir direkten diğer direğe diski oynatan fonksiyondur. Her oynama bir adım olarak kabul edileceğinden adım değeri artar ve her oynamadan sonra ekrana direklerin durumu basılır.

Kodun çalıştığı ana fonksiyon yukarıda verilmiştir. Buradaki işlemler sırasıyla:

66-67 arasında bütün yığınların sayaçları 0 yapılmıştır. Bu durum yığınların boş olduğu anlamına da gelmektedir ve ayrıca bu yığınlara push yapılması halinde sayaç değerini arttırmak için başlangıç değeri kabul edilir.

68-69 satırlar arasında, ilk 3 disk, 0 numaralı yığına (direğe) yerleştirilmiştir. Bu oyunun başlangıç durumu olarak kabul edilir.

Ardından 70. satırda başlangıç durumumuzu ekrana basark algoritmamıza başlıyoruz.

71-95 arasındaki satırlar, ana döngü olup, oyun bitmedikçe bu döngüden çıkılmayacaktır. Algoritmayı anlattığım yukarıdaki şekillerdende fark edileceği üzere algoritmamızın 2 adımı bulunmakta ve oyun bu iki adımın arasında da bitebilmektedir. Yani 1. adım tamamlandıktan sonra 2. adıma geçilmeden oyunun bitme ihtimali bulunmaktadır. Bu durum 83. satırda bulunan if kontrolü ile kontrol edilmekte ve şayet oyun bittiyse 84. satırda bulunan break komutu ile 71. satırda başladığımız döngü kırılmaktadır.

Algoritmamızın 2 adımından ilki, en küçük diski oynatma adımıdır. Bu adım için 72. satıda, en küçük diskin hangi direkte olduğunu bulmak ile başlayan ve ardından, en küçük diski oynatabileceğimiz ve tanımlı olan yöndeki ilk direği bulma adımları gerçekleştirilir. Burada 75 ve 80. adımlar arasında, uygun olan ilk direk aranmaktadır. Dikkat edileceği üzere direk sayısı 2den fazla olduğu durumlarda, direk sayısı başa dönmektedir. Bu sayede direklerin bir daire şeklind yelerştirildiği düşünülebilir. Yani 2. direğin sağında 0. direk bulunmaktadır.

Diskimizin hangi direkten hangi direğe gideceğini bulduktan sonra oynama işlemi yapılır ve ardından, daha önce bahsettiğim oyunun bitip bitmediği kontrol edilir.

85-92 satırlar arasında ise algoritmanın ikinci adımı olan, 1 numaralı en küçük diskten sonraki en küçük diski oynatma işlemi yapılmaktadır. Buna göre en küçük disk bulunur ve bu diskin oynayabileceği yine aynı yöndeki ilk müsait direk aranır (zaten bu direğin tek direk olduğunu hatırlayınız). Bir önceki adıma benzer şekilde diskin hangi direkten hangi direğe gideceği bulunduktan sonra oynatma işlemi yapılır.

Yukarıdaki kodun çalışan hali aşağıda verilmiştir:

1. adim 
0. direk:3      2       1       
1. direk:
2. direk:
push 1 2. adim 
0. direk:3      2       
1. direk:1      
2. direk:
push 2 3. adim 
0. direk:3      
1. direk:1      
2. direk:2      
push 1 4. adim 
0. direk:3      
1. direk:
2. direk:2      1       
push 3 5. adim 
0. direk:
1. direk:3      
2. direk:2      1       
push 1 6. adim 
0. direk:1      
1. direk:3      
2. direk:2      
push 2 7. adim 
0. direk:1      
1. direk:3      2       
2. direk:
push 1 8. adim 
0. direk:
1. direk:3      2       1       
2. direk:
oyun bitti
new-host-2:~ sadievrenseker$

Yukarıdaki çalışmada da görüldüğü üzere, oyunun başında 3 diskte ilk direkte bulunurken oyun sonunda bütün diskler 1 numaralı direğe taşınmıştır.


Yorumlar

  1. mustafa

    hocam bu soru recursive olarak yazımını anlayabilmek için aynı şekilde mi inceleyip düşünmemiz gerekiyor? bir süredir uğraşıyorum yapamadım.

mustafa için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir