9. yüzyıldan günümüze 1200 yıllık matematik bulmacası
Yüz Yüze, ilk bakışta basit bir okul oyunu gibi görünür: bir karede başla, 3 düz veya 2 çapraz atlayarak ilerle, mümkün olduğunca yükseğe çık. Ama bu oyunun matematik literatüründe bir akrabası var: at turu problemi (knight's tour problem). Aynı bulmaca sınıfının yüzyıllarca üzerinde çalışılmış versiyonu.
Bilinen en eski at turu örneği 9. yüzyıla ait. Hintli şair ve matematikçi Rudrata, Kavyalankara adlı eserinde at hamlelerini şiir yapısına bağladı. Rudrata'nın çözümleri 4x8 yarım satrançtahtası üzerindeydi ve atın her kareyi tam bir kez ziyaret ettiği yolları gösteriyordu. Bu sırada Avrupa henüz satrancı yeni öğreniyordu.
Sonraki birkaç yüzyıl boyunca problem matematik dünyasında uyudu. 18. yüzyıla kadar.
1759'da İsviçreli matematikçi Leonhard Euler, Solution d'une question curieuse başlıklı çalışmasında at turu problemini ilk kez sistematik olarak ele aldı. Euler, 8x8 satrançtahtasında atın hangi kareyi ziyaret edip etmediğini takip eden bir yöntem geliştirdi. "Açık tur" (atın bittiği kare başlangıç karesine bir hamle uzaktan farklı) ve "kapalı tur" (atın bittiği kareden başlangıca tek hamle ile dönülebildiği tur) arasındaki ayrımı netleştirdi.
Euler aynı zamanda problemi grafik teorisi diliyle ifade eden ilk kişiydi — o zaman henüz kavram bu ada sahip değildi. At turunu, bir grafiğin tüm köşelerini ziyaret eden Hamilton yolu olarak tanımladı (Hamilton'dan yarım yüzyıl önce).
1771'de Fransız matematikçi Alexandre-Théophile Vandermonde problemi farklı bir açıdan ele aldı. Vandermonde, simetri kullanarak at turlarını sistematik olarak inşa etmenin yollarını gösterdi. Bu yöntem, daha büyük tahtalara genelleme yapmanın temelini oluşturdu.
1823'te Alman matematikçi H. C. von Warnsdorff, problemi pratik olarak çözmenin sade bir kuralını formüle etti: her hamlede, en az geçerli devam seçeneğine sahip kareye git. Bugün bu kural Warnsdorff Kuralı olarak biliniyor.
Warnsdorff'un dehası şu fikirde: çok seçeneği olan kareler "güvenli", az seçeneği olan kareler "tehlikeli". Tehlikeliyi erken ziyaret edersen, oyunun sonunda çıkmaza düşmezsin. Kural sezgisel ama matematiksel olarak ispatlanmış optimum değil — bazı kombinasyonlarda başarısız olur. Yine de pratikte 8x8 tahtada %99'un üzerinde başarı oranıyla çalışır.
Yüz Yüze'nin ipucu sistemi de bu kuralın modernleştirilmiş bir varyantını kullanır.
20. yüzyılın sonlarında bilgisayarlar at turu probleminin sayısal sınırlarını zorladı. 1996'da Loebbing ve Wegener, 8x8 satrançtahtasında 26.534.728.821.064 farklı kapalı at turu bulunduğunu hesapladı. Brendan McKay 1997'de bu sayıyı bağımsız olarak doğruladı. Yani 26 trilyondan fazla farklı kapalı tur var — ve hâlâ tümünü açıkça listeleyebilen bir bilgisayar yok.
Modern algoritmalar at turunu çözmek için çeşitli yöntemler kullanır:
Yüz Yüze, at turu probleminin doğrudan kopyası değil. Atın "L şeklindeki" hareketi yerine üç düz veya iki çapraz hareket kullanılır. Ama matematiksel olarak aynı problem sınıfına aittir: bir grafikte Hamilton yolu arama. 100 köşeli bir grafikte mümkün olduğunca uzun bir yol bulmaya çalışıyorsun.
Bu yapısal benzerlik şu sonucu doğurur: at turu için geliştirilmiş tüm matematiksel araçlar Yüz Yüze'ye de uygulanabilir. Warnsdorff kuralı, simetri argümanları, parite kontrolleri — hepsi geçerli.
Bir farkla: at turu 8x8 tahtada her kareden başlanırsa çözülebilir (başlangıç köşede olmadığı sürece kapalı tur garanti). Yüz Yüze'de 10x10 grid ve 3-2 hareketleriyle bazı başlangıç kareleri 100'e ulaşılabilir, bazıları matematiksel olarak ulaşılamaz. Bu yüzden günlük bulmaca her gün farklı zorlukta gelir.
1200 yıl boyunca matematikçiler bu problem üzerinde çalıştı. Hâlâ bazı varyantları açık problem statüsünde duruyor — örneğin, keyfi tahta boyutları için en kısa hesaplama yöntemi. At turu problemi, görünen sadeliğin altında derin matematik barındıran bulmacaların klasik örneği.
Yüz Yüze'yi her oynayışında, aslında binlerce yıllık bir matematik geleneğinin parçasını oynuyorsun.