Oyunun arkasındaki matematik: Hamilton yolu
Görevimiz Kelime’de çizdiğin yol, matematikte “Hamilton yolu” denen yapının bir örneğidir. Bu kavram, oyunun neden bu kadar düşündürücü olduğunu ve neden kısa yolun hemen hemen hiç işe yaramadığını açıklar.
Hamilton yolu nedir?
Matematikte bir graf, noktalardan ve bu noktaları birleştiren çizgilerden oluşur. Görevimiz Kelime tahtasını böyle düşünebilirsin: her kare bir nokta, yan yana duran ve aralarında taş çit olmayan iki kare ise bir çizgiyle bağlı. Bir grafın her noktasından tam bir kez geçen yola Hamilton yolu denir. Adını, 19. yüzyılda bu tür yollarla ilgili bir bulmaca tasarlayan İrlandalı matematikçi William Rowan Hamilton’dan alır.
Oyunun kuralı tam olarak budur: her kareden bir kez geç. Harfler ise bu yola ek bir koşul koyar: belirli noktalardan belirli bir sırayla geçmen gerekir.
Neden zordur?
Bir grafta Hamilton yolu olup olmadığını bulmak, bilgisayar biliminin ünlü zor problemlerinden biridir. Kare sayısı arttıkça olası yolların sayısı patlarcasına büyür. 8×8 bir tahtada bile her kareden bir kez geçen yolların sayısı astronomik düzeydedir; hepsini tek tek denemek bir insan için imkânsızdır.
Bu yüzden oyunda deneme yanılma yerine mantık kullanırsın. Strateji rehberindeki kuralların her biri, olası yolların büyük bir kısmını tek bir gözlemle eler:
- Tek çıkış ve iki kapılı kareler: Hamilton yolunda iç noktaların iki, uç noktaların bir bağlantısı vardır. Bağlantı sayısı azalan bir nokta yolu zorlar.
- Tahtayı bölme: Hamilton yolu bağlı bir yapıdır; boş kareler iki parçaya ayrılırsa yol tamamlanamaz.
- Satranç tahtası sayımı: Kare ızgara “iki parçalı” bir graftır; her adım bir renkten öbürüne geçer. Bu, renk sayılarıyla ilgili kesin bir koşul verir.
Harfler zorluğu nasıl değiştirir?
Harfsiz bir tahtada çoğu zaman birden fazla Hamilton yolu vardır. Harfler ve taş çitler, bu yolları tek bir yola indirgemek için kullanılır. Görevimiz Kelime’nin tahtaları üretilirken, her tahtanın kurallara uyan tek bir yolu olup olmadığı bilgisayarla kontrol edilir; birden fazla yol varsa, alternatif yolları kesen taş çitler eklenir. Bu sürecin ayrıntılarını tahtalar nasıl üretiliyor yazısında anlattık.
Gündelik hayatta Hamilton yolları
Bu problem yalnızca bulmacalarda karşımıza çıkmaz. Bir kuryenin her adrese bir kez uğrayan rotası, bir robot kolunun bir devre kartındaki her noktayı bir kez ziyaret etmesi ya da bir turistin her müzeyi bir kez gezmesi aynı yapının farklı biçimleridir. Görevimiz Kelime’de çözdüğün her tahta, bu klasik problemin küçük ve eğlenceli bir örneğidir.
Sık sorulanlar
Hamilton yolu ile Euler yolu farklı mı?
Evet. Euler yolu her çizgiden (kenardan) bir kez geçer; Hamilton yolu ise her noktadan bir kez geçer. Görevimiz Kelime’de kareleri dolaştığın için Hamilton yolu söz konusudur.
Bilgisayar bu tahtaları nasıl çözüyor?
Olası yolları sistemli biçimde dener, ama boş karelerin tek parça kalması ve tek girişli kare oluşmaması gibi kurallarla çoğu yolu erkenden eler. Bu, oyuncuların kullandığı kuralların aynısıdır.
Daha büyük tahtalar gelecek mi?
Tahtalar şu anda en fazla 8×8’dir. Telefon ekranında rahat oynanabilirlik için bu sınır bilinçli olarak seçildi.