אם נסמן את מספר הצעדים הדרושים להעביר מגדל בעל n דיסקיות ב-formula_1 אזי מכיוון שהפתרון מורכב משלושה שלבים - העברת מגדל בעל n-1 דיסקיות, העברת הדיסקית התחתונה, ושוב העברת מגדל בעל n-1 דיסקיות, אזי מתקבלת נוסחת הנסיגה הבאה:
formula_2
מכיוון ש-formula_3 (לוקח מהלך אחד להעביר מגדל בעל דיסקית אחת), אזי ניתן להשתמש בנוסחאת הנסיגה בשביל לחשב את הסדרה: formula_4. סדרה זאת נקראת מספרי מרסן, והיא כוללת מספרים השווים לחזקה של 2 פחות אחת, כלומר formula_5. את השוויון האחרון ניתן שוב להוכיח באמצעות אינדוקציה שכן:
formula_6
מכאן ניתן לפתור את החידה ב-formula_7 צעדים. כאמור לעיל, פתרון זה הוא גם היעיל ביותר - לא ניתן לפתור את החידה במספר קטן יותר של צעדים. במונחים של מדעי המחשב, מספר ההעברות המינימלי להעברת n דיסקיות הוא formula_8, כלומר הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה, ולכן זהו אלגוריתם בעל סיבוכיות זמן מעריכית formula_9 - לבעיה אין פתרון "יעיל".
בהקשר של האגדה של לוקאס, מספר הצעדים שלוקח להעביר מגדל בעל 64 דיסקיות הוא formula_10, ומכאן שאפילו אם הנזירים יכולים להעביר דיסקיות בקצב של אחת לשנייה (מבלי להתבלבל), הזמן שיידרש להם להעביר את כל המגדל הוא כ-580 מיליארד שנים - פי 42 מגילו המוערך של היקום.
הפתרון האיטרטיבי (הלולאתי).
הפתרון האיטרטיבי מבוסס על רעיון טבעי, אך קשה מאוד לביצוע באמצעות חישוב אנושי. ישנה שיטה נוספת, המובילה לאותו רצף של פעולות כמו הפתרון הרקורסיבי, אך קלה לחישוב אנושי. השיטה מתבצעת באופן הבא:
בפעם הראשונה שבה לא יהיה ניתן לבצע את צעד 2, יהיה זה סימן שהמשחק נפתר. נשים לב שהפעולה בצעד 2 מוגדרת היטב: ההעברה המתוארת בו לא יכולה להיות העברה של דיסקית אל המוט שעליו נמצאת הדיסקית הקטנה ביותר, שכן לא ניתן לשים שום דיסקית על הדיסקית הקטנה ביותר, ולכן ההעברה חייבת להיות בין שני המוטות האחרים. אם אחד מהם ריק, ההעברה היחידה האפשרית היא מהמוט עם הדיסקיות למוט הריק. אם על שניהם יש דיסקיות, אז אחת הדיסקיות גדולה מהשנייה, ולא ניתן להעביר אותה למוט השני. בכל מקרה, תמיד יש לכל היותר העברה אחת אפשרית שאינה כוללת את הדיסקית הקטנה ביותר.
חשוב לשים לב שבפתרון הזה יועברו כל הדיסקיות ממוט אחד לאחר, אבל השאלה לאיזה מוט תלויה במספר הדיסקיות; אם הוא זוגי יש להעביר את הדיסקית למוט הביניים. ואם הוא אי-זוגי, אזי יש להעבירה אל מוט היעד. העניין מתבסס על כך שעל דיסקית המונחת במקום הסידורי יונח "מיני מגדל" (מגדל שלא כולל את כל הדיסקיות) המתבסס עליה, אם יש מספר דיסקיות אי זוגי אז ה"מיני מגדל" יהיה לבסוף מגדל שלם. אך אם מדובר במספר דיסקיות זוגי אז ה"מיני מגדל" יהיה חסר בדיסקית אחת, הגדולה ביותר, והדיסקית הזו תוכל להיות מועברת אל מוט היעד. ובעקבותיה - שאר הדיסקיות.
גישה נוספת להסתכלות על הפתרון האיטרטיבי היא זו: צבע את כל הדיסקיות בשחור ולבן לסירוגין, וגם את ה"רצפה" שמתחת למוטות (שוב, לסירוגין). עכשיו, שחק כרגיל בתוספת חוק אחד: לשמור על הסירוג בצבעים. כלומר, אסור לשים שחור על שחור או לבן על לבן.
פתרון בעזרת מספרים בינאריים.
אם נכתוב את סדרת המספרים הטבעיים בבסיס בינארי: 1, 10, 11, 100, 101, 110, ... אזי הספרה הראשונה שאיננה 0 מייצגת את מספר הדיסקית (כשהדיסקיות ממוספרות מהקטנה לגדולה) שיש להזיז באותו מהלך. לדוגמה במהלך הרביעי יש להזיז את הדיסקית השלישית, מכיוון שבייצוג הבינארי של המספר 4 שהוא 100, הספרה הראשונה שאיננה 0 היא הספרה השלישית.
ייצוג גרפי של הפתרון.
את כל הצעדים החוקיים לפתרון חידת מגדלי האנוי ניתן לייצג בגרף בלתי מכוון, שבו הצמתים מייצגים פיזור של הדיסקיות והקשתות מייצגות צעדים.
למגדל שבו דיסקית אחת בלבד, הגרף הוא משולש, המייצג את שלושת הצעדים האפשריים:
למגדל של שתי דיסקיות הגרף כולל שלושה משולשים, המחוברים ביניהם ליצירת משולש גדול יותר:
הצמתים שבקודקודי המשולש הגדול מייצגים מצבים שבהם כל הדיסקיות נמצאות על אותו מגדל.
ליצירת גרף עבור h + 1 דיסקיות יש לקחת את הגרף ל-h דיסקיות ולהחליף בו כל משולש קטן במשולש לשתי דיסקיות.
למגדל של שלוש דיסקיות הגרף הוא:
הצלעות של המשולש הגדול מייצגות את הדרך הקצרה ביותר להעברת הדיסקיות ממגדל אחד לאחר. הצומת שבמרכז הצלע של המשולש הגדול מייצג העברה של הדיסקית הגדולה ביותר.
באופן כללי, חידה של formula_11 דיסקיות מיוצגת על ידי גרף שבו formula_12 צמתים. לכל צומת מחוברות שלוש קשתות, מלבד הצמתים שבקודקודי המשולש הגדול, שלהן מחוברות רק שתי קשתות. הגרף עבור n + 1 דיסקיות נוצר באמצעות לקיחת שלושה עותקים של הגרף ל-n דיסקיות וחיבורם זה לזה באמצעות שלוש קשתות המחברות את קודקודי המשולשים, המייצגות את שלוש אפשרויות ההעברה של הדיסקית הגדולה ביותר. בגרף שנוצר יש formula_13 צמתים.
הגרף שנוצר בדרך זו, ככל שמוסיפים עוד דיסקיות, הוא משולש שרפינסקי. משולש שרפינסקי הוא פרקטל בצורת משולש, המכיל שלושה עותקים מוקטנים של עצמו, וכל אחד מאלה מכיל שלושה עותקים מוקטנים של עצמו, וכך הלאה. את הקשר בין מגדלי האנוי לבין משולש שרפינסקי קל להבין: נסתכל על משחק בעל n+1 דיסקיות, את הגרף של המשחק ניתן לחלק לשלושה חלקים על פי מיקום הדיסקית הגדולה ביותר. עבור כל אחד מהחלקים הגרף המתאר את המצבים שלו הוא הגרף של המשחק עם n דיסקיות, ולכן כמו במשולש שרפינסקי הגרף מכיל שלושה עותקים מוקטנים של עצמו.
את המסלול הארוך ביותר להשגת הפתרון (בלי להגיע פעמיים לאותו צומת) ניתן להציג באמצעות מחיקת הקשתות המיותרות. דוגמה למסלול כזה במגדל של 3 דיסקיות:
מסלול זה מושג כאשר נמנעים משימוש במגדל c (העברת הדיסקיות היא רק בין המגדלים a ו-b).
מסלול המילטוני לגרף של 3 דיסקיות מוצג בגרף הבא:
הגרפים מלמדים כי:
וריאציות של המשחק.
הכללה של המשימה.
החידה הבסיסית של מגדלי האנוי דורשת להעביר את הדיסקיות ממגדל אחד למגדל אחר תוך שימוש במגדל עזר. הכללה של משימה זו דורשת פתרון למעבר מסידור חוקי כלשהו, מתוך formula_12 הסידורים האפשריים של דיסקיות על פני שלושת המגדלים, לסידור חוקי אחר על פני שלושת המגדלים. ניתן להראות שמכל סידור חוקי ניתן להגדיר מסלול של formula_12 צעדים, שעובר על כל אחד מהסידורים האפשריים פעם אית בדיוק, וחוזר לסידור ההתחלתי. עוד ניתן להראות שניתן לפתור את החידה הבסיסית של מגדלי האנוי בכל מספר של formula_16 צעדים, כאשר formula_17.
הכללה של מספר המגדלים.
בחידה הבסיסית של מגדלי האנוי ישנם שלושה מגדלים. בשנת 1907 החידונאי הנרי ארנסט דודני הציג בספרו "The Canterbury Puzzles" את החידה כאשר בה ארבעה מגדלים, וביקש לדעת מה מספר הצעדים המזערי הנדרש כאשר יש 8, 10 או 21 דיסקיות. דודני כתב שהתשובה היא 33, 49 או 321 צעדים, בהתאמה, אך לא נתן הוכחה לכך. הוא הוסיף נוסחה למספר הצעדים הנחוץ כאשר מספר הדיסקיות הוא מספר משולשי.
בשנת 1939 פרסם B. M. Stewart הכללה של החידה למספר כלשהו של מגדלים, והפתרונות פורסמו בשנת 1941, ללא הוכחה שהם הפתרונות האופטימליים. בשנת 2014 ניתן פתרון אופטימלי לחידה עם ארבעה מגדלים.
מגדלי האנוי בשני צבעים.
ביולי 1988 הוצגו באליפות צרפת השנייה למשחקים מתמטיים ולוגיים וריאציות אחדות לחידת מגדלי האנוי, שבהן יש שני סטים של דיסקיות, האחד שחור והשני לבן, כך שבכל גודל של דיסקיות יש אחת שחורה ואחת לבנה.
חידת הפרדת הצבעים: במצב ההתחלתי הדיסקיות מונחות זו על זו בשני מגדלים, כשצבעי הדיסקיות הם לסירוגין שחור ולבן, בסדר יורד של גודלי הדיסקיות. המטרה היא להפריד את הדיסקיות לשני מגדלים חדגוניים, באמצעות מגדל עזר, תוך שמירה על שני כללים:
לחידה זו שתי תת-וריאציות: באחת שתי הדיסקיות הגדולות ביותר מתחלפות ביניהן במקומותיהן, ובאחרת, הקלה יותר, הן נשארות במקומן.
חידת מיזוג: במצב ההתחלתי הדיסקיות מונחות זו על זו בשני מגדלים, האחד שחור והשני לבן. יש למזג את שני המגדלים למגדל אחד, שבו הדיסקיות מונחות מהגדולה לקטנה, ובכל שתי דיסקיות בנות אותו גודל, הדיסקית הלבנה היא מעל לדיסקית השחורה.
חידת פיצול: במצב ההתחלתי הדיסקיות מונחות זו על זו במגדל אחד, מהגדולה לקטנה, ובכל שתי דיסקיות בנות אותו גודל, הדיסקית הלבנה היא מעל לדיסקית השחורה. יש לפצל את המגדל, באמצעות מגדל עזר, לשני מגדלים חדגוניים, שבהם נשמר הכלל שאין לשים דיסקית מעל דיסקית קטנה ממנה.
מגדלי האנוי מגנטיים.
וריאציה נוספת, מגדלי האנוי מגנטיים פותחה על ידי ד"ר אורי לוי ממכון ויצמן למדע. בווריאציה זו לכל דיסקית יש שני צבעים, למשל כחול ואדום (או שני קטבים מגנטיים). במצב ההתחלתי הדיסקיות מונחות זו על זו באחד מהמגדלים, כך שאין מגע בין שני צבעים זהים (כלומר צדה הכחול של דיסקית מופנה אל צדה האדום של הדיסקית שמתחתיה). המשימה היא להעביר את כל הדיסקיות ממגדל זה אל אחד משני המגדלים האחרים, לפי הכללים הבאים:
המגבלה שנוספה בווריאציה זו מגדילה את מספר הצעדים המזערי הנחוץ לפתרון בהשוואה לחידה הבסיסית. במגדל של שלוש דיסקיות נחוצים 11 צעדים (לעומת 7 בגרסה הבסיסית) ובמגדל של ארבע דיסקיות נחוצים 30 צעדים (לעומת 15 בגרסה הבסיסית).
תנא
חיקסוס