Oyun Treni / Rehberler / Hanoi Kuleleri Çözümü: En Az Hamle Formülü (2ⁿ − 1) ve Adım Adım Çözüm
Çözüm · Bulmaca · Matematik

Hanoi Kuleleri Çözümü: En Az Hamle Formülü (2ⁿ − 1) ve Adım Adım Çözüm

Oyun Treni · Satranç Akademisi ·

Kısaca

n diskli Hanoi Kuleleri en az 2ⁿ − 1 hamlede çözülür: 3 disk 7, 4 disk 15, 5 disk 31 hamle. Yöntem her seviyede aynıdır: üstteki n − 1 diski yardımcı çubuğa taşı, en büyük diski hedef çubuğa koy, sonra n − 1 diski onun üzerine taşı.

3 diskin 7 hamlelik çözümü

Çubuklar soldan sağa A, B ve C olsun. Bütün diskler A’da; hedef C.

  1. Küçük disk A → C
  2. Orta disk A → B
  3. Küçük disk C → B
  4. Büyük disk A → C
  5. Küçük disk B → A
  6. Orta disk B → C
  7. Küçük disk A → C

Disk sayısına göre en az hamle

DiskEn az hamleHesap
372³ − 1
4152⁴ − 1
5312⁵ − 1
6632⁶ − 1
71272⁷ − 1
82552⁸ − 1

Neden 2ⁿ − 1?

En büyük diski taşıyabilmek için üstündeki n − 1 diskin tamamı başka bir çubukta olmalıdır. Yani önce n − 1 disklik bulmacayı çözer, en büyük diski bir hamlede taşır, sonra n − 1 disklik bulmacayı yeniden çözersin. Hamle sayısı her diskte iki katına çıkıp bir artar: 1, 3, 7, 15, 31…

Bu düşünme biçimine özyineleme denir: büyük bir problemi, kendisinin daha küçük bir kopyasını çözerek çözmek. Bilgisayar biliminde en çok öğretilen örneklerden biridir.

Pratik ipucu: küçük disk hep aynı yöne

  • Tek ve çift hamleleri ayır: tek numaralı hamlelerde en küçük disk hep aynı yönde döner (disk sayısı tekse A → C → B → A…, çiftse A → B → C → A…).
  • Çift numaralı hamlelerde küçük diske dokunmadan yapılabilecek tek geçerli hamleyi yap.
  • Bu iki kuralla, hiç düşünmeden en kısa çözümü uygulayabilirsin.

64 disk efsanesi

Bulmacayı 1883'te Fransız matematikçi Édouard Lucas tanıttı ve onu bir efsaneyle süsledi: rahipler 64 altın diski taşıyınca dünyanın sonu gelecekti. 64 disk için gereken hamle sayısı 2⁶⁴ − 1, yani yaklaşık 18,4 kentilyondur. Saniyede bir hamleyle bu iş yüz milyarlarca yıl sürer.

Oyun Treni'ni yükle!Hızlı erişim için ekranına ekle.