פאזל מגדלי האנוי: היסטוריה, אסטרטגיה ומהלכים מומלצים
לַחֲלוֹק
מגדל האנוי הוא אחד מאותם חידות שנראים פשוטים מדי מכדי להיות מעניינים. שלושה יתדות. ערימת דיסקים. להזיז אותם לשם. נגמר, נכון?
טועה.
שבו בפעם הראשונה עם גרסת 7 דיסקים ותגלו במהרה ש"חוקים פשוטים" ו"פתרון קל" הם דברים שונים מאוד. מגדל האנוי טומן בחובו עומק מתמטי אמיתי בתוך מערך מינימליסטי ואלגנטי – והשילוב הזה הוא בדיוק הסיבה שבגללה הוא שרד למעלה מ-140 שנה, הופיע בספרי לימוד במדעי המחשב, וזכה למקום קבוע במדף של אספני חידות רציניים.
במדריך זה אני רוצה לכסות הכל: ההיסטוריה, האגדה, המתמטיקה (מוסברת בצורה שבאמת הגיונית), איך לפתור אותה במספר דיסקים שונה, ואיך לבחור את הגרסה הפיזית הנכונה לקנות. בין אם אתם מתחילים עם זה כחידת היגיון ראשונה או מוסיפים אותה לאוסף של חידות מכניות, יש כאן יותר ממה שאתם מצפים.
מהו פאזל מגדל האנוי? חוקים, הגדרה ומטרת המשחק
ההגדרה היא שלושה יתדות אנכיים וסט של דיסקים עם חורים במרכזם, הערוכים על יתד אחד לפי הסדר מהגדול לקטן. הגרסה הקלאסית משתמשת ב-7 או 8 דיסקים. הגרסה הקטנה ביותר הנמכרת למתחילים משתמשת בדרך כלל ב-3.
מטרתכם היא להעביר את הערימה כולה מהיתד ההתחלתי ליתד היעד.
פשוט מספיק. אבל יש שני חוקים שהופכים את זה לקשה באמת:
- אתם יכולים להזיז דיסק אחד בלבד בכל פעם.
- אסור לכם אף פעם להניח דיסק גדול יותר על גבי דיסק קטן יותר.
החוק השני הוא זה שפועל נגדכם ללא הרף. בכל פעם שאתם מתקדמים בהזזת דיסקים גדולים למקומם, הדיסקים הקטנים יושבים במקום לא נוח ואתם צריכים להזיז אותם קודם. והזזתם מדרך משמעותה שהם נגמרים במקום אחר לא נוח. וכך זה נמשך.
הפאזל נפתר כאשר הערימה המלאה משוחזרת על יתד אחר בסדר הנכון.
אין חלקים רופפים. אין מנגנונים נסתרים. רק היגיון ורצף. זו אחת הדוגמאות הטהורות ביותר לחידת אתגר מחשבתי הקיימות – כל האתגר נמצא בתוך החוקים, לא בתוך שום תחבולה פיזית.
ההיסטוריה והאגדה שמאחורי מגדל האנוי
מגדל האנוי הומצא בשנת 1883 על ידי המתמטיקאי הצרפתי אדוארד לוקאס. הוא פרסם אותו תחת השם "נ. קלאוס דה סיאם" – אנגרמה שובבה של שמו שלו, "לוקאס ד'אמיין". סוג כזה של משחק מילים התאים מאוד למתמטיקאי שברור שנהנה מחידה טובה.
לוקאס שיווק אותו עם אגדה נלווית על מקדש בהאנוי (או בבנארס, תלוי בגרסת הסיפור) שבו נזירים עבדו על גרסת 64 דיסקים מאז בריאת העולם. האגדה מספרת: כשיסיימו להעביר את כל 64 הדיסקים באמצעות החוקים המותרים, העולם יגיע לקיצו.
מתברר, שזה מפחיד מתמטית. המספר המינימלי של מהלכים הנדרשים לפתור מגדל האנוי עם 64 דיסקים הוא 2 בחזקת 64 פחות 1. זה 18,446,744,073,709,551,615 מהלכים. אם הנזירים היו מבצעים מהלך אחד לשנייה ללא הפסקה, זה היה לוקח להם בערך 585 מיליארד שנים לסיים. גיל היקום הנוכחי הוא כ-13.8 מיליארד שנים. אז כנראה שאנחנו בסדר.
לוקאס כמעט בוודאות המציא את האגדה בעצמו כדי למכור את הפאזל. אבל היא דבקה – והיא סוג של אגדת פאזל מושלמת כי היא למעשה מבוססת על מתמטיקה אמיתית. הסיפור אינו רק טעם. זו תוצאה ישירה של נוסחת הצמיחה האקספוננציאלית השולטת בפתרון הפאזל.
לאחר שחרורו המסחרי, מגדל האנוי עבר במהירות להקשרים אקדמיים וחינוכיים. עד המאה ה-20 הוא הפך לדוגמה סטנדרטית במדעי המחשב להוראת רקורסיה - עוד על כך בעוד רגע. הוא גם נתן השראה למשפחה של חידות מתמטיות קשורות ונשאר אחד האובייקטים הנלמדים ביותר בקומבינטוריקה ותורת האלגוריתמים.
די מרשים אם אתם שואלים אותי.
המתמטיקה שגורמת לזה לעבוד: מהלכים מינימליים, קוד בינארי, ורקורסיה מוסברת בפשטות
כאן זה נהיה מעניין באמת. רוב הפאזלים מדלגים על החלק הזה או פשוט מציגים את הנוסחה מבלי להסביר אותה. תנו לי לעבור על זה בפועל.
נוסחת המהלכים המינימליים
עבור מגדל האנוי עם n דיסקים, מספר המהלכים המינימלי הנדרש לפתור אותו הוא:
2^n - 1
אז:
- 3 דיסקים: 7 מהלכים
- 4 דיסקים: 15 מהלכים
- 5 דיסקים: 31 מהלכים
- 6 דיסקים: 63 מהלכים
- 7 דיסקים: 127 מהלכים
- 8 דיסקים: 255 מהלכים
- 64 דיסקים: 18,446,744,073,709,551,615 מהלכים
כל דיסק שמוסיפים מכפיל את מספר המהלכים הנדרשים ומוסיף אחד נוסף. צמיחה אקספוננציאלית זו היא הסיבה שהפאזל הזה מתרחב בצורה כה אכזרית. שלושה דיסקים מרגישים ניתנים לניהול. שבעה דיסקים הם אתגר רציני. עשרה דיסקים מתחילים להרגיש כמעט מופשטים.
למה הנוסחה הזו עובדת: ההיגיון הרקורסיבי
הנה הדרך הברורה ביותר להבין זאת. כדי להזיז את הדיסק הגדול ביותר מיתד A ליתד C, עליכם קודם כל להזיז כל דיסק שמעליו מן הדרך. זה אומר להזיז n-1 דיסקים מיתד A ליתד B. לאחר מכן אתם מזיזים את הדיסק הגדול. לאחר מכן אתם מזיזים את כל n-1 הדיסקים מיתד B ליתד C.
לכן, מספר המהלכים עבור n דיסקים שווה: פי שניים ממספר המהלכים עבור n-1 דיסקים, בתוספת מהלך אחד עבור הדיסק הגדול עצמו.
מתמטית: T(n) = 2 * T(n-1) + 1
זוהי הגדרה רקורסיבית - הבעיה עבור n דיסקים מוגדרת במונחים של אותה בעיה עבור n-1 דיסקים. מדעני מחשב אוהבים זאת מכיוון שהיא מתאימה בצורה מושלמת לאלגוריתם רקורסיבי. מגדל האנוי הוא פשוטו כמשמעו בעיה בספרי לימוד ללימוד רקורסיה בקורסי תכנות ברחבי העולם.
החיבור הבינארי
הנה החלק שתמיד מפתיע אנשים. יש קשר ישיר בין פתרון מגדל האנוי למספרים בינאריים.
אם תמספרו את המהלכים שלכם באופן רציף - מהלך 1, מהלך 2, מהלך 3 וכן הלאה - ותמירו כל מספר מהלך לבינארי, מיקום הספרה 1 הימנית ביותר במספר הבינארי הזה יגיד לכם איזה דיסק להזיז בשלב זה. הזוגיות (מיקום אי-זוגי או זוגי) תגיד לכם לאיזה כיוון להזיז אותו.
במילים אחרות, הפתרון האופטימלי המלא למגדל האנוי מקודד ברצף הספירה הבינארית. בכל פעם שאתם סופרים בבינארית, אתם פותרים באופן מרומז את מגדל האנוי. הקשר הזה אמיתי, מוכח, וקצת פרוע כשיושבים איתו.
זו הסיבה שמתמטיקאים ומדעני מחשב ממשיכים לחזור לפאזל הזה. זה לא רק צעצוע. זהו חלון למבנה עמוק באמת במתמטיקה דיסקרטית.
איך לפתור את מגדל האנוי צעד אחר צעד: אסטרטגיה עבור 3, 4, ו-7 דיסקים
לדעת את התיאוריה זה דבר אחד. לפתור אותה בפועל זה דבר אחר. הנה האסטרטגיה המעשית.
אסטרטגיית הרקורסיה המרכזית
חשבו על זה כך. תנו שמות ליתדות: מקור (S), עזר (A), ויעד (T).
כדי להזיז n דיסקים מ-S ל-T:
- הזיזו את n-1 הדיסקים העליונים מ-S ל-A (באמצעות T כעזר).
- הזיזו את הדיסק הגדול ביותר מ-S ל-T.
- הזיזו את n-1 הדיסקים מ-A ל-T (באמצעות S כעזר).
זהו האלגוריתם המלא. כל פתרון, בכל כמות דיסקים, עוקב אחר מבנה זה בדיוק באופן רקורסיבי. עומק הרקורסיה הוא מה שיוצר את המורכבות.
פתרון 3 דיסקים (7 מהלכים)
זוהי נקודת הכניסה. נסמן דיסקים 1 (הקטן ביותר), 2 ו-3 (הגדול ביותר). היתדות הן שמאל (L), מרכז (C), ימין (R). נתחיל עם כל הדיסקים על L, המטרה היא R.
- הזז דיסק 1 מ-L ל-R
- הזז דיסק 2 מ-L ל-C
- הזז דיסק 1 מ-R ל-C
- הזז דיסק 3 מ-L ל-R
- הזז דיסק 1 מ-C ל-L
- הזז דיסק 2 מ-C ל-R
- הזז דיסק 1 מ-L ל-R
שבעה מהלכים. הפאזל נפתר. ברמה זו אפשר לשמור את כל הרצף בראש ולעבוד עליו די מהר. רוב האנשים מבינים זאת תוך כמה ניסיונות אפילו בלי לדעת את האלגוריתם.
פתרון 4 דיסקים (15 מהלכים)
הוסיפו דיסק אחד והרצף מוכפל בתוספת אחד - 15 מהלכים בסך הכל. ברמה זו עליכם ליישם את האסטרטגיה הרקורסיבית בכוונה תחילה. ניסיון לפתור בכוח על ידי תחושה מתחיל להתמוטט. אתם תתבלבלו סביב מהלכים 7-10 אם אתם לא חושבים באופן רקורסיבי.
הגישה: הזיזו את 3 הדיסקים העליונים ליתד המרכזי באמצעות היתד הימני כעזר (זהו רצף 7 המהלכים לעיל, מותאם לתוויות יתדות שונות). הזיזו את הדיסק הגדול ביותר ליתד הימני. הזיזו את ערימת 3 הדיסקים מהמרכז לימין באמצעות השמאלי כעזר (עוד 7 מהלכים). זה 7 + 1 + 7 = 15 מהלכים.
פתרון 7 דיסקים (127 מהלכים)
זה המקום שבו סבלנות הופכת לדרישה אמיתית. 127 מהלכים. אם תעשו מהלך אחד שגוי, כנראה שלא תשימו לב מיד - ועד שדבר מה ייראה לכם שגוי, אתם כבר 20 מהלכים עמוקים בענף רע. מאוד מעצבן.
הגישה האמינה היחידה היא להתמסר לחלוטין לאסטרטגיה הרקורסיבית. אל תנסו לתכנן את כל העניין בראשכם. פשוט התמקדו בבעיית המשנה הנוכחית: מהו הדיסק הגדול ביותר שאני צריך להזיז כרגע, ולאן אני צריך לשים אותו? כל השאר הוא רק פינוי הדרך למהלך הזה.
פותרים מנוסים מפתחים תחושה של קצב – דיסק 1 זז כל תור שני, דיסק 2 זז כל תור רביעי, דיסק 3 כל תור שמיני, וכן הלאה. ברגע שאתם מפנימים את התבנית הזו, הפתרון מתחיל להרגיש כמעט מדיטטיבי.
אם אתם מוצאים ש-7 דיסקים קשים מדי בהתחלה, התחילו עם 5 (31 מהלכים) ובנו את עצמכם. התבנית שתלמדו ב-5 דיסקים עוברת ישירות ל-7.
קושי מגדל האנוי לפי ספירת דיסקים: איזו גרסה מתאימה לכם?
זהו מידע שימושי באמת שכמעט אף אחד לא מכסה היטב. ספירת הדיסקים חשובה מאוד בעת בחירת גרסה לקנייה או להמלצה.
- 3 דיסקים (7 מהלכים): הטוב ביותר לילדים קטנים (גילאי 5-8) ולמתחילים מוחלטים. היכרות מהנה, אך רוב המבוגרים יפתרו אותה תוך מספר דקות. נהדר לכיתות או כפאזל התחלתי.
- 4 דיסקים (15 מהלכים): מתאים לילדים בגילאי 8-12. מבוגרים שחדשים בחידות היגיון עשויים להקדיש 15-20 דקות לזה לפני שהם מבינים את זה בצורה נקייה. עדיין בצד הקל עבור חובבי חידות.
- 5 דיסקים (31 מהלכים): נקודת המוצא האופטימלית לחובבי פאזלים מזדמנים ולילדים גדולים יותר. דורש ריכוז אמיתי. לוקח לרוב המבוגרים ניסיון רציני אחד או שניים. זו לרוב הכמות המינימלית שהייתי ממליץ עליה למבוגר שבאמת רוצה אתגר.
- 7 דיסקים (127 מהלכים): האתגר הקלאסי למבוגרים ולפותרים רציניים. דורש סבלנות, אסטרטגיה וריכוז מספיק כדי לקיים 127 מהלכים ללא טעות. מספק מאוד לפתור בצורה נקייה.
- 8 דיסקים (255 מהלכים): למשתמשים מסורים שרוצים השקעת זמן משמעותית. כאן פועלים פותרי מהירות תחרותיים.
- 10+ דיסקים: תחום חידושים. הפאזל הפיזי הופך גדול ומסורבל, והפתרון הוא יותר תרגיל סיבולת מאשר אתגר פאזל. חלק מהאספנים מעריכים אותם לתצוגה.
המלצתי הכנה לרוב המבוגרים: קנו גרסה של 7 דיסקים. זו הגודל המסורתי מסיבה טובה. מספיק קשה כדי להרגיש כמו הישג אמיתי, מספיק נגיש כדי שבאמת תסיימו אותו. אם אתם קונים לילד בן 10 או למישהו שמתחיל בפעם הראשונה עם פאזל, 5 דיסקים זו הבחירה הנכונה.
אם אתם כבר עמוקים בחידות קשות ומחפשים משהו שיבחן אתכם באמת, שדכו לו מספר דיסקים גדול יותר או חפשו חידות תנועה רציפות הבנויות על אותו היגיון בדרכים מורכבות יותר.
איזה מגדל האנוי כדאי לכם לקנות?
ערכות מגדל האנוי מגיעות מעץ, מתכת ופלסטיק - והאמת היא שחומר גלם חשוב פחות ממה שרוב מדריכי הקנייה מציעים. מה שבאמת הופך מגדל האנוי לטוב הוא ספירת הדיסקים, כמה חלק הדיסקים נעים, והאם הדבר הזה ייאסף או ייגמר במגירה.
הגרסה שהייתי מצביע עליה לרוב האנשים היא פאזל מגדל האנוי למטיילים כאן ב-Greg Puzzles. הנה למה.
הוא מגיע עם 7 דיסקים – ספירת האתגר הקלאסית, 127 מהלכים, הגרסה שאנשים מתכוונים אליה כשהם אומרים שפתרו את מגדל האנוי. המוטות ניתקים לחלוטין, כך שהוא מתקפל שטוח לנסיעה או נשמר מבלי לתפוס מדף שלם. פלטת הצבעים היא טורקיז ושיש – גוונים רגועים בכוונה שנועדו להפוך את הפאזל למרגיע מבחינה ויזואלית, מה שנשמע כמו דבר קטן עד שאתם 60 מהלכים לתוך פתרון ורעש ויזואלי של סט פלסטיק זול ובהיר מתחיל לפעול נגדכם. צבעים אלה נבחרו מתוך מחשבה על חווית הפתרון.
הוא קומפקטי (150 x 52 x 42 מ"מ), בעל פרופורציות טובות ובמחיר סביר. בשביל מה שהוא, זו בחירה קלה.
אם אתם קונים לילד, קנו את הסט הזה ותתחילו אותם עם 3 או 5 דיסקים – פשוט השאירו את הדיסקים הנוספים בצד וטפסו למעלה. אם אתם מבוגרים הקונים לעצמכם או כמתנה למבוגר אחר, 7 דיסקים זו המטרה הנכונה והגרסה הזו מביאה אתכם לשם בצורה נקייה. אם אתם אספנים שכבר יש להם גרסה מעץ ורוצים משהו שמתאים לנסיעות ושלא נראה כמו צעצוע, פלטת הטורקיז והשיש הופכת אותו ראוי למדף ומרגיע.
הערה על ספירת דיסקים בקנייה
ערכות רבות כוללות 7 או 8 דיסקים ומאפשרות לכם להתעלם מהקטנים ביותר בהתחלה. גמישות זו שימושית באמת - התחילו מ-5 דיסקים, עלו ל-7 כשתהיו מוכנים. כמתנה, טווח זה מכסה מגוון רחב של גילאים ורמות מיומנות מבלי שתצטרכו לנחש איזו גרסה לקנות.
אם מישהו אוהב את מגדל האנוי, ההיגיון שהופך אותו למספק מופיע בכל משפחה של פאזלים. עיינו בחידות מוח ב-Greg Puzzles כדי לראות מה מתאים באופן טבעי לצידו.
שאלות נפוצות: חוקים, שיאים, והיכן לקנות את מגדל האנוי
מהם חוקי מגדל האנוי?
שלושה כללים: התחילו עם כל הדיסקים ערוכים על יתד אחד לפי הסדר מהגדול ביותר (למטה) לקטן ביותר (למעלה). העבירו את הערימה כולה ליתד אחר. אתם יכולים להזיז רק דיסק אחד בכל פעם, ואסור לכם אף פעם להניח דיסק גדול יותר על גבי דיסק קטן יותר. יתד שלישי זמין כנקודת אחסון זמנית בכל עת.
מהו המספר המינימלי של מהלכים לפתור את מגדל האנוי?
מספר המהלכים המינימלי הוא 2 בחזקת n פחות 1, כאשר n הוא מספר הדיסקים. עבור 3 דיסקים זה 7 מהלכים. עבור 7 דיסקים זה 127 מהלכים. עבור גרסת 64 הדיסקים האגדית זה ייקח למעלה מ-18 קווינטיליון מהלכים - בערך 585 מיליארד שנים במהירות מהלך אחד לשנייה.
האם מגדל האנוי נפתר באותה צורה בכל פעם?
האסטרטגיה האופטימלית היא תמיד אותו אלגוריתם רקורסיבי: העברת n-1 הדיסקים העליונים ליתד העזר, העברת הדיסק הגדול ביותר ליעד, ולאחר מכן העברת ערימת n-1 הדיסקים ליעד. רצף המהלכים הספציפי הייחודי לכל מספר דיסקים אך תמיד עוקב אחר מבנה זה. אין קיצור דרך – כל סטייה מוסיפה מהלכים נוספים.
מהו שיא העולם של מגדל האנוי?
שיאי מהירות עבור מגדל האנוי נרשמים עבור מספר דיסקים שונים. עבור גרסת 7 הדיסקים הסטנדרטית, פותרי תחרות משלימים את הפאזל בתוך פחות משתי דקות. השיא המדויק משתנה ככל שפותרי מהירות תחרותיים משתפרים. המיקוד בפתרון מהיר הוא גם דיוק (אין מהלכים לא חוקיים) וגם זמן - ביצוע מהלך לא חוקי בדרך כלל אומר להתחיל מחדש.
באיזה גיל מתאים מגדל האנוי?
גרסת 3 דיסקים מתאימה היטב לילדים קטנים מגיל 5 או 6 כהקדמה להיגיון עוקב. גרסת 5 דיסקים מתאימה לגילאי 10 ומעלה. אתגר 7 הדיסקים המלא מיועד למבוגרים ולבני נוער מבוגרים יותר. אין באמת מגבלת גיל עליונה - הפאזל נמצא בשימוש נרחב בהקשרים חינוכיים וקוגניטיביים בכל הגילאים המבוגרים.
כיצד מגדל האנוי קשור למדעי המחשב?
מגדל האנוי הוא דוגמת הוראה קלאסית לרקורסיה – טכניקת תכנות שבה פונקציה קוראת לעצמה כדי לפתור גרסאות קטנות יותר של אותה בעיה. האלגוריתם הרקורסיבי שפותר את מגדל האנוי מתאים כמעט בצורה מושלמת לפונקציה רקורסיבית בקוד, מה שהופך אותו לאחת הדוגמאות הנפוצות ביותר בקורסים למדעי המחשב למתחילים ברחבי העולם. יש לו גם קשרים ישירים למספרים בינאריים וקוד גריי במתמטיקה.
מגדל האנוי קיים למעלה מ-140 שנה והוא עדיין מעניין באמת. זו לא מקריות. המתמטיקה אמיתית, ההיגיון אלגנטי, והמעשה הפיזי של פתרון על סט איכותי מספק בצורה שגרסאות דיגיטליות טהורות אף פעם לא מצליחות לתפוס. אם מעולם לא פתרתם אותו נקי ב-7 דיסקים, שווה להכניס את זה לרשימה שלכם.
ואם אתם נהנים מההיגיון ומהאתגר של תנועה עוקבת שמגדל האנוי מציע, יש עולם שלם של פאזלים הבנויים על עקרונות דומים. עיינו באוסף המלא של חידות מכניות ב-Greg Puzzles כדי למצוא מה מגיע לאחר מכן - בין אם אתם מחפשים משהו מאתגר עוד יותר, משהו למתנה, או סתם משהו חדש להוסיף למדף.
אם אתם מוכנים לנסות את זה - פאזל מגדל האנוי למטיילים ב-Greg Puzzles היא הגרסה שהייתי ממליץ עליה. שבעה דיסקים, מוטות נשלפים, ופלטת צבעים מרגיעה של טורקיז ושיש, בנויה לחווית הפתרון, לא רק למדף. קנו אותו כאן.