חידת מסע הפרש

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

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

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

החידה

8
7
6
5
4
3
2
1
	א	ב	ג	ד	ה	ו	ז	ח

המשבצות אליהן הפרש יכול להגיע
מסומנות ב-X.

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

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

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

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

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

פתרון במסלול סגור
פתרון במסלול פתוח

היסטוריה

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

המחקר המודרני יותר של החידה החל במאה ה-18^[2]. במסגרת מחקר זה התחילו לחפש אחרי שיטות כלליות לפתור את החידה. עם האנשים שחקרו את החידה נמנו לאונרד אוילר, אברהם דה מואבר וויליאם רואן המילטון^[3], שמצא בעיה המכלילה את חידת מסע הפרש. האלגוריתם הראשון ניתן בשנת 1823 על ידי ורנסדורף (מתואר בפסקה "דרכים לפתרון" להלן). במאה העשרים התחילו להשתמש במחשבים לפתרון הבעיה, ובסוף המאה נמצא מספר הפתרונות ונמצאו כל המקרים בהם יש פתרון ללוח בגודל כלשהו.

"הטורקי", שהיה בובה מכנית שנטען שידעה לשחק שחמט אך למעשה הסתתר בתוכה מפעיל, "ידעה" גם איך לפתור את חידת מסע הפרש. למעשה, בידי המפעיל היה שרטוט של הפתרון^[4].

במהלך המשחק השישי באליפות העולם בשחמט בשנת 2010, ביצע וישוואנתן אנאנד 13 מהלכים רצופים בפרשים. הפרשן התבדח ואמר ש"הוא מנסה לפתור את חידת מסע הפרש"^[5].

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

מספר המסלולים הסגורים הוא 26,534,728,821,064. אם סופרים פעם אחת שני מסלולים סגורים הנבדלים זה מזה רק בכיוונם, כלומר שביצוע אחד מהם בסדר מסעים הפוך נותן את השני, המספר מצטמצם בחצי. אם לא מחשיבים פתרונות המתקבלים זה מזה על ידי שיקוף הלוח וסיבובו מקבלים 1,658,420,855,433 פתרונות. תוצאות אלה הוכחו על ידי ברנדן מקיי (Brendan D. McKay) במאמר שפרסם בשנת 1997^[6].

מספר המסלולים הפתוחים לא ידוע, אך עדיין מעניין למצוא לו חסם (כלומר מספר שבוודאות המספר שאנחנו מחפשים לא גבוה ממנו) נמוך ככל האפשר. בשנת 1862 מצא פון ג'ניש (C. F. von Jaenisch) חסם: ישנם סך הכול 168 זוגות של משבצות שאפשר להגיע מאחת לשנייה, ויש לבחור 63 מתוכן (כי במהלך הפתרון הפרש מבצע 63 קפיצות, וכל קפיצה היא למעשה זוג משבצות כזה), לפיכך מספר הפתרונות אינו עולה על ${\tbinom {168}{63}}$ , שהוא מספר הדרכים לבחור 63 עצמים מתוך 168 (ראו מקדם בינומי). סדר הגודל של מספר זה הוא 47 ספרות. חסם זה הוא גרוע, כי למעשה רק חלק קטן מקבוצות הזוגות אכן מתחברים לכדי מסלול רציף. במשך השנים סופקו חסמים טובים יותר על ידי מתמטיקאים שונים, אך עד היום לא נמצא פתרון מדויק^[7]. החסם הטוב ביותר הידוע הוא מסדר גודל של 22 ספרות.^[8]

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

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

ערך מורחב – גרף פרש

החידה היא מקרה פרטי של בעיה חשובה בתורת הגרפים.

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

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

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

דרכים לפתרון

חלוקה לחלקים

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

גישוש נסוג

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

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

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

גישה זאת נקראת גישוש נסוג והיא לא יעילה.

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

8
7
6
5
4
3
2
1
	א	ב	ג	ד	ה	ו	ז	ח

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

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

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

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

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

