חידת מסע הפרש

חידת שחמט הידועה בכינויה "חידת מסע הפרש" מעסיקה מתמטיקאים כבר 1,200 שנה. מטרת החידה היא למצוא את כל המסלולים האפשריים שבהם הפרש נוחת על כל אחת ממשבצות לוח השחמט - פעם אחת בלבד. לשם כך נדרשים 63 מהלכים שבהם נע הפרש בהתאם לחוקי המשחק - שתי משבצות בכיוון אחד ועוד משבצת אחת בכיוון ניצב. במשך מאות שנים חישבו מתמטיקאים את המסלולים האפשריים של הפרש על הלוח וככל שהם חקרו את הסוגייה הם גילו יותר תצורות. קודם כל, הם הבחינו בין שני סוגי מסלולים אפשריים: מסלול סגור ומסלול פתוח. במסלול סגור מהלך אחד בלבד של הפרש מפריד בין נקודת ההתחלה לבין הנקודה האחרונה במסלול. ב-1997 פרסם המתמטיקאי ברנדן מקיי מאמר שבו הוא הוכיח כי קיימים 26,534,728,821,064 מסלולים סגורים אפשריים. הוא גם הראה כיצד ניתן להפוך כל מסלול סגור ל-64 מסלולים פתוחים אחרים - כלומר מסלולים שבהם הצעד האחרון אינו צעד סוגר. החידה עדיין לא נפטרה משום שטרם חושבו מספר המסלולים הפתוחים האפשריים - מספר שעולה, באופן בלתי יאמן, על כמות המסלולים הסגורים. לאחרונה, בניסיון למצוא מסלולים אפשריים נוספים, השתמש המתמטיקאי גרהם קנדל באלגוריתם שפותח בעקבות מעקב אחר מסלולי הנדידה של נמלים בין מאגר מזון לקולוניה שלהן. קנדל, יחד עם קולגה מאוניברסיטת נוטינגהם שבאנגליה, חישב כך עוד 500 אלף מסלולים אפשריים. נסו כאן למצוא פתרון לחידת מסע הפרש.

פרט מעניין זה התפרסם באלכסון ב