At Turu hakkında | Warnsdorff kuralı, açık ve kapalı turlar

Eski bir bulmaca

Hintli şair Rudrata’nın 9. yüzyılda yazdığı Kavyalankara’da bir dize, yarım satranç tahtasına bir atın yolu boyunca okunabilecek şekilde yerleştirilmiştir. Leonhard Euler, at turu üzerine ilk matematiksel çalışmayı 1759’da yazdı; bu çalışmada tur kurmanın ve turları kapalı turlara dönüştürmenin yollarını gösterdi.

Graf içinde bir yol

Her kareyi bir nokta, her at hamlesini de iki nokta arasındaki bir çizgi olarak düşünün. O zaman at turu, her noktaya tam bir kez uğrayan bir yoldur; matematikçiler buna Hamilton yolu der. Kapalı tur ise bir Hamilton döngüsüdür. Çoğu ağda böyle bir yolu bulmak çok zordur. Atın ağı ise cömerttir: o kadar çok turu vardır ki iyi bir kural hızla bir tane bulur.

Warnsdorff kuralı

H. C. von Warnsdorff kuralını 1823’te tanımladı: her zaman, sonrasında en az hamle seçeneği bırakan kareye sıçra. Kenar boyunca uzanan karelerin komşusu azdır, bu yüzden kural onları ulaşılamaz hâlde bırakmak yerine erkenden onlara uğrar. İki kare berabere kaldığında bir seçim yapmak gerekir ve şanssız bir seçim atı yine de çıkmaza sokabilir. Uygulamada altın rengi sayılar, kuralın seçeceği kareleri gösterir.

Geri izlemeyle arama

Çöz, Warnsdorff’un sırasını izler ama ona körü körüne güvenmez. Derinlik öncelikli arama yapar ve uğranmamış bir kareye artık ulaşılamadığı anda o dalı bırakıp sonraki hamleyi dener. 10×10’a kadar tahtalarda genellikle hemen bir tur bulur. Kendi yolunuz atı kapana kıstırdıysa, önce birkaç hamle geri gider.

Renkler ve kapalı turlar

Her at hamlesi karenin rengini değiştirir. 5×5 gibi kenarı tek olan bir tahtada köşe renginde, diğer renge göre bir kare fazla vardır; bu yüzden tur köşe renginde başlayıp köşe renginde bitmelidir. Orada kapalı tur imkânsızdır, çünkü renkleri sırayla değiştiren bir döngüde her renkten eşit sayıda kare bulunur. Kenarı çift olan tahtalarda kapalı turlar 6×6’dan itibaren vardır.

PictorX’te deneyin

At Turu’nu açın ve başlamak için bir kareye tıklayın. Vurgulanan kareler geçerli sıçrayışlardır, altın rengi sayı Warnsdorff’un seçimidir ve tahta hamlelerinizin sırasını saklar. Boyut tahtayı 5×5’ten 10×10’a kadar ayarlar, “Kapalı tur” Çöz’den bir döngü ister, Geri al da herhangi bir hamleyi geri alır. Bitmiş yolu PNG olarak kaydedin.

Sık sorulan sorular

At turunu ilk kim inceledi?

Turlar, matematiksel olarak incelenmelerinden çok önce biliniyordu. Leonhard Euler ilk matematiksel incelemeyi 1759’da yazdı, Warnsdorff da kuralını 1823’te ortaya koydu.

Her tahtada bir tur var mı?

5×5’ten itibaren kare tahtalarda açık turlar vardır; bunlardan 6×6’dan itibaren kenarı çift olanlarda kapalı turlar da vardır. 2×2, 3×3 ve 4×4 tahtalarda hiç tur yoktur.

Bir satranç tahtasında kaç tur vardır?

Bir tur ile aynı turun tersten gidilişi ayrı sayılırsa 26.534.728.821.064 kapalı tur vardır. Açık turların sayısı yaklaşık 19,6 katrilyondur.

PictorX bir şey yükler mi?

Hayır. Tahta, tarayıcınızdaki bir tuvalde çizilir. Kaydet bir PNG indirir, Düzenle de o görüntüyü PictorX düzenleyicisinde açar.