מגדלי האנוי באינטרנט, בחינם

מגדלי האנוי (Tower of Hanoi) — אחד מהחידות הלוגיות המפורסמות ביותר בהיסטוריה, המוקפת באגדה מרתקת ובמורשת תרבותית עשירה. על אף פשטות המבנה — שלושה מוטות וסט של דיסקים בקטרים שונים — המשחק מתבלט בעומק הלוגי שלו ובמשיכת המיתוס הקשור אליו. המשחק, שהומצא במאה ה־19, כבש במהרה את לב חובבי החידות והמתמטיקאים ברחבי העולם.

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

ההיסטוריה של מגדלי האנוי

מקור ומחבר

חידת מגדלי האנוי נוצרה בצרפת בשנת 1883 והפכה במהרה למפורסמת בזכות השילוב הייחודי של פשטות הצורה עם רעיון מתמטי אלגנטי. מחברה היה המתמטיקאי הצרפתי אדואר לוקאס (Édouard Lucas) — חוקר שהתפרסם במחקריו בתחום תורת המספרים, וכן בהנגשת המדע באמצעות מה שכונה «מתמטיקה של בידור».

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

עם הזמן הבחינו חוקרים קפדניים במשחק מילים נסתר. התברר כי השם N. Claus (de Siam) הוא אנגרמה של Lucas d’Amiens (לוקאס מאמיין), וכי ה«קולג’ Li-Sou-Stian» שהוזכר בתיאורים מתהפך לשם בית הספר התיכון Saint Louis בפריז, שבו לוקאס לימד. כך, האגדה שנבנתה בקפידה התגלתה כחידה מתוחכמת שבה השאיר המחבר את חתימתו.

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

המהדורה הראשונה של המשחק

במקור יצאה החידה בצרפת תחת השם La Tour d’Hanoï («המגדל של האנוי») ונלוותה אליה הוראות מודפסות שבהן הוסבר מוצאה המיתולוגי בצורה נגישה. הערכה כללה בסיס עץ עם שלושה מוטות אנכיים וסט של שמונה דיסקים מחוררים בגדלים שונים. בחירת שמונה הדיסקים נעשתה על ידי אדואר לוקאס עצמו: מספר זה נראה מספיק מורכב כדי לשמור על עניין, אך עדיין ניתן לפתרון.

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

בשנים 1884–1885 הופיעו תיאורים ואיורים של מגדלי האנוי במגזינים פופולריים. כך, כתב העת הצרפתי La Nature פרסם גרסה של האגדה על «מגדל ברהמה» והציג את החידה החדשה כחלק ממיתוס מזרחי. באותה שנה הופיעה בכתב העת האמריקאי Popular Science Monthly ידיעה מלווה בתחריט שבו תואר תהליך פתרון הבעיה. פרסומים אלו מילאו תפקיד חשוב בהפצת המשחק מעבר לגבולות צרפת: בזכות העיתונות הוא נודע באירופה ובארצות הברית, ובכך ביסס את מעמדו כחידה קלאסית הראויה לתשומת לבם של מדענים ושל הציבור הרחב.

האגדה על מגדל ברהמה

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

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

אך גם אם נדמיין את התרחיש המהיר ביותר — צעד אחד בכל שנייה — לאנושות אין סיבה לדאגה: להשלמת הבעיה דרושות 2^64 – 1 העברות, שהם כ־585 מיליארד שנה. פרק זמן זה ארוך פי עשרות מגילה של היקום לפי המדע המודרני. כך האגדה לא רק העניקה לחידה נופך דרמטי, אלא גם כללה קורטוב של הומור אלגנטי: היא הדגישה שהבעיה קשה ביותר, אך בו בזמן נתנה למתמטיקאים ולאוהבי חידות אפשרות «לחשב את קץ העולם» במסגרת סיפור יפה.

הפצה והתפתחות

המשחק מגדלי האנוי כבש במהירות את אירופה. בסוף המאה ה־19 הוא היה מוכר לא רק בצרפת אלא גם באנגליה ובאמריקה הצפונית. בשנת 1889 פרסם אדואר לוקאס חוברת נפרדת עם תיאור החידה, ולאחר מותו בשנת 1891 נכללה הבעיה בכרך שלאחר מותו של ספרו המפורסם «Récréations mathématiques». בזכות פרסום זה מגדלי האנוי התבססו סופית כחלק מהמורשת הקלאסית של המתמטיקה הבידורית.

