En uzun aşılmamış şövalye yolu - Longest uncrossed knights path

en uzun çaprazlanmamış (veya kesişmeyen) şövalye yolu içeren matematiksel bir problemdir şövalye standart 8 × 8'de satranç tahtası veya daha genel olarak bir karede n×n yazı tahtası. Sorun en uzun olanı bulmak yol Şövalye verilen tahtayı alabilir, böylece yol kendisiyle kesişmez. Aşağıdakiler arasında başka bir ayrım yapılabilir: kapalı başladığı yer ile aynı alanda biten yol ve açık başladığı yerden farklı bir alanda biten yol.

Bilinen çözümler

Bir üzerindeki en uzun açık yollar nxn yönetim kurulu sadece n ≤ 9. Uzunlukları n = 1, 2, ..., 9:

0, 0, 2, 5, 10, 17, 24, 35, 47 (sıra A003192 içinde OEIS )

En uzun kapalı yollar yalnızca n ≤ 10. Uzunlukları n = 1, 2, ..., 10:

0, 0, 0, 4, 8, 12, 24, 32, 42, 54 (sıra A157416 içinde OEIS )
UncrossedKnightsPath7x7.svgUncrossedKnightsPath8x8.svg
İçin en uzun kapalı yol n = 7
uzunluk 24.
İçin en uzun açık yol n = 8
uzunluk 35.

Genellemeler

Sorun dikdörtgen şeklinde daha da genelleştirilebilir n×m panolar, hatta herhangi bir şeklindeki panolara poliomino. Diğer standart satranç taşları şövalyeden daha az ilginç, ama peri satranç taşları gibi deve ((3,1) - daha az), zürafa ((4,1) - daha az) ve zebra ((3,2) -leaper) karşılaştırılabilir karmaşıklıkta sorunlara yol açar.

Ayrıca bakınız

  • Bir şövalye turu kendisiyle kesişen bir şövalyenin tahtanın tüm alanlarını ziyaret eden yoludur.
  • TwixT, aşılmamış şövalye yollarına dayanan bir tahta oyunu.

Referanslar

  • L.D. Yarbrough (1969). "Sınırsız şövalye turları". Rekreasyonel Matematik Dergisi. 1 (3): 140–142.
  • George Jelliss, Kesişmeyen Yollar
  • Geçişsiz şövalye turları

Dış bağlantılar