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

המשחק הומצא על ידי המתמטיקאי הצרפתי אדואר לוקאס בשנת 1883, ותואר בשנת 1892 בספר "Mathematical Recreations and Essays".^[1] לוקאס שיווק את המשחק בתוספת אגדה על מקדש בראהמי שבו הכהנים עוסקים בהעברת מגדל בן 64 דיסקיות. על פי האגדה, כאשר הכהנים יסיימו את עבודתם, יגיע סוף העולם.

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

המשחק כולל:

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

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

• מותר להזיז רק דיסקית אחת בכל פעם – מראש מוט אחד לראש מוט אחר (אפשר להזיז רק את הדסקית העליונה בכל עמוד).
• אסור להניח דיסקית אחת על דיסקית שקטנה ממנה.

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

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

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

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

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

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

בצורה פורמלית, האלגוריתם יוגדר כך:

העבר-דיסקיות (קלט: מספר-דיסקיות, מוט-מקור, מוט-ביניים, מוט-יעד)

1. אם מספר-דיסקיות=1 העבר את הדיסקית ממוט-מקור למוט-יעד.
2. אחרת, בצע:
   1. העבר-דיסקיות (מספר-דיסקיות פחות אחת, מוט-מקור, מוט-יעד, מוט-ביניים): מעביר את כל הדיסקיות פרט לתחתונה למוט הביניים.
   2. העבר-דיסקיות (1, מוט-מקור, מוט-ביניים, מוט-יעד) : מעביר את הדיסקית התחתונה למוט היעד.
   3. העבר-דיסקיות (מספר דיסקיות פחות אחת, מוט-ביניים, מוט-מקור, מוט-יעד): מעביר את כל הדיסקיות שעל מוט הביניים למוט היעד.

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

דוגמה לפתרון רקורסיבי בשפת התכנות פייתון:

A = [3, 2, 1]
B = []
C = []

def move(n, source, target, auxiliary):
    if n > 0:
        # Move n - 1 disks from source to auxiliary, so they are out of the way
        move(n - 1, source, auxiliary, target)

        # Move the nth disk from source to target
        target.append(source.pop())

        # Display our progress
        print(A, B, C, '##############', sep='\n')

        # Move the n - 1 disks that we left on auxiliary onto target
        move(n - 1, auxiliary, target, source)

# Initiate call from source A to target C with auxiliary B
move(3, A, C, B)

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

אם נסמן את מספר הצעדים הדרושים להעביר מגדל בעל n דיסקיות ב-${\displaystyle \ H(n)}$ אזי מכיוון שהפתרון מורכב משלושה שלבים - העברת מגדל בעל n-1 דיסקיות, העברת הדיסקית התחתונה, ושוב העברת מגדל בעל n-1 דיסקיות, אזי מתקבלת נוסחת הנסיגה הבאה: $${\displaystyle \ H(n)=2\times H(n-1)+1}$$ מכיוון ש-${\displaystyle \ H(1)=1}$ (לוקח מהלך אחד להעביר מגדל בעל דיסקית אחת), אזי ניתן להשתמש בנוסחאת הנסיגה בשביל לחשב את הסדרה: ${\displaystyle \ H(n)=1,3,7,15,31,...}$. סדרה זאת נקראת מספרי מרסן, והיא כוללת מספרים השווים לחזקה של 2 פחות אחת, כלומר ${\displaystyle \ H(n)=2^{n}-1}$. את השוויון האחרון ניתן שוב להוכיח באמצעות אינדוקציה שכן: $${\displaystyle H(n+1)=2\times H(n)+1=2\times (2^{n}-1)+1=2^{n+1}-1}$$ מכאן ניתן לפתור את החידה ב-${\displaystyle \ 2^{n}-1}$ צעדים.^[5] כאמור לעיל, פתרון זה הוא גם היעיל ביותר - לא ניתן לפתור את החידה במספר קטן יותר של צעדים. במונחים של מדעי המחשב, מספר ההעברות המינימלי להעברת n דיסקיות הוא ${\displaystyle \ 2^{n}-1}$, כלומר הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה, ולכן זהו אלגוריתם בעל סיבוכיות זמן מעריכית ${\displaystyle \ O(2^{n})}$ - לבעיה אין פתרון "יעיל".