בערך באותו זמן החידה החלה להתפשט תחת שמות שונים: «מגדל ברהמה», «מגדל לוקאס» ואחרים — בהתאם למדינה ולמוציא לאור. יצרני צעצועים במדינות שונות הוציאו גרסאות משלהם, משום שלוקאס לא רשם פטנט על ההמצאה והמבנה היה חופשי להעתקה. באנגליה בראשית המאה ה־20, למשל, הופיעו מהדורות בשם The Brahma Puzzle. ידועים עותקים שנותרו שפורסמו בלונדון על ידי חברת R. Journet בסביבות 1910–1920, שעל הקופסה הודפס טקסט האגדה על הכוהנים ועל 64 הדיסקים המוזהבים.

בארצות הברית נכנס מגדלי האנוי לאוסף ה«צעצועים המדעיים» הפופולריים ומצא במהירות את מקומו לצד בידורים לוגיים מפורסמים אחרים. פשטות המבנה — שלושה מוטות וסט דיסקים — אפשרה לייצר את המשחק בקלות, והגרסאות השונות של האגדה הפכו אותו למושך עוד יותר. בעשורים הראשונים של המאה ה־20 התפשטה החידה באלפי עותקים ותפסה מקום לצד קלאסיקות כמו חידת ה־15 ומאוחר יותר קוביית רוביק (אם כי כמובן מגדלי האנוי הופיעו הרבה לפני הקובייה).

קביעות הכללים והמשמעות המדעית

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

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

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

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

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

הגיאוגרפיה של הפופולריות

השם מגדלי האנוי מתייחס ישירות לבירת וייטנאם — העיר האנוי, אף על פי שהחידה עצמה אינה בעלת שורשים מזרחיים אמיתיים והיא הומצאה לחלוטין בצרפת בסוף המאה ה־19. עם זאת, הנופך האקזוטי של האגדה התגלה כמוצלח ביותר: הוא העניק למשחק מסתורין וסייע בהפצתו הרחבה. משום כך במדינות שונות הוא התקבע בשם הקשור להאנוי: בעולם דובר האנגלית — Tower of Hanoi, בצרפת — Tour d’Hanoï, בגרמניה — Türme von Hanoi וכן הלאה.

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

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

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

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

עובדות מעניינות על מגדלי האנוי

