חידת מסע הפרש

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

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

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

## החידה

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

ה**[[פרש (שחמט)|פרש]]** הוא כלי שחמט המסוגל לנוע בתורו שתי משבצות בכיוון ישר (למעלה, למטה, שמאלה או ימינה) ועוד צעד אחד בכיוון ניצב. בדיאגרמה משמאל ניתן לראות הדגמה של המשבצות אליהן הוא יכול להגיע בצעד אחד ממשבצת נתונה.

המטרה בחידה היא למצוא מסלול של פרש שעובר בכל משבצות הלוח, כאשר בכל משבצת הוא מבקר בדיוק פעם אחת.

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

באופן כללי יותר, החידה שואלת כמה פתרונות שונים יש לחידה.


קובץ:Turk-knights-tour.svg|פתרון במסלול סגור
קובץ:Knights tour.png|פתרון במסלול פתוח


## היסטוריה
המקור הידוע הראשון לחידה הוא ספר ערבי משנת 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 קפיצות, וכל קפיצה היא למעשה זוג משבצות כזה), לפיכך מספר הפתרונות אינו עולה על  \tbinom {168}{63}, שהוא מספר הדרכים לבחור 63 עצמים מתוך 168 (ראו מקדם בינומי). סדר הגודל של מספר זה הוא 47 ספרות. חסם זה הוא גרוע, כי למעשה רק חלק קטן מקבוצות הזוגות אכן מתחברים לכדי מסלול רציף. במשך השנים סופקו חסמים טובים יותר על ידי מתמטיקאים שונים, אך עד היום לא נמצא פתרון מדויק. החסם הטוב ביותר הידוע הוא מסדר גודל של 22 ספרות.

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

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

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

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

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

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

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

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

בפסאודו קוד ניתן לתאר את השיטה בעזרת האלגוריתם הרקורסיבי הבא:

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

### אלגוריתם חמדן

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

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

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

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

#### קיום פתרון

הוכח, שיש מסלול סגור אם מתקיימים התנאים הבאים:
# mn הוא זוגי (אחרת לא ניתן למצוא מסלול סגור, מאחר שבכל מהלך הפרש משנה את צבע המשבצת עליה הוא נמצא, ומכאן שהוא חייב להתחיל ולסיים במשבצות באותו צבע, ולכן אינו יכול לדלג ביניהן)
# גם m וגם n הם לפחות 5, או אחד מהם 3 והשני 10 ומעלה

ההוכחה למשפטים אלה מתבססת על חלוקה ללוחות קטנים יותר.

שמאל|ממוזער|שתי דרכים לצבוע לוח 4xn
נראה אי קיום של מסלול סגור בשאר הלוחות:
* עבור 1xn או 2xn אי אפשר אפילו להגיע מכל משבצת לכל משבצת, ובוודאי שלא לעבור על כל המשבצות.
* עבור 4xn נצבע את הלוח בצורה המתוארת משמאל: שורות עליונה ותחתונה בירוק, אמצעית באדום.
:ניתן לראות שממשבצת ירוקה אפשר לקפוץ רק למשבצת אדומה. כיוון שמספר המשבצות האדומות והירוקות שווה, המסלול מוכרח להיות פעם משבצת ירוקה ופעם אדומה לסירוגין. אך אם נצבע אותו בצביעה רגילה נראה שהמסלול חייב להיות לבן ושחור לסירוגין. כיוון שאין התאמה בין הצביעות, המסלול בלתי אפשרי.
* עבור 3x6 או 3x8 נסתכל על גרף של הלוח. נשים לב שניתן לקבל מסלול המילטוני על ידי הסרת קשתות עד שנקבל רק את הקשתות שמרכיבות את המסלול הרצוי. אולם, ניתן להוכיח שהסרה כזאת בהכרח תהפוך את הגרף ללא קשיר (כלומר גרף שיש בו נקודות שאינן מחוברות זו לזו כלל, אפילו על ידי מסלול) ולכן לא יכול להיות בו מסלול כמבוקש.

מסלול פתוח קיים לכל לוח mxn, למעט 1xn, 2xn, 3x3, 3x5, 3x6 ו-4x4.

#### מספר הפתרונות
גם עבור גדלים שונים מעניין לבדוק את מספר הפתרונות ולחפש קשר בין גודל הלוח למספר הפתרונות. להבדיל ממציאת פתרון אחד, חישוב מספר הפתרונות הוא בעיה קשה, ולכן הצליחו לחשב אותו רק עבור גדלים קטנים. חסם שהושג עבור לוח nxn הוא \Omega (1.3535^{n^2}) (ראו סימון אסימפטוטי). להלן טבלה ובה מוצגות תוצאות עבור לוחות ריבועיים ולוחות בעלי שלוש וארבע שורות:

### שינוי צורת הלוח
ממוזער|שמאל|חידה עבור לוח קטן ולא מלבני.

