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

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 Kuleleri Nasıl Çözülür?

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ız, 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 istiyoruz. Öyleyse önce bir disk için problemi çözmeliyiz. Bir disk için problemi çözdüğümüzde geriye fazladan olan ikinci disk kalacak. Bunu da hedef konum olan, sağ sütuna koyabilirim. Öyleyse bir disk için problemi, ortada çözmeliyiz.

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

Üç 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.

Dört Diskli Problemin Çözümü

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 sonraki adım, üç 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. Üç disk problemini çözdük ve üç disk de ortada. Böylelikle dördüncü ve en büyük olanı sağa koyabiliriz. İş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 ediniz. 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.

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

Aslında üç disk probleminin çözümü olan $(3+1+3)$ de $(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))$

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:

$m=2{}^x-1$