בהקשר של האגדה של לוקאס, מספר הצעדים שלוקח להעביר מגדל בעל 64 דיסקיות הוא ${\displaystyle \ 2^{64}-1=18,446,744,073,709,551,615}$, ומכאן שאפילו אם הנזירים יכולים להעביר דיסקיות בקצב של אחת לשנייה (מבלי להתבלבל), הזמן שיידרש להם להעביר את כל המגדל הוא כ-580 מיליארד שנים - פי 42 מגילו המוערך של היקום.

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

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

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

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

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

אם נכתוב את סדרת המספרים הטבעיים בבסיס בינארי: 1, 10, 11, 100, 101, 110, ... אזי הספרה הראשונה שאיננה 0 מייצגת את מספר הדיסקית (כשהדיסקיות ממוספרות מהקטנה לגדולה) שיש להזיז באותו מהלך. לדוגמה במהלך הרביעי יש להזיז את הדיסקית השלישית, מכיוון שבייצוג הבינארי של המספר 4 שהוא 100, הספרה הראשונה שאיננה 0 היא הספרה השלישית.

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

למגדל שבו דיסקית אחת בלבד, הגרף הוא משולש, המייצג את שלושת הצעדים האפשריים:

למגדל של שתי דיסקיות הגרף כולל שלושה משולשים, המחוברים ביניהם ליצירת משולש גדול יותר:

הצמתים שבקודקודי המשולש הגדול מייצגים מצבים שבהם כל הדיסקיות נמצאות על אותו מגדל.

ליצירת גרף עבור h + 1 דיסקיות יש לקחת את הגרף ל-h דיסקיות ולהחליף בו כל משולש קטן במשולש לשתי דיסקיות.

למגדל של שלוש דיסקיות הגרף הוא:

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

באופן כללי, חידה של ${\displaystyle \ n}$ דיסקיות מיוצגת על ידי גרף שבו ${\displaystyle 3^{n}}$ צמתים. לכל צומת מחוברות שלוש קשתות, מלבד הצמתים שבקודקודי המשולש הגדול, שלהן מחוברות רק שתי קשתות. הגרף עבור n + 1 דיסקיות נוצר באמצעות לקיחת שלושה עותקים של הגרף ל-n דיסקיות וחיבורם זה לזה באמצעות שלוש קשתות המחברות את קודקודי המשולשים, המייצגות את שלוש אפשרויות ההעברה של הדיסקית הגדולה ביותר. בגרף שנוצר יש ${\displaystyle 3^{n+1}}$ צמתים.

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

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

מסלול זה מושג כאשר נמנעים מהעברה ממגדל a ישירות למגדל c.

מעגל המילטוני לגרף של 3 דיסקיות מוצג בגרף הבא:

הגרפים מלמדים כי:

• מכל פיזור חוקי של דיסקיות יש מסלול יחיד שהוא הקצר ביותר להעברת דיסקיות אלה למגדל יחיד.
• בין כל זוג של פיזורים חוקיים של דיסקיות יש מסלול יחיד או שני מסלולים שהם הקצרים ביותר.
• מכל פיזור חוקי של דיסקיות יש יש מסלול יחיד או שני מסלולים (בלי להגיע פעמיים לאותו צומת) שהם הארוכים ביותר.
• בין כל זוג של פיזורים חוקיים של דיסקיות יש מסלול יחיד או שני מסלולים (בלי להגיע פעמיים לאותו צומת) שהם הארוכים ביותר.
• נסמן ב-N_h את מספר המסלולים (בלי להגיע פעמיים לאותו צומת) להעברה של h דיסקיות ממגדל אחד לאחר, ונקבל:
  • N₁ = 2
  • N_h+1 = (N_h)² + (N_h)³

זה נותן ל-N_h את הערכים 2, 12, 1872, 6563711232, ... שהם סדרה A125295 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים.

