חידת מסע הפרש
חידת מסע הפרש היא חידת שחמט שבה צריך למצוא את דרכו של פרש על גבי כל משבצות לוח השחמט, כך שיעבור פעם אחת בלבד בכל משבצת. ניתן להוסיף לחידה את הדרישה שהפרש יוכל לחזור מהנקודה האחרונה לנקודת ההתחלה בתור אחד (מסלול כזה נקרא "מסלול סגור").
ניתן לתרגם את החידה לבעיה מתורת הגרפים: יש למצוא מסלול המילטוני בגרף מתאים (שקודקודיו הם משבצות הלוח, והקשתות בו מייצגות מהלכי פרש חוקיים).
מספר המסלולים הסגורים הפותרים את החידה הוא 13,267,364,410,532 . מספר המסלולים הפתוחים עדיין אינו ידוע.
מתמטיקאים רבים חקרו את החידה, ובהם לאונרד אוילר. אוילר יצר ריבוע קסם מיוחד שבו סכום כל שורה או עמודה שווים ל-260 וסכום כל מחצית שורה או עמודה שווים ל-130, ופרש אשר מתקדם לפי סדר המספרים פותר את חידת מסע הפרש.
-
פתרון לחידה במסלול פתוח
-
פתרון לחידה במסלול סגור
-
ריבוע הקסם של אוילר
.png)
דרכים לפתרון [עריכה]
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| בתמונה נראות כמה אפשרויות להזיז את הפרש, ועליהן רשום מספר המשבצות שאליהן יוכל להגיע הפרש לאחר מכן. יש לבחור את המשבצת עליה כתוב המספר 2, מאחר וזהו המספר הקטן ביותר. |
קיימים מספר אלגוריתמים לפתרון הבעיה. אלגוריתם חמדן פותר בעיה זו כדלקמן: בכל תור יש להוביל את הפרש אל המשבצת, שממנה ניתן להגיע בתור לאחר מכן אל המספר הקטן ביותר של משבצות. (נספרות רק משבצות "חוקיות", כלומר שהפרש עדיין לא היה בהן.) אם יש מספר מספר משבצות בעלות המספר הקטן ביותר, יש לבחור אחת מהן באופן אקראי.
בניסוח של תורת הגרפים, יש להזיז את הפרש לקודקוד סמוך בעל הדרגה הקטנה ביותר. (דרך זו אינה עובדת לכל גרף; למעשה, מציאת מסלול המילטוני בגרף כללי היא בעיית NP קשה. חידת הפרש היא מקרה מיוחד.)
