Bulmacanın kombinatorik analizi ve imkansızlık ispatları
Yüz Yüze 10x10'luk basit bir grid üzerinde oynanır. Kurallar üç düz veya iki çapraz hareket. Görünüşte sadelik ama altında zengin bir kombinatorik yapı var. Bu sayfa o yapıyı inceler: kaç olası yol var, hangi başlangıç noktalarından 100'e ulaşılabilir, ve imkansızlığın matematiksel kanıtları.
Grid 10 satır × 10 sütun = 100 kare. Her kare 8 farklı yöne hamle yapabilir (eğer grid sınırına çarpmazsa):
Ama gerçekte her karenin geçerli hamle sayısı (out-degree) konumuna göre değişir.
Her karenin kaç çıkışı olduğunu sayarsak şu dağılımı buluruz:
| Konum | Out-degree | Kare sayısı |
|---|---|---|
| Köşeler (4 adet) | 2 | 4 |
| Köşeye 1 uzaklık | 3-4 | 8 |
| Kenar (köşelere uzak) | 4-5 | ~24 |
| Kenara 1 uzaklık | 5-7 | ~28 |
| Merkez bölge | 8 | 36 |
Toplam kenar (yön) sayısı yaklaşık 580'dir — çift sayılırsa, çünkü her hamle iki yönde işler. Bu, Yüz Yüze grafiğini orta yoğunlukta bir grafik yapar.
Düz hamle: 3 kare aynı satır veya sütunda. Bir kare (r, c) için:
Bu yapısal fark önemli sonuçlar doğurur. Eğer oyun süresince N tane düz hamle yapılırsa, başlangıç ve bitiş karelerinin r+c paritesi farkı N (mod 2) olur. Çapraz hamleler bu fark üzerinde etki etmez.
100 kareyi tamamen ziyaret etmek için 99 hamle yapılır. Bu 99 hamlenin kaçının düz, kaçının çapraz olacağı sabit değil — ama bazı düz/çapraz dağılımları matematiksel olarak imkansız olabilir.
Grid'i 4-renk şemasıyla boyayalım: (r mod 2, c mod 2) çiftine göre 4 renk. 100 kare 25'erden 4 sınıfa bölünür:
Hamleler bu sınıflar arasında nasıl hareket eder?
Yani çapraz hamleler renk değiştirmez, düz hamleler iki sınıf değiştirir. Bu, her oyun sonunda dört sınıfta da kaç kare ziyaret edildiği konusunda kısıtlama getirir.
İdeal bir tam tur (1-100) her sınıftan tam 25 kare ziyaret eder. Eğer ziyaretleriniz dengesizse — örneğin Sınıf A'dan 15, Sınıf D'den 30 ziyaret etmek istiyorsunuz — bu mümkün olmayabilir.
Yüz Yüze'nin tam tur problemi (1'den 100'e ulaşmak) bir Hamilton yolu arama problemidir. 100 köşeli grafikte, her köşeyi tam bir kez ziyaret eden yol bulmaya çalışıyorsunuz.
Hamilton yolu problemi NP-zor olarak bilinir — yani genel halinde hiçbir polinom-zaman algoritması bilinmemektedir. Ama Yüz Yüze'nin grid yapısı düzenli olduğu için pratikte çözülebilir. Modern bilgisayarlar tüm 100 başlangıç karesi için tam yolu saniyeler içinde bulabilir veya bulunamadığını ispatlayabilir.
Empirik olarak: 100 başlangıç karesinden bazıları matematiksel olarak 100'e ulaşamaz. Sebepleri çeşitli:
Köşelerden başlamak. Bir köşe karesi (örn. 0,0) sadece iki çıkışa sahiptir. Köşeye sonradan dönmek zorundaysanız, çıkış yollarınız çok kısıtlanır. Bazı köşe başlangıçları tam tur izin vermez.
Renk dengesizliği. Yukarıda gösterilen 4-renk şemasında, başlangıç ve bitiş karelerinin renkleri arasındaki ilişki düz/çapraz hamle sayısını kısıtlar. Bazı kombinasyonlar hiçbir 99-hamleli sıralamayla tutarlı değildir.
Yapısal izolasyon. Bazı kareler "çıkmaz" pozisyonda olabilir — sadece ziyaret etme zamanlamasıyla ulaşılabilir, yanlış sırada gelinirse kapana kısılır.
Yüz Yüze'de 100 her zaman ulaşılamaz. Peki iyi bir skor nedir?
Empirik olarak (ipucu motoru kullanılarak yapılan binlerce simülasyondan):
"Mükemmel oyun" tanımı bulmacaya bağlıdır. Bazı bulmacalarda 100 mümkündür, bazılarında matematiksel maksimum 80'ler civarındadır. Ekrandaki skorun, o günün matematiksel maksimumunun ne kadar altında olduğu tahmin sahibinin gerçek başarısını gösterir.
Yüz Yüze'nin matematiği üzerinde hâlâ çözülmemiş bazı sorular var:
10x10 grid, 8 hareket yönü ve basit bir hedef — yüzeyde sade görünen bu kurulumun altında 1200 yıllık matematik geleneği uzanır. Her oyun, özünde NP-zor bir problemin örnekleminin sezgisel olarak çözülmesine çalışır. Optimal oynamak demek, bilgisayarın ipucu motorunun saniyede yapamadığı şeyi insan beyninin sezgiyle bulması demektir.
Yüz Yüze sadece bir oyun değil — Hamilton yolu probleminin günlük bir örneği. Her bulmaca yeni bir matematiksel meydan okuma.