וריאציות

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

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

קיום פתרון

הוכח, שיש מסלול סגור אם מתקיימים התנאים הבאים:

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

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

סקירת ההוכחה
ההוכחה תעשה בשלבים שברובם ניעזר באינדוקציה. את קיומם של מקרי הבסיס נזכיר בלי להראות אותם במפורש. הערה: במונח "אלכסון של פינה" נתכוון למשבצת הסמוכה הנוגעת בה באלכסון. לדוגמה, אלכסון של הפינה הימנית התחתונה הוא המשבצת השנייה מימין ושנייה מלמטה (ז2 בלוח רגיל).
טענה 1: לכל לוח 5xm יש מסלול פתוח המתחיל בפינה השמאלית התחתונה ונגמר באלכסון של הפינה הימנית התחתונה.
בסיס האינדוקציה: הצגת מסלול כזה עבור 5x5, 5x6, 5x7, 5x8, 5x9.
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את המסלול הזה לאלכסון של הפינה הימנית התחתונה ומשם נמשיך לפינה השמאלית התחתונה של הלוח מימין ונעשה את המסלול על פי הנחת האינדוקציה.
טענה 2: לכל לוח 6xm יש מסלול פתוח המתחיל בפינה השמאלית התחתונה ונגמר באלכסון של הפינה השמאלית העליונה.
בסיס האינדוקציה: הצגת מסלול כזה עבור 6x5, 6x6, 6x7, 6x8, 6x9.
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד לפינה הימנית התחתונה, משם נעבור לפינה השמאלית התחתונה של הלוח מימין ונבצע בו את המסלול על פי הנחת האינדוקציה. המסלול נגמר בפינה השמאלית העליונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.
טענה 3: לכל לוח 6xm יש מסלול סגור.
הוכחה: ניתן להציג מסלול כזה עבור 6x5, 6x6, 6x7, 6x8, 6x9. אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד לפינה ימנית תחתונה, משם נעבור לפינה שמאלית תחתונה של הלוח מימין ונבצע בו את המסלול שקיומו הוכח בטענה 2. המסלול נגמר בפינה שמאלית עליונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.
טענה 4: לכל לוח 8xm יש מסלול סגור.
בסיס האינדוקציה: הצגת מסלול כזה עבור 8x5, 8x6, 8x7, 8x8, 8x9.
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד לפינה הימנית התחתונה, משם נעבור לפינה השמאלית התחתונה של הלוח מימין ונבצע בו את המסלול על פי הנחת האינדוקציה. המסלול נגמר משבצת מעל הפינה הימנית התחתונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.
טענה 5: לכל לוח 8xm יש מסלול פתוח שמתחיל בפינה השמאלית התחתונה ומסתיים באלכסון של הפינה השמאלית העליונה.
הוכחה: ניתן להציג מסלול כזה עבור 8x5, 8x6, 8x7, 8x8, 8x9. אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד למשבצת רביעית מלמטה בשורה ימנית ביותר, משם נעבור למשבצת מעל אלכסון של פינה שמאלית תחתונה ונבצע בו את המסלול שקיומו הוכח בטענה 4. המסלול נגמר בפינה שמאלית תחתונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.
טענה 6: בכל לוח nx5 כאשר n זוגי ו-10≤n, יש מסלול סגור.
הוכחה: נחתוך מלמטה לוח בגודל 5x5. על פי למה 1, יש מסלול שמתחיל בפינה השמאלית העליונה ומסתיים באלכסון של הפינה הימנית התחתונה. נבצע אותו, ומשם נקפוץ לפינה הימנית התחתונה של הלוח העליון, ועל פי למה 1 ניתן לבצע מסלול שיגמר באלכסון של הפינה השמאלית התחתונה, ממנה ניתן לחזור לנקודת ההתחלה.
טענה 7: לכל לוח nxr כאשר r בין 5 ל-9 ו-n אי זוגי יש מסלול פתוח המתחיל בפינה השמאלית העליונה ומסתיים באלכסון של הפינה הימנית העליונה.
הוכחה: עבור r=5,6,8 זה הוכח בטענות 6,5,2 (עם סיבוב הלוח) עבור r=7,9 נבצע טיעון אנלוגי לטיעונים של טענות 1,7 (עם בניית לוחות מתאימים להנחת האינדוקציה).
בסיס האינדוקציה: טענה 7.
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל nx5, נבצע בו את המסלול הזה לאלכסון של הפינה הימנית העליונה ומשם נמשיך לפינה השמאלית העליונה של הלוח מימין ונעשה את המסלול על פי הנחת האינדוקציה.
משפט: לכל לוח nxm כאשר nm זוגי ושניהם לפחות 5 יש מסלול סגור.
הוכחה: נניח ללא הגבלת הכלליות ש-n זוגי. אם m=6,8 זה נובע מטענות 3,4. אחרת 10≤n ואז נחתוך מלמעלה לוח 5xm ונבצע בו על פי טענה 1 מסלול שמתחיל בפינה השמאלית התחתונה ומסתיים באלכסון של הפינה הימנית התחתונה. משם נקפוץ לפינה הימנית העליונה של הלוח התחתון. משם נפעיל את טענה 6 (הורדנו מ-n‏ 5 ולכן נשארנו עם מספר אי זוגי) ולהגיע לאלכסון של הפינה השמאלית העליונה, ממנה ניתן לחזור לנקודת ההתחלה.
משפט: לכל לוח mxn כששניהם לפחות 5 יש מסלול פתוח.
הוכחה: אם mn זוגי אז יש מסלול סגור, ובפרט מסלול פתוח (אם מורידים ממנו צעד 1) אם mn אי זוגי זה נובע מטענה 8.