• שיא במספר הדיסקים. במוזיאונים ובאוספים פרטיים קיימות גרסאות ענק של מגדלי האנוי עם שלושים ואף יותר דיסקים. מספר המהלכים המינימלי עבור בעיה כזו עולה על מיליארד, ולכן פתרונה ביד כמעט בלתי אפשרי. סטים כאלה נוצרו לא למשחק אלא כתצוגות מרשימות המדגישות את המורכבות האינסופית והעומק המתמטי של החידה.
• המגדל בתרבות הפופולרית. מגדלי האנוי הופיעו פעמים רבות בספרות, בקולנוע ובסדרות טלוויזיה. בסיפור המדע הבדיוני המפורסם של הסופר האמריקאי אריק פרנק ראסל (Eric Frank Russell) «Now Inhale» (1959), הגיבור הראשי, המצפה להוצאה להורג בידי חייזרים, בוחר במשחק מגדלי האנוי כ«משאלתו האחרונה». הוא עושה זאת במודע, ביודעו על אינסופיותה האגדית של הבעיה. כדי להעניק לאירוע אופי תחרותי, החייזרים הופכים את החידה לדו־קרב: שני שחקנים מבצעים מהלכים לסירוגין, והמנצח הוא זה שמבצע את המהלך האחרון. בבחירת מגדל עם 64 דיסקים מבטיח לעצמו הגיבור בפועל דחייה אינסופית. גם בקולנוע המודרני מופיע המשחק. בסרט «Rise of the Planet of the Apes» (2011) משמשת החידה כמבחן אינטלקטואל עבור קופים שהונדסו גנטית: אחד מהם מרכיב מגדל מארבע טבעות בעשרים מהלכים. אף שזה יותר מהמספר המינימלי האפשרי (15 מהלכים אופטימליים), הסצנה עצמה מדגישה את כישורי החשיבה של בעלי החיים וממחישה היטב את מורכבות הבעיה. גם הסדרה הבריטית הקלאסית «Doctor Who» התייחסה לחידה הזו. בפרק «The Celestial Toymaker» (1966) התבקש הדוקטור לפתור מגדלי האנוי עם עשרה דיסקים. תנאי המבחן היה נוקשה ביותר: עליו היה לבצע בדיוק 1023 מהלכים — לא יותר ולא פחות. מספר זה נבחר לא במקרה: 1023 הוא מספר המהלכים המינימלי האפשרי עבור בעיה עם עשרה דיסקים. לפיכך היה על הגיבור לעבור את כל הדרך ללא אף טעות אחת, מה שחיזק שוב את המוניטין של מגדלי האנוי כאתגר כמעט בלתי־אפשרי אפילו לגאון נוסע בזמן.
• נוכחות במשחקי וידאו. מעניין שמגדלי האנוי הפכו ל«תקן חידה» וחדרו לעולם משחקי הווידאו. הסטודיו הקנדי BioWare ידוע בכך שהוא כולל מיני־משחק המבוסס על מגדלי האנוי ברבים מהפרויקטים שלו. לדוגמה, במשחק התפקידים Jade Empire יש משימה שבה צריך להעביר טבעות על עמודים, וחידות דומות מופיעות בסדרות המפורסמות Star Wars: Knights of the Old Republic, Mass Effect ו־Dragon Age: Inquisition. קטעים אלו מוצגים לעתים קרובות כמנגנונים עתיקים או מבחנים הדורשים מהגיבור תושייה. החידה מופיעה גם במשחקי הרפתקאות קלאסיים, למשל ב־The Legend of Kyrandia: Hand of Fate, שבו אחד מהמנגנונים המסתוריים הוא למעשה מגדלי האנוי בתחפושת של טקס קסום. הופעות כאלה מחזקות את הדימוי של מגדלי האנוי כסמל אוניברסלי של חידה לוגית.
• היבט חינוכי. מעבר לאגדות ולבידור, מגדלי האנוי הותירו חותם גם במדע. בשנת 2013 פרסמו חוקרים מונוגרפיה בשם «The Tower of Hanoi: Myths and Maths» (Hinz et al.), החוקרת בפירוט את המאפיינים המתמטיים של החידה וגרסאותיה. התברר שסביב החידה נבנתה תיאוריה שלמה של «גרפי מגדלי האנוי», הקשורה לפרקטל של סירפינסקי ולתחומים אחרים במתמטיקה. בפסיכולוגיה קוגניטיבית קיים מבחן «מגדלי האנוי» שבאמצעותו בודקים את התפקודים הניהוליים של המוח — היכולת לתכנן ולעקוב אחר כללים מורכבים. ברפואה משמש מבחן זה להערכת רמת ההחלמה של מטופלים לאחר פגיעות מוחיות: היכולת לפתור את הבעיה משמשת כסמן לתפקוד האונות המצחיות וליצירת קשרים עצביים חדשים. כך הפך משחק שבעבר נמכר כצעצוע מהנה לנושא מחקר רציני ואף לכלי שיקומי.

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

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

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

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

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

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

כללי מגדלי האנוי: איך לשחק

מטרת המשחק

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

ציוד

למשחק משתמשים בבסיס עם שלושה מוטות אנכיים, שמסומנים לרוב כ־A,‏ B ו־C. בנוסף נדרש מערך של n דיסקים בקטרים שונים (n ≥ 3; בגרסה הקלאסית — 8). לכל הדיסקים יש חורים וניתן להזיזם בחופשיות בין המוטות. בתחילת המשחק הם משורשרים על מוט A ויוצרים פירמידה: הדיסק הגדול ביותר נמצא למטה, ומעליו מסודרים בהדרגה הקטנים יותר.

כללי מהלכים

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

מהלך המשחק

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

סיום

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

מספר המהלכים המינימלי

הוכח תאורטית שמספר המהלכים האופטימלי לפתרון מגדלי האנוי עם n דיסקים שווה ל־2^n − 1. לערכים קטנים קל לבדוק זאת: עבור שלושה דיסקים — 7 מהלכים, עבור ארבעה — 15, עבור חמישה — 31. לדוגמה, עבור שמונה דיסקים נדרשים 255 מהלכים, עבור עשרה — כבר 1023. כל סטייה מהאסטרטגיה האופטימלית מגדילה את מספר המהלכים, ולכן שחקנים מנוסים שואפים לעקוב אחרי המסלול המינימלי.

וריאציות של הכללים

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

