Hanoi Kuleleri: Özyinelemenin En Zarif Bulmacası

Brahma'nın altın diskleri

Efsaneye göre Hindistan'da bir tapınakta üç elmas çubuk vardır. Birinin üzerinde Brahma'nın koyduğu 64 altın disk bulunur — en büyüğü altta, üst üste küçülerek. Rahiplerin görevi tüm diskleri başka bir çubuğa taşımaktır. Üç kural var:

1. Tek seferde tek disk taşınır.
2. Disk yalnızca üç çubuktan birinin en üstüne konur.
3. Büyük disk asla küçüğün üstüne konulamaz.

Efsaneye göre tüm diskler taşındığında evren sona erecektir. Korkulacak bir şey var mı?

Bulmacayı bu hikâyeyle popüler yapan kişi Fransız matematikçi Édouard Lucas (1883). Lucas oyuncak versiyonunu satılığa çıkardığında matematikçiler ve bilgisayar bilimciler için sıçramalı bir örnek doğmuştu.

Algoritma: kendine seslenen çözüm

$n$ diski A'dan C'ye, B'yi yardımcı çubuk olarak kullanarak taşıyalım. Üç adım:

1. Üstteki $n-1$ diski A'dan B'ye taşı.
2. En alttaki büyük diski A'dan C'ye taşı (1 hamle).
3. B'deki $n-1$ diski C'ye taşı.

Dikkat: 1. ve 3. adımlar aynı problemin küçük versiyonu. Algoritma kendisini çağırıyor — bu özyineleme.

function hanoi(n, kaynak, hedef, yardımcı):
    if n == 1:
        print "Taşı: " + kaynak + " -> " + hedef
        return
    hanoi(n-1, kaynak, yardımcı, hedef)
    print "Taşı: " + kaynak + " -> " + hedef
    hanoi(n-1, yardımcı, hedef, kaynak)

Sadece dört satır. Bu kadar kısa bir kod milyonlarca hamlelik düzgün bir koreografi üretir. Bu yüzden hemen her bilgisayar bilimi dersinde özyinelemenin ilk örneğidir.

Kaç hamlede biter?

$T(n)$ toplam hamle sayısı olsun. Algoritma şunu söyler:

$T(n) = 2T(n-1) + 1, \quad T(1) = 1$

Bu özyineleme bağıntısı çözüldüğünde:

$T(n) = 2^n - 1$

Yani $n$ diske karşılık $2^n - 1$ hamle. Küçük örnekler:

• $T(3) = 7$ hamle
• $T(10) = 1023$ hamle
• $T(20) \approx 10^6$ hamle
• $T(64) = 18\,446\,744\,073\,709\,551\,615 \approx 1.8 \times 10^{19}$

Brahma'nın rahipleri ne zaman bitirir?

Saniyede bir hamle yapsalar:

$\frac{1.8 \times 10^{19}}{60 \cdot 60 \cdot 24 \cdot 365} \approx 5.85 \times 10^{11} \text{ yıl}$

Yaklaşık 585 milyar yıl. Evrenin şu anki yaşı yaklaşık 13.8 milyar yıl olduğuna göre rahipler işin %2.4'ünü ancak bitirmişlerdir. Endişeye gerek yok.

Üstel büyümenin gözle görülür dersi

Hanoi Kuleleri'nin en güçlü tarafı, üstel patlamayı somutlaştırmasıdır. Bir disk eklediğinizde hamle sayısı iki katına çıkar artı bir. 64 disk için gereken süre, 63 disk için gerekenin tam iki katıdır. Bu, kriptografide neden 256 bitlik anahtarlar kırılmaz olarak kabul edildiğini açıklayan aynı patlamadır.

Aynı zamanda NP-zor problemleri "bilgisayar daha hızlı olsa çözeriz" yanılgısının panzehridir: bilgisayar 1000 kat hızlansa, çözebileceğiniz problem boyutu sadece $\log_2 1000 \approx 10$ disk artar. Donanım hızı üstel duvarı yıkamaz.

Tek çözüm var mı?

Evet — minimum hamle sayısıyla çözüm tektir (simetri hariç). Hatta bir başka güzellik: hamleleri ikili sayma ile eşleştirebilirsiniz. $k$. hamlede hangi diskin hareket ettiği, $k$ sayısının ikili gösterimindeki en sağdaki 1'in konumu ile belirlenir. Yani bulmacanın yapısı doğrudan Gray kodu ve ikili sayma ile aynı iskelete sahiptir.

Bir bulmaca, bir efsane, bir özyineleme örneği, bir kombinatorik şekil — Hanoi Kuleleri tek bir küçük oyuncakta matematiğin pek çok dalını birden öğretir. Lucas neden başarılı? Çünkü o bir oyuncak değil; bir fikrin maket halidir.