חידת מסע הפרש

חידת מסע הפרש היא חידת שחמט מפורסמת. בחידה על הפותר למצוא מסלול של הפרש על כל הלוח, כאשר בכל משבצת הוא עובר פעם אחת בלבד.
החידה נחקרה במשך השנים על ידי אנשים רבים. בנוסף למציאת פתרונות לחידה, נחקרו גם מספרם, אלגוריתמים למציאתם וכן הכללה ללוחות שונים.
החידה מהווה מקרה פרטי של בעיה חשובה בתורת הגרפים - מציאת מסלול המילטוני בגרף.

היסטוריה

המקור הידוע הראשון לחידה הוא ספר ערבי משנת 840, המזכיר את החידה ונותן לה שני פתרונות. בנוסף קיים ספר הודי משנת 900 המביא פתרון לחצי לוח שממנו ניתן לבנות פתרון ללוח שלם (בנוסף לפתרון של החידה גם עבור כלי אגדתי בשם "פיל"). ספר של אל-סולי משנת 940 מביא פתרון אשר חלק ממנו מקיים סימטריה מושלמת סביב הצירים. פתרונות רבים נוספים הובאו בספרים ערביים והודים בשנים שלאחר מכן. המקור האירופי הראשון הידוע הוא מהמאה ה-13.
המחקר המודרני יותר של החידה החל במאה ה-18. במסגרת מחקר זה התחילו לחפש אחרי שיטות כלליות לפתור את החידה. עם האנשים שחקרו את החידה נמנו לאונרד אוילר, אברהם דה מואבר וויליאם רואן המילטון, שמצא בעיה המכלילה את חידת מסע הפרש. האלגוריתם הראשון ניתן בשנת 1823 על ידי ורנסדורף (מתואר בפסקה "דרכים לפתרון" להלן). במאה העשרים התחילו להשתמש במחשבים לפתרון הבעיה, ובסוף המאה נמצא מספר הפתרונות ונמצאו כל המקרים בהם יש פתרון ללוח בגודל כלשהו.
"הטורקי", שהיה בובה מכנית שנטען שידעה לשחק שחמט אך למעשה הסתתר בתוכה מפעיל, "ידעה" גם איך לפתור את חידת מסע הפרש. למעשה, בידי המפעיל היה שרטוט של הפתרון.
במהלך המשחק השישי באליפות העולם בשחמט בשנת 2010, ביצע וישוואנתן אנאנד 13 מהלכים רצופים בפרשים. הפרשן התבדח ואמר ש"הוא מנסה לפתור את חידת מסע הפרש".

מספר הפתרונות

מספר המסלולים הסגורים הוא 26,534,728,821,064. אם סופרים פעם אחת שני מסלולים סגורים הנבדלים זה מזה רק בכיוונם, כלומר שביצוע אחד מהם בסדר מסעים הפוך נותן את השני, המספר מצטמצם בחצי. אם לא מחשיבים פתרונות המתקבלים זה מזה על ידי שיקוף הלוח וסיבובו מקבלים 1,658,420,855,433 פתרונות. תוצאות אלה הוכחו על ידי ברנדן מקיי (Brendan D. McKay) במאמר שפרסם בשנת 1997.
מספר המסלולים הפתוחים לא ידוע, אך עדיין מעניין למצוא לו חסם (כלומר מספר שבוודאות המספר שאנחנו מחפשים לא גבוה ממנו) נמוך ככל האפשר. בשנת 1862 מצא פון ג'ניש (C. F. von Jaenisch) חסם: ישנם סך הכול 168 זוגות של משבצות שאפשר להגיע מאחת לשנייה, ויש לבחור 63 מתוכן (כי במהלך הפתרון הפרש מבצע 63 קפיצות, וכל קפיצה היא למעשה זוג משבצות כזה), לפיכך מספר הפתרונות אינו עולה על , שהוא מספר הדרכים לבחור 63 עצמים מתוך 168 (ראו מקדם בינומי). סדר הגודל של מספר זה הוא 47 ספרות. חסם זה הוא גרוע, כי למעשה רק חלק קטן מקבוצות הזוגות אכן מתחברים לכדי מסלול רציף. במשך השנים סופקו חסמים טובים יותר על ידי מתמטיקאים שונים, אך עד היום לא נמצא פתרון מדויק. החסם הטוב ביותר הידוע הוא מסדר גודל של 22 ספרות.
נחקרים גם מספרי הפתרונות שמקיימים תכונות מסוימות, למשל, שתחילה הפרש עובר בכל מחצית הלוח העליונה, ולאחר מכן בכל המחצית התחתונה.

החידה כבעיה בתורת הגרפים

