חידת מסע הפרש

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

יש שתי גרסאות מרכזיות: מסלול פתוח, שבו ההתחלה והסוף שונים, ומסלול סגור, שבו המשבצת האחרונה תחבר חזרה למשבצת ההתחלה.

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

נמצאו בדיוק 26,534,728,821,064 מסלולים סגורים. אם מתעלמים מהבדלים שמתקבלים רק על ידי סיבוב או שיקוף של הלוח, יש 1,658,420,855,433 פתרונות. תוצאות אלה הוכחו על ידי ברנדן מקיי ב-1997.

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

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

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

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

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

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

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

מסלול פתוח קיים ברוב הגדלים, למעט מקרים קטנים כגון 1xn, 2xn, 3x3, 3x5, 3x6 ו-4x4.

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

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

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

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

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

החידה ידועה כבר לפני יותר מאלף שנה. אנשים הודים וערבים כתבו עליה במאה ה-9 וה-10. גם במאות הבאות מדענים חשבו עליה.

יש הרבה מאוד פתרונות סגורים. בשנת 1997 הוכח שיש בדיוק 26,534,728,821,064 כאלה. זה מספר עצום.

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

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

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

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