החידה הבסיסית של מגדלי האנוי דורשת להעביר את הדיסקיות ממגדל אחד למגדל אחר תוך שימוש במגדל עזר. הכללה של משימה זו דורשת פתרון למעבר מסידור חוקי כלשהו, מתוך ${\displaystyle 3^{n}}$ הסידורים האפשריים של דיסקיות על פני שלושת המגדלים, לסידור חוקי אחר על פני שלושת המגדלים.^[7] ניתן להראות שמכל סידור חוקי ניתן להגדיר מסלול של ${\displaystyle 3^{n}}$ צעדים, שעובר על כל אחד מהסידורים האפשריים פעם אחת בדיוק, וחוזר לסידור ההתחלתי. עוד ניתן להראות שניתן לפתור את החידה הבסיסית של מגדלי האנוי בכל מספר של ${\displaystyle \ m}$ צעדים, כאשר ${\displaystyle 2^{n}-1\leq m\leq 3^{n}-1}$.^[8]

בחידה הבסיסית של מגדלי האנוי ישנם שלושה מגדלים. בשנת 1907 החידונאי הנרי ארנסט דודני הציג בספרו "The Canterbury Puzzles" את החידה כאשר בה ארבעה מגדלים, וביקש לדעת מה מספר הצעדים המזערי הנדרש כאשר יש 8, 10 או 21 דיסקיות. דודני כתב שהתשובה היא 33, 49 או 321 צעדים, בהתאמה, אך לא נתן הוכחה לכך. הוא הוסיף נוסחה למספר הצעדים הנחוץ כאשר מספר הדיסקיות הוא מספר משולשי.^[9]

בשנת 1939 פרסם B. M. Stewart הכללה של החידה למספר כלשהו של מגדלים,^[10] והפתרונות פורסמו בשנת 1941, ללא הוכחה שהם הפתרונות האופטימליים.^[11][12] בשנת 2014 ניתן פתרון אופטימלי לחידה עם ארבעה מגדלים.^[13]

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

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

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

לחידה זו שתי תת-וריאציות: באחת שתי הדיסקיות הגדולות ביותר מתחלפות ביניהן במקומותיהן, ובאחרת, הקלה יותר, הן נשארות במקומן.

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

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

וריאציה נוספת, מגדלי האנוי מגנטיים (אנ') פותחה על ידי ד"ר אורי לוי ממכון ויצמן למדע.^[15][16] בווריאציה זו לכל דיסקית יש שני צבעים, למשל כחול ואדום (או שני קטבים מגנטיים). במצב ההתחלתי הדיסקיות מונחות זו על זו באחד מהמגדלים, כך שאין מגע בין שני צבעים זהים (כלומר צדה הכחול של דיסקית מופנה אל צדה האדום של הדיסקית שמתחתיה). המשימה היא להעביר את כל הדיסקיות ממגדל זה אל אחד משני המגדלים האחרים, לפי הכללים הבאים:

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

המגבלה שנוספה בווריאציה זו מגדילה את מספר הצעדים המזערי הנחוץ לפתרון בהשוואה לחידה הבסיסית. במגדל של שלוש דיסקיות נחוצים 11 צעדים (לעומת 7 בגרסה הבסיסית) ובמגדל של ארבע דיסקיות נחוצים 30 צעדים (לעומת 15 בגרסה הבסיסית).

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

מדיה וקבצים בנושא מגדלי האנוי בוויקישיתוף

• ישראל אהרוני, ממגדל הנוי למשולש פסקל, באתר "אלף אפס"
• מגדלי האנוי לניסוי עצמי, באתר "אלף אפס" (דורש תמיכה בJava)
• גדי אלכסנדרוביץ', המגדל הלוהט, באתר "לא מדויק", 7 בספטמבר 2007
• ארז גרטי, מגדלי האנוי מגנטיים, באתר של מכון דוידסון לחינוך מדעי, 5 נובמבר 2011
• מהם מגדלי האנוי?, באתר אנציקלופדיה אאוריקה
• מגדלי האנוי, באתר MathWorld (באנגלית)
• topic/Lucas-Puzzle מגדלי האנוי, באתר אנציקלופדיה בריטניקה (באנגלית)

ערך מומלץ