Bu videoda, ayrık matematik ve algoritmalar alanında önemli bir yer tutan Şövalye Turu (Knight’s Tour) problemi ele alınmaktadır. Problem, satranç tahtasında bulunan bir şövalyenin, her kareye tam olarak bir kez uğrayacak şekilde hareket edip edemeyeceğini araştırır.
Şövalye, satrançta “L” şeklinde hareket eder: iki kare bir yönde ve bir kare buna dik yönde ilerler. Bu özel hareket kuralı, problemi sıradan bir yol bulma probleminden ayırır ve ciddi bir kombinatorik yapı oluşturur.
Şövalye turu problemi genellikle 8×8’lik klasik satranç tahtası üzerinde incelenir; ancak problem, genel olarak n×n boyutlu tahtalar için de ele alınabilir. İki temel türü vardır: Açık şövalye turu: Şövalye tüm kareleri birer kez ziyaret eder, ancak başladığı kareye geri dönmez. Kapalı şövalye turu: Şövalye tüm kareleri birer kez ziyaret ettikten sonra, son hamlede başlangıç karesine dönebilir. Bu durumda tur bir çevrim oluşturur.
Problem grafik teorisi açısından incelendiğinde, her kare bir düğüm, şövalyenin geçerli hamleleri ise kenar olarak modellenir. Böylece şövalye turu, bu grafikte Hamilton yolu (açık tur) veya Hamilton çevrimi (kapalı tur) arama problemine dönüşür.
Bu problem tarihsel olarak Orta Çağ’dan beri bilinmekte olup, günümüzde: algoritma tasarımı, geri izleme (backtracking), sezgisel yöntemler (örneğin Warnsdorff kuralı), yapay zekâ ve optimizasyon konularında sıkça örnek olarak kullanılmaktadır.
Kaynaklar
- https://www.instagram.com/reels/DSbtqNFDHvg/
