Hanoi Kuleleri ve Çözümü

Hanoi kuleleri, 1883 yılında E. Lucas tarafından icat edilmiş bir bulmacadır. Bu bulmacadaki amaç, sol tarafta üst üste duran diskleri, her seferinde bir disk hareket ettirmek kaydıyla, sağ tarafa taşımaktır. Bu sırada hiçbir disk, kendinden küçük olanın üstüne konulamaz. Amaç, mümkün olan en az hamle sayısıyla oyunu tamamlamaktır. Disk sayısı arttıkça, minimum hamle sayısı da değişmektedir.

Hanoi kulelerinin çözümü için en basitten ilerleyelim ve yalnızca bir disk olduğunu düşünelim. Bu durumda yalnızca bir hamlede bu diski sağ tarafa alarak problemi çözebiliyoruz. Peki iki disk olduğu durumda ne oluyor? Amacım, sağ tarafa bu iki diski almak. Eğer küçük olanı sağ tarafa koyarsam, bu durumda büyük olanı ortaya koymak durumunda kalırım, bu da işleri uzatır. Oysa ki ben, en büyük olan diski sağ tarafa koymayı hedefliyorum. Bu durumda küçük diski ortaya koyar, ardından büyük olanı sağa koyar, ardından da ortaya koyduğum küçük diski, sağda bekleyen büyük diskin üstüne koyarım. Böylelikle üç hamlede problem çözülmüş olur. Bir disk için bir hamle, iki disk için üç hamle yeterli oldu.

Hanoi kulelerinde üç disk için, yukarıdaki görselde çözüm gösteriliyor. Fakat bundan önce dikkatinizi çekmek istediğim nokta, çözdüğümüz iki soruda, yaptığımız hamlelerin nasıl olduğu? Bir diskte, ilk hamlemiz sağ sütuna oldu. İki diskte ise ilk hamlemiz orta sütuna oldu. Üç diskte ise ilk hamlemiz sağ sütuna olacak. Dikkat edin, problem aslında kendi içerisinde alt problemlere ayrılmış durumda. Güzel bir dinamik programlama örneği.
İki diskte, iki diski de sağ tarafa almak istiyorum. Öyleyse önce bir disk için problemi çözmeliyim. Bir disk için problemi çözdüğümde, geriye fazladan olan ikinci disk kalacak. Bunu da hedef konum olan, sağ sütuna koyabilirim. Öyleyse bir disk için problemi, ortada çözmeliyim.
Aynı mantığı üç disk için düşünelim. Üç diski sağ tarafa taşımak istiyorum. Öyleyse iki diski ortada toplamalıyım ki, fazladan olan en büyük disk sağ tarafa gelebilsin. İki diski ortada toplayabilmek için ise, bir üstteki adımın geçerli olduğunu göreceksiniz. Küçük olanı en sağa almalıyım ki, ikinci disk ortaya gelebilsin. Bu yüzden, üç diskli problemde, ilk hamle en sağa koyarak başlıyor.
Üç diskli problemin çözümünde, ilk hamlenin, bir diskli problemin çözümü, üçüncü hamlenin de iki diskli problemin çözümü olduğuna dikkat edin. Üç disk problemi, yedi basamakta çözüldüğüne göre, dört disk problemini çözerken, yedinci basamakta üç disk problemini çözmüş olmalıyız.

Hanoi Kuleleri

Dört Diskli Problemin Çözümü

Hanoi kulelerinde dört diskli problemin çözümü de ele aldıktan sonra, konunun rahatça kavranacağını düşünüyorum. Daha önce bahsettiğimiz gibi, ilk önce yapmamız gereken hamleyi bulmalıyız. Bir diskte sağda, iki diskte ortada, üç diskte sağda başlamıştık. Öyleyse dört diskte ortada başlamalıyız. Çünkü en küçüğü ortaya alırsak, bir büyüğünü en sağa alıp, küçüğü de onun üstüne alarak, üç hamlede Hanoi kulelerinin iki disk problemini çözmüş oluruz. Bundan sonra işlem üç disk problemini çözmek olur.
Orta kısım boş olduğuna göre, üçüncü disk buraya gelir. En sağdaki küçük disk sola geçer, ortanca ortaya gelir ve küçük tekrar ortaya gelir. Böylelikle üç disk problemi çözülmüş olur ve işte işin açıklaması. Üç disk problemini çözdük ve üç disk de ortada. Böylelikle dördüncü ve en büyük olanı sağa koyabilirim. İşte tam bu sebepten ilk hamleyi ortaya yaptık.
Bu noktadan sonrası, sanki en sağda büyük bir disk yokmuş gibi düşünülerek çözülebilir. Amaç, ortadaki üç diski sağa almaktır. Küçük sağa alınır, ortanca sola, ardından küçük sola, büyük sağa. Böylelikle problem iki diske düşer. Küçük ortaya, büyük sağa, küçük sağa ve problem çözülmüştür.

Hamle sayılarına dikkat etmenizi istiyorum. Birinci hamle ile bir disk problemini çözdük, üçüncü hamle ile iki disk, yedinci hamle ile üçüncü disk problemini çözdük. Toplamda 15 hamle ile, dört disk problemini de çözmüş olduk. İşin matematiğine inebiliriz.

Formülasyon

Hanoi kulelerinde dört disk problemininin çözümü 15 hamlede gerçekleşti, üç diskin 7, iki diskin 3, bir diskin 1. Burada yakalayacağımız nokta, aslında yukarıdaki algoritmada geçiyor. Dikkatle inceleyelim.
Üç diski ortada toplamamız 7 hamle almıştır, bundan sonraki 1 hamle, dördüncü diske sağa almaktır. Sonraki hamle ise, 7 hamlede üç diski, bu en büyük diskin üzerine almaktır. Yani yapılan işlem sayısı 7+1+7=15'tir.
Benzeri şekilde üç disk problemini ele alalım. Üç disk probleminde, ilk 3 hamle ile iki disk problemi çözülür, 1 hamle ile büyük disk hedefe konulur, sonraki 3 hamle ile iki disk üstüne eklenir. Yani yapılan işlem sayısı 3+1+3 = 7'dir.
Yani aslında daha alt problemlere ayrılmış şekilde yazacak olursak, dört disk problemi 7+1+7 şeklinden aşağıdaki şekle gelir.

Aslında üç disk probleminin çözümü olan (3+1+3) de (1+(1)+1)+1+(1+(1)+1) şeklindedir. Böylelikle ifade,

halini alır. Problemin nasıl iç içe olduğu, çok daha belirgin bir şekilde ortaya çıktı. Eğer bu sonuçları doğru şekilde formülize etmek istersek, $x$ disk sayısı olmak üzere, minimum hamle sayısı $m$ aşağıdaki şekilde hesaplanabilir.

Böylelikle x=1 için m=1, x=2 için m=3, x=3 için m=7, x=4 için m=15, x=5 için m=31, x=6 için m=63... olarak bulunur. Hanoi kulelerinin mantığını bir kez kavradığınızda, fazla hamle sayısından ötürü sıkılmayacağınız kadar çok diskli problemini, sorunsuz bir şekilde tek seferde tamamlayabilirsiniz.

---

Hazırlayan:Ögetay Kayalı
Referanslar
1. Mathworld Wolfram, <http://mathworld.wolfram.com/TowerofHanoi.html>
Bu yazı ilk olarak 26 Ağustos 2016 tarihinde yayınlanmıştır.