Makale Özeti

Gerçekte bir matematik problemi ve ya bir bulmaca olarak tanımlayabileceğimiz bu oyun aslında -efsaneye göre- çok uzun yıllardır oynanmakta. Çözümü ise oldukça kolay.

Makale

 Towers Of Hanoi (Hanoi Kuleleri)

    Gerçekte bir matematik problemi ve ya bir bulmaca olarak tanımlayabileceğimiz bu oyun aslında -efsaneye göre- çok uzun yıllardır oynanmakta. Bir çoğumuz bunu duymuştur mutlaka ama bilmeyenler için biraz anlatayım. Oyun üç adet çubuk ve bu çubuklar üzerinde, küçükten büyüğe doğru sıralanmış disklerin belirli kurallar dahilinde diger bir çubuğa taşınmasından oluşuyor.

    Kurallar oyunun materyalleri kadar basit aslında. Her seferinde yalnızca bir disk hareket ettirilebilir, bir çubukta disklerin sıralanması küçük disk büyük diskin üzerinde olacak şekilde durabilir, kesinlikle bir diskin üzerine kendinden daha büyük bir disk gelemez.

    Efsane ise oldukça ilginç. Hanoi, şu an Vietnam'da bulununan eski bir şehir ve orada, çok uzun yıllar önce çatısı dünyanın merkezini odaklayan bir tapınak yaptırmış zamanın büyük imparatoru Fo Hi.  Bu kayıp bir tapınakta, başlangıçta tek bir çubuk üzerinde bulunan 64 adet altın diski asırlar boyu, kuralı bozmadan, geceli gündüzlü diğer çubuğa taşımaya çalışmışlar. Denir ki, bu disklerin taşınması bittiği anda bütün evrenin sonun gelecektir.

    Bu efsaneyi günümüze taşıyan kişi ise Fransız Matematikçi Edouard Lucas'tır. Lucas 1883'te bu bulmacadan, aynen yukarıda bahsettiğimiz şekilde bahsetmiş ve efsane dışında da, ne tapınağa ne de gerçekten bu oyunun oynandığına ait bir bilgiye ulaşılamamıştır. Bu nedenle Lucas'ın bu bulmacayı kendisi mi uydurduğu yoksa gerçekten efsane mi olduğu tam olarak bilinemese de, algoritma dünyasında büyük yer edinen problemlerden biridir.

    Matemtiksel olarak çözmek gerekir ise, her harekin doğru yapıldığını düşünürsek, ardışıl tam 264 -1 hareket gereklidir. Her hareketin çok hızlı (!) hareket eden bu rahipler tarafından 1 saniyede yapıldığını düşünüp bir hesap yaparsak yaklasık 585 milyar yıla ihtiyaçları var. Son yapılan hesaplamalara göre evrenin yaşı (bing bang'ten  bu yana geçen süre) 13.7 milyar yıl . Dolayısıyla henüz korkacak birsey yok. :)

    Programımıza geçelim.

    Uygulamamız ekran görüntüsü olarak aşağıda gördüğünüz animasyon şeklinde olacak:

   

        Uygulamamız algoritmik çözüm olarak recursive methodu kullanmaktadır ki, bu problemin çözümü için en iyi yöntemlerden biridir. İteratif yöntem, (bol bol for - while vs.. döngüleri) pek uygun değildir ve implementasyonu oldukça zordur.

    Çözümün dışında yaptığım tek şey, o anki durumu ekrana çizdirmek için Drawing namespace'ini kullanmaktır. Kodları birlikte inceleyelim.

  private void Tasi(int TasinacakDiskSayisi, ArrayList Source, ArrayList Destination, ArrayList Empty)
        {
            if (TasinacakDiskSayisi > 0)
            {
               
                Tasi(TasinacakDiskSayisi - 1, Source, Empty, Destination);
                Destination.Insert(0, Source[0]);
                Source.RemoveAt(0);
                DiskleriCiz();
                System.Threading.Thread.Sleep( 150 *  trackBar1.Value );
      
                  if (TasinacakDiskSayisi > 1)
                     Tasi(TasinacakDiskSayisi - 1, Empty, Destination, Source);
                   
            }
}

    Çözüm için bu recursive fonksiyon yeterli. Yaptigimiz tek sey, hangi cubuktan hangi cubuga diskin gideceğini iyi analiz etmek.

    Disk objemize gelince, cizilebilir bir disk objesi icin, bir dikdortgene ve gercekte baktığımızda disk ile bizi bağdaştıracak propertylere ihtiyacımız var. Bunlar AitOlduguCubukNo, CubukUzerindekiToplamDisk, CubukUzerindekiSira, BuyuklukNo ve ek olarak, disk için çizeceğimiz dikdörtgene ihtiyacımız var : DiskRectangle. Disk sınıfı üzerinde, propertylerde yaptığımız işlemin tamamı çizim için gereken pixel boyutlarının ayarlanmasıdır. (Pixel boyutlarının hesaplanması mümkün olduğunca kodun anlaşılabilir olması için sabit değerler kullanılmış ve formun boyutu değiştirilemeyecek bir şekle getirilmiştir. Kod geliştirilerek, formun size'ı değiştiğinde disk ve çubuk boyutları değişecek bir şekle getirilebilir.)

  public class Disk
    {
        private int cubukUzerindekiToplamDisk;
        private int cubukUzerindekiSira;
        private int cubukNo;
        private int buyuklukNo;
        private Rectangle r;
       
        public int AitOlduguCubukNo
        {
            get { return cubukNo; }
            set
            {
                cubukNo = value;
                r.X = 150 - 10 * buyuklukNo + (200 * (cubukNo - 1));
            }
        }
        public int CubukUzerindekiToplamDisk
        {
            get { return cubukUzerindekiToplamDisk; }
            set
            {
                cubukUzerindekiToplamDisk = value;
                r.Y = 415 - 10 * (cubukUzerindekiToplamDisk - cubukUzerindekiSira);
 
            }
        }
        public int CubukUzerindekiSira
        {
            get { return cubukUzerindekiSira; }
            set
            {
                cubukUzerindekiSira = value;
                r.Y = 415 - 10 * (cubukUzerindekiToplamDisk - cubukUzerindekiSira);
            }
        }
        public Rectangle DiskRectangle
        {
            get { return r; }
        }
        public int BuyuklukNo
        {
            get { return buyuklukNo; }
            set
            {
                buyuklukNo = value;
                r.X = 150 - 10 * buyuklukNo + (200 * (cubukNo - 1));
                r.Height = 10;
                r.Width = 10 + 20 * buyuklukNo;
            }
        }
 
    }

    Ve son olarak, çubukları ve diskleri çizmek kaldı. Bunun için de aşağıdaki iki fonksiyonu kullanıyoruz:

private void FormCiz()
        {
            Graphics g = panel1.CreateGraphics();
            g.Clear(Color.WhiteSmoke);
            System.Drawing.Rectangle r = new Rectangle(150, 10, 10, 415);
            Pen p = new Pen(Color.Red, 2);
            g.DrawRectangle(p, r);
            r = new Rectangle(350, 10, 10, 415);
            g.DrawRectangle(p, r);
            r = new Rectangle(550, 10, 10, 415);
            g.DrawRectangle(p, r);
            //cubuklar cizildi.
        }
 private void DiskleriCiz()
        {
            FormCiz();
            Graphics g = panel1.CreateGraphics();
            Pen p = new Pen(Color.Blue , 2);
 
            for (int i = 0; i < Cubuk1.Count; i++ )
            {
                Disk d = (Disk )Cubuk1[i];
                d.CubukUzerindekiSira = i+1;
                d.CubukUzerindekiToplamDisk = Cubuk1.Count;
                d.AitOlduguCubukNo = 1;
                g.DrawRectangle( p, d.DiskRectangle);
            }
 
            for (int i = 0; i < Cubuk2.Count; i++)
            {
                Disk d = (Disk )Cubuk2[i];
                d.CubukUzerindekiSira = i+1;
                d.CubukUzerindekiToplamDisk = Cubuk2.Count;
                d.AitOlduguCubukNo = 2;
                g.DrawRectangle(p, d.DiskRectangle);
            }
 
            for (int i = 0; i < Cubuk3.Count; i++)
            {
                Disk d = (Disk)Cubuk3[i];
                d.CubukUzerindekiSira = i + 1;
                d.CubukUzerindekiToplamDisk = Cubuk3.Count;
                d.AitOlduguCubukNo = 3;
                g.DrawRectangle(p, d.DiskRectangle);
            }
        }

    Sonuç olarak artık çalışan ve hızlı bir şekilde çözüme giden bir "Towers of Hanoi" programımız var. Özellikle programcılığa yeni başlayan ve ya recursive fonksiyonlar ile araları pek iyi olmayan arkadasların çözüm bölümünü dikkatle incelemesi çok faydalı olacaktır.

Kivanc OZUOLMEZ

Proje