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