אפשר לשאול את החידה גם ללוחות אחרים, לדוגמה:
*לוח בצורה שאיננה מלבן. למשל, החידה משמאל.
*לוח עם חוקי מעבר מיוחדים בין המשבצות. לעיתים ניתן להציג לוח כזה כלוח רגיל אך כזה שאיננו ניתן לפריסה מישורית. למשל, אם מתירים לפרש לקפוץ מקצה השורה לקצה השורה השנייה, מתקבל לוח גלילי (כי את תוצאה זאת היינו מקבלים מהדבקת העמודות הקיצוניות). אם מוסיפים גם מעבר בין קצות העמודות, מתקבל לוח טבעתי (כי את תוצאה זאת היינו מקבלים מהדבקת השורות הקיצוניות של לוח גלילי. לוח כזה הוא טורוס). עבור לוח טבעתי הוכח שתמיד קיים מסלול סגור, ואילו ללוח גליל קיים מסלול סגור מלבד המקרים 1xn, 2xn, 4xn.
*לוח תלת-ממדי: לוח שהמשבצות בו הן קוביות. מציגים לוח כזה בדרך כלל על ידי מערכת של שלוש קואורדינטות, כאשר מהקואורדינטה ה-(x,y,z) ניתן לנוע למשל ל-(x+2,y+1,z) (כל עוד לא חורגים מגבולות הלוח). הוכח שתמיד קיים מסלול עבור לוח בגודל mxnxp אם המכפלה זוגית וכל המספרים לפחות 2, אלא במקרים 2x2xn או 2x3x3.

### כלים אחרים
ממוזער|250px|שמאל|פתרון חידת מסע עבור צריח.
ניתן לשאול את החידה גם על שאר כלי השחמט. עבור הכלים הרגילים, התשובה פשוטה: רץ בוודאי לא ניתן, כי הוא נשאר כל הזמן על אותו צבע ולמחצית משבצות הלוח הוא לא יכול להגיע כלל. גם רגלי אי אפשר כי הוא נשאר כל הזמן על אותו טור. למלכה, צריח ומלך הדבר אפשרי: די בכך שהם יכולים ללכת משבצת אחת בכיוון מאוזן או מאונך, כדי לפתור באופן הבא:
# התחל בפינה השמאלית התחתונה, ולך ימינה לאורך השורה.
# עלה את העמודה הימנית, זוז משבצת אחת שמאלה, ורד את העמודה שמשמאלה עד לשורה השביעית מלמעלה.
# כעת זוז משבצת אחת שמאלה וחזור על שלב 2 עוד שלוש פעמים.
# רד משבצת אחת.
הפתרון מתואר בדיאגרמה משמאל.

אלה הפתרונות לכל כלי השחמט הרגילים. אולם, אם מדברים על כלי שחמט אגדתיים, אפשר למצוא כלים רבים שעבורם החידה מעניינת. לדוגמה, עבור leaper-5, שהוא כלי שמסוגל לקפוץ שלוש משבצות ואז ארבע בכיוון ניצב או חמש משבצות, מצא מוריס קרייטצ'יק (Maurice Kraitchik) בשנת 1927 את הפתרון הבא:
ממוזער|מרכז|פתרון עבור leaper-5

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

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

פתרון חידה זאת מוצג משמאל.

## ריבוע קסם למחצה כפתרון לבעיה
אחד מהפתרונות של הבעיה הוא הפתרון הבא: (הפרש מתחיל במספר 1, מדלג בכל צעד למספר העוקב)
לא ממוסגר|מרכז|250px
פתרון זה, שהוצג על ידי ויליאם בוורלי, מיוחד בכך שהוא מהווה ריבוע קסם למחצה, כלומר סכום המספרים בכל שורה ועמודה שווה. הרעיון שמאחוריו הוא שכל פעם הפרש מבצע ארבעה מהלכים באותו רבע-לוח (כלומר אחד מהריבועים 4x4 המתקבלים אם מחלקים את הלוח לאורך ולרוחב). את ארבעת המהלכים האלה הוא מבצע כך שכל אחד מהם בשורה אחרת ובטור אחר. נציג כל מספר כסכום של שני מספרים: אחד מתחלק ב-4 והשני בין 1 ל-4, ואז לכל ארבעה מהלכים רצופים, הרכיב המתחלק ב-4 שלהם יהיה זהה, והמרכיבים בין 1 ל-4 יהיו שונים. חלוקה כזאת מודגמת בתמונה הבאה: (המציגה את הרבע השמאלי-עליון)
מרכז

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

קיימים עוד ריבועי קסם למחצה המקיימים תכונות שונות, אך לא קיים ריבוע קסם מלא, כלומר כזה שבו גם סכום האלכסונים שווה לסכום השורות. דבר זה הוכח בשנת 2003.

## בתרבות
ספר הודי עתיק מביא שיר שההברות שלו מסודרות במלבן 4x8 כך שכדי לקרוא אותן לפי הסדר יש ללכת בצעדי פרש על פני ההברות.

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

## קישורים חיצוניים

* 
* מאמרים על חידת מסע הפרש 
* קישורים על החידה 

## הערות שוליים

מסע הפרש
קטגוריה:תורת הגרפים
קטגוריה:לאונרד אוילר