• עם מוטות נוספים. הוספת מוט רביעי או חמישי מביאה לחיפוש אחר אלגוריתמים חדשים להעברה. ידוע כי בארבעה מוטות מספר המהלכים המינימלי קטן יותר מאשר בשלושה (גרסה זו ידועה כ־Reve’s Puzzle). כך, שמונה דיסקים ניתן להעביר ב־129 מהלכים במקום 255. עבור מספר כלשהו של מוטות אין נוסחה כללית: השערת פריים–סטיוארט (Frame–Stewart) משמשת כקו מנחה, אך היא נותרה בלתי מוכחת כבר יותר משבעה עשורים.
• המגדל המחזורי. בגרסה זו המוטות ממוקמים במעגל, והדיסקים ניתנים להעברה רק בכיוון אחד (למשל, עם כיוון השעון), מבלי «לקפוץ» מעל מוט ביניים. כך, ממוט A ניתן להעביר דיסק רק למוט B, מ־B ל־C וכן הלאה. מגבלה זו מקשה באופן ניכר על האסטרטגיה ומגדילה את מספר המהלכים, אף על פי שההיגיון הרקורסיבי נשאר בבסיס הפתרון.
• המשולש הקסום. וריאציה נוספת שבה שלושת המוטות ממוקמים בקודקודי משולש. אותם כללים חלים (דיסק אחד בכל פעם, אין להניח גדול על קטן), אך נוסף תנאי: הדיסק הקטן ביותר נע רק עם כיוון השעון, וכל השאר — בכיוון ההפוך. גרסה זו למעשה קרובה למגדל המחזורי וקשורה לשימוש בקוד גריי בינארי (Frank Gray): רצף העברת הדיסקים תואם לקודים המסודרים ללא צעדים מיותרים.

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

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

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

גישות טקטיות

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

• אלגוריתם «שחרור הדיסק הגדול». האלמנט המרכזי של החידה הוא הדיסק הגדול ביותר. לא ניתן להזיזו כל עוד כל הדיסקים מעליו לא הוסרו. לכן הפתרון תמיד בנוי משני שלבים: תחילה יש להסיר n − 1 דיסקים קטנים יותר ולהניחם זמנית על מוט עזר, אחר כך להעביר את הדיסק הגדול ביותר למוט היעד, ולאחר מכן להרכיב עליו מחדש את הפירמידה מ־n − 1 דיסקים. טכניקה זו היא הבסיס לשיטה הרקורסיבית: כדי להעביר מגדל עם n דיסקים, יש תחילה לפתור את אותה הבעיה עבור n − 1 דיסקים. בפועל המשמעות היא שהשחקן צריך למקד בכל שלב את תשומת ליבו בשחרור הדרך לאלמנט הגדול ביותר.
• תפקיד הדיסק הקטן ביותר. הדיסק הקטן ביותר הוא הנייד ביותר ובפועל קובע את קצב כל המשחק. קיימת אסטרטגיה שבה הוא זז בכל מהלך שני, מתחלף עם הדיסקים האחרים. במספר אי־זוגי של דיסקים המהלך הראשון תמיד לכיוון מוט היעד (A → C), במספר זוגי — למוט העזר (A → B). לאחר מכן הדיסק הקטן נע במעגל: ב־n אי־זוגי — עם כיוון השעון (A → C → B → A ...), ב־n זוגי — נגד כיוון השעון (A → B → C → A ...). תבנית סדירה זו ממכנת מחצית מהמהלכים והופכת את התהליך לצפוי.
• מהלך יחיד אפשרי. לאחר כל הזזה של הדיסק הקטן, נוצר מהלך אפשרי יחיד: מבין שאר הדיסקים ניתן באותו רגע להזיז רק אחד מבלי להפר את הכללים. משמעות הדבר היא שהאסטרטגיה מצטמצמת לחלופה: «דיסק קטן → הדיסק הגדול היחיד המותר → קטן → גדול יחיד...». אלגוריתם זה מבטיח פתרון במספר המהלכים המינימלי ומגן גם על מתחילים מטעויות.

טעויות של מתחילים

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

• מהלכים אקראיים ללא תוכנית. שגיאה נפוצה היא להזיז דיסקים באופן אקראי, ללא אסטרטגיה כללית. מהלכים אקראיים יכולים לעבוד עם 3–4 דיסקים, אך עם 5–6 הם מובילים למעגליות. עדיף לעקוב מיד אחרי האלגוריתם: לשחרר את הדיסק הגדול, להעבירו ולשחזר את הפירמידה. אסטרטגיה מושכלת מונעת מהלכים מיותרים וחוסכת זמן.
• הפרת כלל הגודל. מתחילים מנסים לעיתים להניח דיסק גדול על קטן יותר. בערכה אמיתית מהלך כזה אפשרי פיזית, אך הוא מפר את הכללים והופך את סידור הדיסקים לבלתי תקין. בגרסאות דיגיטליות מהלכים כאלה נחסמים בדרך כלל על ידי התוכנה. יש לוודא תמיד שהדיסק מונח או על מוט ריק או על דיסק גדול יותר.
• ניסיון לפרק את המגדל כולו. מתחילים מנסים לעיתים «לפרוק» את כל הדיסקים למוטות הפנויים, מתוך מחשבה שאחר כך יהיה קל יותר להרכיב את הפירמידה על מוט היעד. המשחק אינו מאפשר זאת: אחד המוטות נשאר תפוס בהכרח וחוסם מהלכים. הדרך היעילה — העברה הדרגתית: להעביר חלק מהדיסקים למוט העזר, לשחרר ולהעביר את הדיסק המרכזי (הגדול), ואז להחזיר את החלק שהוסר.
• חיפזון וחוסר תשומת לב. מגדלי האנוי — משחק מתון. מהלכים חפוזים גורמים לדילוג על צעדים נחוצים ולהגדלת מספר המהלכים. במיוחד בהתחלה כדאי לשמור על קצב אחיד, לעקוב אחרי מצב שלושת המוטות ולחשב מראש את תוצאות כל מהלך; כך קל יותר להגיע לפתרון המינימלי.