החידה היא מקרה פרטי של בעיה חשובה בתורת הגרפים.
גרף הוא אוסף נקודות הקרויות צמתים, עם קווים המחברים ביניהן הנקראים קשתות. מסלול הוא סדרה של קשתות כך שכל שתיים רצופות מחוברות בצומת. מסלול המילטוני הוא מסלול העובר בכל הצמתים פעם אחת. מעגל המילטוני הוא מסלול העובר בכל הצמתים פעם אחת, למעט הצומת הראשון בו הוא עובר גם בסוף המסלול.
בשביל לתאר את חידת מסע הפרש כבעיה מתורת הגרפים, נבנה גרף הנקרא "גרף פרש" שכל צומת בו מייצג משבצת בלוח השחמט, ושני צמתים יהיו מחוברים בקשת אם המשבצות שהם מייצגים הן כאלו שניתן לעבור ביניהן על ידי צעד פרש (גרף כזה מתואר בתמונה משמאל). בגרף זה החידה הופכת להיות: "מצא מסלול המילטוני (או מעגל המילטוני בגרסה השנייה) בגרף זה".
הבעיה הכללית היא מציאת מסלול המילטוני בגרף כלשהו (או לפחות קביעה האם קיים מסלול כזה). לא ידוע היום על דרך יעילה לפתור אותה. מצד שני, בהינתן פתרון לכאורה, ניתן לבדוק ביעילות אם הוא נכון. למעשה, הוכח שפתרון בעיה זאת יפתור כל בעיה אחרת הניתנת לבדיקה בזמן יעיל (בעיה כזאת נקראת NP-שלמה) ועל כן משערים שלא ניתן לפתור אותה בזמן יעיל. אך בניגוד למקרה הכללי, את חידת מסע הפרש ניתן לפתור עבור לוח בגודל כלשהו בזמן ליניארי.

חלוקה לחלקים

דרך פשוטה לפתור את הבעיה היא לחלק את הלוח לחלקים קטנים יותר, ולמצוא בכל אחד מהם מסלול פתוח, שבנוסף מאפשר לעבור בין המסלולים. שיטה זאת מאפשרת להוכיח קיום מסלול לכל לוח (למעט גדלים מסוימים), וכן למצוא אותו ביעילות.

רשת עצבית מלאכותית

אפשר לפתור את הבעיה באמצעות רשת עצבית מלאכותית. בפתרון זה נותנים לכל "נוירון" המייצג קשת בגרף פרש (כלומר מסע חוקי כלשהו) את הערך 1 או 0. במצב הסופי 1 יציין מסע הנכלל בפתרון, ו-0 יציין מסע שאיננו נכלל. מתחילים בהשמה אקראית, ומפעילים על הנוירונים פונקציה שמשנה את ערכם, שמגיעה למצב סטטי רק כאשר התקבל פתרון חוקי.

שינוי גודל הלוח

את החידה ניתן לשאול לא רק על הלוח הסטנדרטי בגודל 8x8, אלא על כל לוח מלבני מגודל mxn.

גרסאות אחרות

קיימות גרסאות נוספות לכל אלה שהוזכרו לעיל. וריאציה לדוגמה היא הגרסה הבאה:
מה האורך הארוך ביותר של מסלול שפרש יכול לעשות אשר לא "חותך" את עצמו? (כלומר, אם נצייר קווים לאורך המסלול שום קו לא יגע בקו אחר)
פתרון חידה זאת מוצג משמאל.

ריבוע קסם למחצה כפתרון לבעיה

אחד מהפתרונות של הבעיה הוא הפתרון הבא: (הפרש מתחיל במספר 1, מדלג בכל צעד למספר העוקב)
פתרון זה, שהוצג על ידי ויליאם בוורלי, מיוחד בכך שהוא מהווה ריבוע קסם למחצה, כלומר סכום המספרים בכל שורה ועמודה שווה. הרעיון שמאחוריו הוא שכל פעם הפרש מבצע ארבע מהלכים באותו רבע-לוח (כלומר אחד מהריבועים 4x4 המתקבלים אם מחלקים את הלוח לאורך ולרוחב). את ארבעת המהלכים האלה הוא מבצע כך שכל אחד מהם בשורה אחרת ובטור אחר. נציג כל מספר כסכום של שני מספרים: אחד מתחלק ב-4 והשני בין 1 ל-4, ואז לכל ארבעה מהלכים רצופים, הרכיב המתחלק ב-4 שלהם יהיה זהה, והמרכיבים בין 1 ל-4 יהיו שונים. חלוקה כזאת מודגמת בתמונה הבאה: (המציגה את הרבע השמאלי-עליון)
המסלול המתואר גרם לכך שהריבוע של המספרים המתחלקים ב-4 יוצר ריבוע לטיני, כלומר כזה שכל מספר מופיע פעם אחת בכל שורה ועמודה (כי את ארבעת המהלכים עשינו כך שכל אחד בטור אחר ובשורה אחרת). הריבוע של המספרים מ-1–4 בנוי תמיד כך שסכום השורות והעמודות הוא 10. בצורה כזאת אם נחבר את שני החלקים נקבל ריבוע קסם למחצה (כי בכל אחד מהם סכום העמודות שווה לשורות). לפיכך הריבוע מורכב מ-4 ריבועי קסם קטנים. בנוסף המסלול מתוכנן כך שלכל ריבועי הקסם יהיה את אותו סכום של שורות (130), וכך ארבעתם יוצרים ביחד ריבוע קסם למחצה גדול.
קיימים עוד ריבועי קסם למחצה המקיימים תכונות שונות, אך לא קיים ריבוע קסם מלא, כלומר כזה שבו גם סכום האלכסונים שווה לסכום השורות. דבר זה הוכח בשנת 2003.

בתרבות

ספר הודי עתיק מביא שיר שההברות שלו מסודרות במלבן 4x8 כך שכדי לקרוא אותן לפי הסדר יש ללכת בצעדי פרש על פני ההברות.
קבוצת אוליפו עשתה ברעיון זה שימוש נרחב. המפורסם ביותר הוא ספרו של ז'ורז' פרק, "החיים: הוראות שימוש", שמתאר בית שבו 10 קומות שבכל אחת מהן 10 חדרים, היוצרים לוח שחמט 10x10.‏ 99 הפרקים מתרחשים בחדרי הבית, כאשר סדר הפרקים נקבע לפי מסעי הפרש.