נראה אי קיום של מסלול סגור בשאר הלוחות:

עבור 1xn או 2xn אי אפשר אפילו להגיע מכל משבצת לכל משבצת, ובוודאי שלא לעבור על כל המשבצות.
עבור 4xn נצבע את הלוח בצורה המתוארת משמאל: שורות עליונה ותחתונה בירוק, אמצעית באדום.

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

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

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

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

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

n:	4	5	6	7	8	9	10	11	12
מספר המסלולים הפתוחים בלוח nxn^[15]	0	1,728	6,637,920	165,575,218,320
מספר המסלולים הפתוחים בלוח 3xn^[16]	16	0	0	104	792	1,120	6,096	21,344	114,496
מספר המסלולים הסגורים בלוח (3x(2n^[17]	0	32	352	3,072	30,848	295,456	2,896,832	28,120,096	273,895,232
מספר המסלולים הפתוחים בלוח 4xn^[18]	0	82	744	6,378	31,088	189,688	1,213,112	6,683,852	36,486,328

שינוי צורת הלוח

פתרון

class=notpageimage|הצגה

אפשר לשאול את החידה גם ללוחות אחרים, לדוגמה:

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

כלים אחרים

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

התחל בפינה השמאלית התחתונה, ולך ימינה לאורך השורה.
עלה את העמודה הימנית, זוז משבצת אחת שמאלה, ורד את העמודה שמשמאלה עד לשורה השביעית מלמעלה.
כעת זוז משבצת אחת שמאלה וחזור על שלב 2 עוד שלוש פעמים.
רד משבצת אחת.

הפתרון מתואר בדיאגרמה משמאל.

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

גרסאות אחרות

פתרון לבעיית מסע הפרש שאינו חותך את עצמו (35 מסעים)

קיימות גרסאות נוספות לכל אלה שהוזכרו לעיל. וריאציה לדוגמה היא הגרסה הבאה:

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

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

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

אחד מהפתרונות של הבעיה הוא הפתרון הבא: (הפרש מתחיל במספר 1, מדלג בכל צעד למספר העוקב)

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

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

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

בתרבות

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

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

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

מדיה וקבצים בנושא חידת מסע הפרש בוויקישיתוף

Knight Graph, באתר MathWorld (באנגלית)
מאמרים על חידת מסע הפרש (באנגלית)
קישורים על החידה (באנגלית)

הערות שוליים

^ Early History of Knight's Tours
^ Rediscovery of the Knight's Problem
^ אברהם קריימר, מתמטיקה על לוח השחמט, הוצאת מכון ויצמן למדע, עמוד 8
^ The Turk
^ Knight and (May) Day
^ Knight’s Tours of an 8 8 Chessboard
^ Some Enumerations of Classes of 8×8 Knight's Tours
^ ¹ ² Olaf Kyeka, Ian Parberryb, Ingo Wegener, Bounds on the number of knight's tours, Volume 74, Issue 2, 18 April 1997, Pages 171–181
^ ¹ ² ³ Mathworld
^ ¹ ² Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisite" . Fibonacci Quarterly 16: 276–285.
^ An efficient algorithm for the Knight’s tour problem
^ Backtracking | Set 1 (The Knight’s tour problem), כולל מימוש של הקוד בשפת ג'אווה
^ Knight’s Tours Using a Neural Network
^ John J. Watkins, Across the Board: The Mathematics of Chessboard Problems עמודים 44-46
^ סדרה A165134 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
^ סדרה A118067 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
^ סדרה A158074 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
^ סדרה A079137 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
^ החידה לקוחה מהספר "מתמטיקה על לוח השחמט" מאת אברהם קריימר, הוצאת מכון ויצמן למדע
^ The Knight's Tour on the Cylinder and Torus
^ Which Chessboards have a Closed Knight’s Tour within the Rectangular Prism?‏,Joe DeMaio & Bindia Mathew
^ Fiveleaper Tours
^ History of Magic Knight's Tours
^ Magic Knight's Tours on the 8 by 8 Board
^ There Are No Magic Knight's Tours on the Chessboard באתר MathWorld
^ Knight's tour
^ Welcome to the Life A User’s Manual Big Read

[1] Early History of Knight's Tours

[2] Rediscovery of the Knight's Problem

[3] אברהם קריימר, מתמטיקה על לוח השחמט, הוצאת מכון ויצמן למדע, עמוד 8

[4] The Turk

[5] Knight and (May) Day

[6] Knight’s Tours of an 8 8 Chessboard

[7] Some Enumerations of Classes of 8×8 Knight's Tours

[פתרונות-8] ¹ ² Olaf Kyeka, Ian Parberryb, Ingo Wegener, Bounds on the number of knight's tours, Volume 74, Issue 2, 18 April 1997, Pages 171–181

[Mathworld-9] ¹ ² ³ Mathworld

[חלוקה-10] ¹ ² Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisite" . Fibonacci Quarterly 16: 276–285.

[11] An efficient algorithm for the Knight’s tour problem

[12] Backtracking | Set 1 (The Knight’s tour problem), כולל מימוש של הקוד בשפת ג'אווה

[13] Knight’s Tours Using a Neural Network

[14] John J. Watkins, Across the Board: The Mathematics of Chessboard Problems עמודים 44-46

[15] סדרה A165134 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים

[16] סדרה A118067 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים

[17] סדרה A158074 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים

[18] סדרה A079137 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים

[19] החידה לקוחה מהספר "מתמטיקה על לוח השחמט" מאת אברהם קריימר, הוצאת מכון ויצמן למדע

[20] The Knight's Tour on the Cylinder and Torus

[21] Which Chessboards have a Closed Knight’s Tour within the Rectangular Prism?‏,Joe DeMaio & Bindia Mathew

[22] Fiveleaper Tours

[23] History of Magic Knight's Tours

[24] Magic Knight's Tours on the 8 by 8 Board

[25] There Are No Magic Knight's Tours on the Chessboard באתר MathWorld

[26] Knight's tour

[27] Welcome to the Life A User’s Manual Big Read

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]