Hanoi Kuleleri Nasıl Çözülür?

Hanoi kuleleri, 1883 yılında E. Lucas tarafından icat edilmiş tek bulmacadır. Bu bulmacadaki amaç; sol tarafta üst üste duran diskleri, her arasında biri seferinde tek disk hareket ettirmek kaydıyla, sağ tarafa taşımaktır. Bu sırada hiçbir disk, kendinden küçük olanın üstüne başlıklamaz. Amaç, mümkün olan asgari hamle sayısıyla oyunu ikmal etmektı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 tek disk olduğunu düşünelim. Bu durumda yalnızca tek hamlede bu diski sağ tarafa alarak sualni çözebiliyoruz. Peki ikisi disk olduğu durumda ne oluyor? Amacımız, sağ tarafa bu ikisi diski edinmek. Eğer küçük olanı sağ tarafa koyarsam bu durumda büyük olanı ortaya koydu 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 sualn çözülmüş olur. Bir disk için tek hamle, ikisi disk için üç hamle yeterlilik 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 ikisi sualda, yaptığımız hamlelerin nasıl olduğu. Bir diskte, birinci hamlemiz sağ sütuna oldu. İki diskte ise birinci hamlemiz vasat sütuna oldu. Üç diskte ise birinci hamlemiz sağ sütuna olacak. Dikkat edin, sualn aslında öz içerisinde dip sualnlere ayrılmış durumda. Güzel tek dinamik programlama örneği.

İki diskte, ikisi diski da sağ tarafa eldeetti istiyoruz. Öyleyse önce tek disk için sualni çözmeliyiz. Bir disk için sualni çözdüğümüzde geriye fazladan olan sonuncu disk kalacak. Bunu da hedefleri başlıkm olan, sağ sütuna koyabilirim. Öyleyse tek disk için sualni, ortada çözmeliyiz.

Aynı mantığı üç disk için düşünelim. Üç diski sağ tarafa taşımak istiyoruz. Öyleyse ikisi diski ortada toplamalıyız ki fazladan olan en büyük disk sağ tarafa gelebilsin. İki diski ortada toplayavakıf oldu içinse tek üstteki adımın geçerli olduğunu göreceksiniz. Küçük olanı en sağa almalıyız ki sonuncu disk ortaya gelebilsin. Bu yüzden, üç diskli sualnde, birinci hamle en sağa koymaktır.

Üç diskli sualnin çözümünde, birinci hamlenin, tek diskli sualnin çözümü, üçüncü hamlenin da ikisi diskli sualnin çözümü olduğuna ilgi edin. Üç disk sualni, 7 basamakta çözüldüğüne göre, dört disk sualnini çözerken, yedinci basamakta üç disk sualnini çözmüş olmalıyız.

Dört Diskli Problemin Çözümü

Daha önce bahsettiğimiz gibi birinci önce, yapmamız lüzumen hamleyi bulmalıyız. Bir diskte sağda, ikisi diskte ortada, üç diskte sağda başlamıştık. Öyleyse dört diskte ortada başlamalıyız. Çünkü en küçüğü ortaya alırsak tek büyüğünü en sağa alıp küçüğü da onun üstüne alarak üç hamlede Hanoi kulelerinin ikisi disk sualnini çözmüş oluruz. Bundan sonrakiler adım, üç disk sualnini çö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 hasılat ve küçük tekrar ortaya gelir. Böylelikle üç disk sualni çözülmüş olur. Üç disk sualnini çözdük ve üç disk da ortada. Böylelikle dördüncü ve en büyük olanı sağa koyabiliriz. İşte hepsi bu sebepten birinci hamleyi ortaya yaptık.

Bu noktadan sonrası, sanki en sağda büyük tek disk yokmuş gibi düşünülerek çözülebilir. Amaç, ortadaki üç diski sağa edinmektır. Küçük sağa alınır; ortanca sola, ardından küçük sola, büyük sağa. Böylelikle sualn ikisi diske düşer. Küçük ortaya, büyük sağa, küçük sağa ve sualn çözülmüştür.

Hamle sayılarına ilgi ediniz. Birinci hamle ile tek disk sualnini çözdük, üçüncü hamle ile ikisi disk, yedinci hamle ile üçüncü disk sualnini çözdük. Toplamda 15 hamle ile dört disk sualnini da çözmüş olduk. İşin matematiğine inebiliriz.

Formülasyon

Hanoi kulelerinde dört disk sualnininin çözümü 15 hamlede gerçekleşti. Üç diskin 7, ikisi diskin 3, tek 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 sonrakiler 1 hamle, dördüncü diske sağa edinmektır. Sonraki hamle ise 7 hamlede üç diski, bu en büyük diskin üzerine edinmektır. Yani yapılan işlem sayısı 7+1+7=157+1+7=157+1+7=15'tir.

Benzeri şekilde üç disk sualnini ele alalım. Üç disk sualninde, birinci 3 hamle ile ikisi disk sualni çözülür, 1 hamle ile büyük disk hedefe başlıklur, sonrakiler 3 hamle ile ikisi disk üstüne eklenir. Yani yapılan işlem sayısı 3+1+3=73+1+3 = 73+1+3=7'dir.

Yani aslında daha dip sualnlere ayrılmış şekilde yazacak olursak dört disk sualni 7+1+77+1+77+1+7 şeklinden aşağıdaki şekle gelir.

7+7+1=(3+(1)+3)+1+(3+(1)+3)7+7+1 = (3+(1)+3)+1+(3+(1)+3)7+7+1=(3+(1)+3)+1+(3+(1)+3)

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

((1+(1)+1)+1+(1+(1)+1))+1+((1+(1)+1)+1+(1+(1)+1))((1+(1)+1)+1+(1+(1)+1))+1+((1+(1)+1)+1+(1+(1)+1))((1+(1)+1)+1+(1+(1)+1))+1+((1+(1)+1)+1+(1+(1)+1))

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

m=2x−1m=2^x-1m=2x−1