Closed Knight’s Tour
กระดานขนาดใหญ่

จากกระดานย่อยที่เรียนรู้ สู่หนึ่งวงจรใหญ่ที่ตรวจสอบได้

ห้องทดลองนี้แบ่งกระดาน N×N เป็นกระดานย่อย 8×8 แก้ constrained Hamiltonian path ทีละก้อน ล็อกคำตอบ แล้วส่งต่อเฉพาะคู่ exit–entry ที่เป็น knight move ถูกต้องไปยังก้อนถัดไป ก้อนสุดท้ายถูกบังคับให้เชื่อมกลับจุดเริ่มที่ตรึงไว้

P(next=j | current=i) ∝ W[i,j] / (1 + OnwardDegree(j))⁴

ชื่อให้ตรงกับ implementation: ตัวเลือกแบบเรียนรู้คือ COIN–Warnsdorff Hybrid ส่วน Warnsdorff baseline ใช้ randomized minimum-onward-degree โดยไม่เรียนเมทริกซ์ edge

วิธีพับกริดย่อยทั้งจำนวนคู่และจำนวนคี่

ให้ q=N/8 เป็นจำนวนก้อนต่อด้าน การพับแบบงูทีละแถวเข้าใจง่ายแต่เป็นเพียง open macro path เพราะก้อนสุดท้ายอาจไม่ติดก้อนแรก การสร้างวงปิดจึงต้องสงวนทางกลับหรือค้นหา macro Hamiltonian cycle โดยตรง

q เป็นเลขคี่ไม่ได้แปลว่ากระดานใหญ่ไม่มี closed tour เพราะ N=8q ยังเป็นเลขคู่ สิ่งที่ล้มเหลวคือ serpentine fold แบบง่ายเท่านั้น และแค่ก้อนติดกันยังไม่พอ ต้องตรวจ connector ระหว่างช่องจริง

กระดานใหญ่ใช้การประกอบ ไม่ใช่สุ่มค้นยักษ์ครั้งเดียว

อัลกอริทึม divide-and-conquer ของ Parberry สร้าง closed tour ใน quadrant แบบ recursive แล้วสลับ edge เพื่อเชื่อมวงจร ใช้งาน O(n²) บนกระดาน n×n หรือเชิงเส้นตามจำนวนช่อง งานต่อมายังแสดง structured และ obfuscated tour ถึง 2,000×2,000 ส่วนห้องทดลองนี้เปิดให้เห็น constrained solve ของแต่ละ 8×8 และให้ COIN เรียนรู้ระดับ local เพื่อให้นักศึกษาตรวจ boundary contract ได้

1. Parberry, I. (1997). An efficient algorithm for the Knight’s Tour Problem. Discrete Applied Mathematics, 73, 251–260.
2. Schwenk, A. J. (1991). Which Rectangular Chessboards Have a Knight’s Tour? Mathematics Magazine, 64(5), 325–332.
3. Parberry, I. (2020). Tourneys and the Fast Generation and Obfuscation of Closed Knight’s Tours.
4. Warnsdorff heuristic analysis: How good is Warnsdorff’s knight’s tour heuristic?
5. Gilith 64×64 Knight’s Tour — ตัวอย่างการนำเสนอทัวร์กระดานใหญ่