אסטרטגיות למתקדמים

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

• חשיבה רקורסיבית. לאחר שליטה במגדל הקלאסי עם 5–6 דיסקים, נסו ליישם במודע את הגישה הרקורסיבית עבור n גדול יותר. חלקו את המשימה לשלבים: העבירו את k הדיסקים העליונים למוט עזר, העבירו את הדיסק (n − k) למוט היעד, ואז החזירו את k הדיסקים. באלגוריתם האופטימלי תמיד k = n − 1, כלומר מוסרים כל הדיסקים מלבד התחתון. אך לצורך תרגול ניתן לנסות גם אפשרויות אחרות, אף אם הן פחות יעילות. תרגיל זה מסייע להבין בפועל מדוע מספר המהלכים המינימלי הוא 2^n − 1, ולשים לב שכל דיסק נוסף מכפיל את מספר המהלכים ומוסיף אחד.
• קוד בינארי והמגדל. את מהלכי מגדלי האנוי ניתן לייצג כרצף של מספרים בינאריים. כל דיסק מתאים לספרה, ומיקומו — לשינוי ספרה זו. כאן מתגלה הקשר לקוד גריי: במעבר ממצב אחד לאחר משתנה רק ביט אחד, דבר המתאים להעברת דיסק אחד. תובנה זו אינה מועילה במיוחד במשחק ידני, אך מאפשרת לראות את הבעיה כסריקה רציפה של כל המספרים מ־0 עד 2^n − 1 בצורה בינארית. לניסיון, נסו לממש אלגוריתם לפתרון בתוכנה: הדבר יחזק את ההבנה של רקורסיה וחשיבה אסטרטגית.
• פתרון «בעיניים עצומות». תרגול נוסף שימושי — לפתור את מגדלי האנוי ללא ערכה פיזית, על ידי רישום המהלכים. תנו שמות למוטות A, B ו־C וכתבו את רצף ההעברות: למשל, עבור n = 2 — A → B, A → C, B → C; עבור n = 3 — A → C, A → B, C → B, A → C, B → A, B → C, A → C. ברצפים אלה נראית בבירור המבנה הרקורסיבי. הבנת התבנית תאפשר לפתור את המשימה בדמיון, מה שמפתח היטב חשיבה מופשטת.
• מוטות נוספים. אם הגרסה הבסיסית אינה מהווה קושי, נסו לשחק עם ארבעה מוטות. כאן האסטרטגיה המינימלית אינה כה ברורה. עבור ארבעה מוטות הנוסחה המדויקת אינה ידועה, ואופטימליותם של מספר אלגוריתמים נותרה בלתי מוכחת. עם זאת ידוע שעבור 15 דיסקים הפתרון המינימלי בארבעה מוטות דורש 129 מהלכים — בעוד שבשלושה היו נדרשים 32,767. התנסו: לאיזה מוטות להעביר ערימות ביניים, כמה דיסקים לערב בכל שלב. הדבר מפתח גישה יצירתית ומאפשר הבנה עמוקה יותר של עקרונות האסטרטגיה של החידה.

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

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

החידה, שנוצרה לפני יותר מ־140 שנה, ממשיכה להעניק השראה גם היום. בניסיון להרכיב את המגדל אתם הופכים לחלק ממסורת ארוכה של חובבי משחק זה — מתלמידים ועד פרופסורים למתמטיקה. האוניברסליות והעומק שלה הופכים את מגדלי האנוי לעיסוק מחוץ לזמן, המאחד דורות. מוכנים לבחון את עצמכם? שחקו במגדלי האנוי אונליין עכשיו — בחינם וללא הרשמה!