הצגת המקור של הדף "מגדלי האנוי"

[[קובץ:Tower of Hanoi.jpeg|שמאל|ממוזער|250px|משחק מגדלי האנוי עשוי [[עץ לבוד]]]]
'''מגדלי האנוי''' או '''מגדלי הבראהמינים''' הוא [[משחק]]-[[חידה]] לשחקן בודד, הנחשב לאחד ה[[שעשועי מתמטיקה|משחקים המתמטיים]] הידועים ביותר.

המשחק הומצא על ידי המתמטיקאי ה[[צרפתי]] [[אדואר לוקאס]] בשנת [[1883]], ותואר בשנת 1892 בספר "Mathematical Recreations and Essays".{{הערה|כיוון=ימין|ראו W. W. Rouse Ball, [https://www.gutenberg.org/files/26839/26839-pdf.pdf Mathematical Recreations and Essays] - מהדורת 1905 של הספר, עמ' 91–93}} לוקאס שיווק את המשחק בתוספת [[סיפור עם|אגדה]] על [[מקדש]] [[ברהמה|בראהמי]] שבו הכהנים עוסקים בהעברת מגדל בן 64 דיסקיות. על פי האגדה, כאשר הכהנים יסיימו את עבודתם, יגיע סוף העולם.

נוסף על היותו משחק ילדים פופולרי, משמש המשחק כאמצעי לימוד והדגמה של הוכחות ב[[אינדוקציה מתמטית|אינדוקציה]], עקרון ה[[רקורסיה]], [[ניתוח אלגוריתמים]] ומושגים בסיסיים אחרים ב[[קומבינטוריקה]] וב[[מדעי המחשב]].{{הערה|כיוון=ימין|דוגמאות:
* [[דוד הראל]], '''אלגוריתמיקה: יסודות מדעי המחשב''', [[האוניברסיטה הפתוחה]], 1994, עמ' 113–117.
* [[דאגלס הופשטטר|Douglas Hofstadter]], [https://archive.org/details/metamagicalthema0000hofs/page/423/mode/2up Metamagical Themas], Basic Books, pp. 423-430}} על החידה והכללותיה נכתבו במהלך השנים מאות מאמרים.{{הערה|Paul K. Stockmeyer, [http://www.cs.wm.edu/~pkstoc/biblio2.pdf The Tower of Hanoi: A Bibliography], September 12, 2005}}

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

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

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

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

==פתרון החידה ברקורסיה (הפתרון הנסיגתי)==
ההוכחה המופיעה בפסקה הבאה משרטטת גם שיטה לפתרון המשחק - שיטה [[רקורסיה|רקורסיבית]]. כבכל רקורסיה, הפתרון כולל שני מרכיבים עיקריים: [[תנאי עצירה]], שמבטיח שהתהליך יסתיים בסופו של דבר, ועיקרון שמבטיח שאם תנאי העצירה טרם הושג, הפתרון יופעל מחדש על בעיה קטנה יותר.{{הערה|{{JSTOR|Paul Cull and E. F. Ecklund, Jr.|Towers of Hanoi and Analysis of Algorithms|2322448|[[American Mathematical Monthly]]|Vol. 92, No. 6, June-July 1985, pp. 407-420}}}}

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

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

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

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

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

דוגמה לפתרון רקורסיבי ב[[שפת תכנות|שפת התכנות]] [[פייתון]]:
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

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

אם נסמן את מספר הצעדים הדרושים להעביר מגדל בעל n דיסקיות ב-<math>\ H(n)</math> אזי מכיוון שהפתרון מורכב משלושה שלבים - העברת מגדל בעל n-1 דיסקיות, העברת הדיסקית התחתונה, ושוב העברת מגדל בעל n-1 דיסקיות, אזי מתקבלת [[נוסחת נסיגה|נוסחת הנסיגה]] הבאה:
<math display="block">\ H(n)=2\times H(n-1)+1</math>
מכיוון ש-<math>\ H(1)=1</math> (לוקח מהלך אחד להעביר מגדל בעל דיסקית אחת), אזי ניתן להשתמש בנוסחאת הנסיגה בשביל לחשב את הסדרה: <math>\ H(n)=1, 3, 7, 15, 31, ...</math>. סדרה זאת נקראת [[מספר מרסן|מספרי מרסן]], והיא כוללת מספרים השווים ל[[חזקה של 2]] פחות אחת, כלומר <math>\ H(n)=2^n-1</math>. את השוויון האחרון ניתן שוב להוכיח באמצעות אינדוקציה שכן:
<math display="block">H(n+1)=2\times H(n)+1=2\times(2^n-1)+1=2^{n+1}-1</math>
מכאן ניתן לפתור את החידה ב-<math>\ 2^n-1</math> צעדים.{{הערה|{{JSTOR|Sheldon S. Myers|An Application of Mathematical Induction to the Tower of Hanoi Puzzle|27954127|The Mathematics Teacher|Vol. 45, No. 7, November 1952, pp. 522-523}}}} כאמור לעיל, פתרון זה הוא גם היעיל ביותר - לא ניתן לפתור את החידה במספר קטן יותר של צעדים. במונחים של מדעי המחשב, מספר ההעברות המינימלי להעברת n דיסקיות הוא <math>\ 2^n - 1 </math>, כלומר הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה, ולכן זהו [[אלגוריתם]] בעל [[סיבוכיות זמן]] מעריכית <math>\ O(2^n)</math> - לבעיה אין פתרון "[[חישוב יעיל|יעיל]]".

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

==הפתרון האיטרטיבי (הלולאתי)==
[[קובץ:Iterative algorithm solving a 6 disks Tower of Hanoi.gif|ממוזער|אנימציה של פתרון איטרטיבי למגדל בן 6 דיסקיות]]
הפתרון הרקורסיבי מבוסס על רעיון טבעי, אך קשה מאוד לביצוע באמצעות חישוב אנושי. ישנה שיטה נוספת, המובילה לאותו רצף של פעולות כמו הפתרון הרקורסיבי, אך קלה לחישוב אנושי. השיטה מתבצעת באופן הבא:
#במהלכים אי זוגיים: העבר את הדיסקית הקטנה ביותר למוט הבא, עם [[כיוון השעון]] אם מספר הדיסקיות הכולל זוגי ונגד כיוון השעון אם מספר הדיסקיות הכולל אי-זוגי (אחרת המגדל יופיע בסוף התהליך בעמוד השני ולא בשלישי כרצוי).
#במהלכים זוגיים: בצע את ההעברה היחידה האפשרית שאינה כוללת את הדיסקית הקטנה ביותר.
בפעם הראשונה שבה לא יהיה ניתן לבצע את צעד 2, יהיה זה סימן שהמשחק נפתר. נשים לב שהפעולה בצעד 2 [[מוגדר היטב|מוגדרת היטב]]: ההעברה המתוארת בו לא יכולה להיות העברה של דיסקית אל המוט שעליו נמצאת הדיסקית הקטנה ביותר, שכן לא ניתן לשים שום דיסקית על הדיסקית הקטנה ביותר, ולכן ההעברה חייבת להיות בין שני המוטות האחרים. אם אחד מהם ריק, ההעברה היחידה האפשרית היא מהמוט עם הדיסקיות למוט הריק. אם על שניהם יש דיסקיות, אז אחת הדיסקיות גדולה מהשנייה, ולא ניתן להעביר אותה למוט השני. בכל מקרה, תמיד יש לכל היותר העברה אחת אפשרית שאינה כוללת את הדיסקית הקטנה ביותר.

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

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

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

==ייצוג גרפי של הפתרון==
את כל הצעדים החוקיים לפתרון חידת מגדלי האנוי ניתן לייצג ב[[גרף בלתי מכוון]], שבו הצמתים מייצגים פיזור של הדיסקיות והקשתות מייצגות צעדים.{{הערה|כיוון=ימין|הצגה ראשונה של גרף כזה ניתנה במאמר{{ש}}{{משמאל לימין|{{JSTOR|R. S. Scorer, P. M. Grundy and C. A. B. Smith|Some Binary Games|3606393|The Mathematical Gazette|Vol. 28, No. 280, July 1944, pp. 96-103}}}}}}

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

[[קובץ:tower_of_hanoi_graph.svg|lang=en-simple|200px|מרכז]]

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

[[קובץ:tower_of_hanoi_graph.svg|lang=tw|300px|מרכז]]

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

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

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

[[קובץ:tower_of_hanoi_graph.svg|lang=en|500px|מרכז]]

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

[[קובץ:Sierpinski deep.svg|ממוזער|250px|שמאל|[[משולש שרפינסקי]] שמקביל לגרף של 7 דיסקיות]]
באופן כללי, חידה של <math>\ n</math> דיסקיות מיוצגת על ידי גרף שבו <math>3^n</math> צמתים. לכל צומת מחוברות שלוש קשתות, מלבד הצמתים שבקודקודי המשולש הגדול, שלהן מחוברות רק שתי קשתות. הגרף עבור n + 1 דיסקיות נוצר באמצעות לקיחת שלושה עותקים של הגרף ל-n דיסקיות וחיבורם זה לזה באמצעות שלוש קשתות המחברות את קודקודי המשולשים, המייצגות את שלוש אפשרויות ההעברה של הדיסקית הגדולה ביותר. בגרף שנוצר יש <math>3^{n+1}</math> צמתים.

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

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

[[קובץ:tower_of_hanoi_graph.svg|lang=pa|500px|מרכז]]

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

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

[[קובץ:tower_of_hanoi_graph.svg|lang=cy|500px|מרכז]]

הגרפים מלמדים כי:
* מכל פיזור חוקי של דיסקיות יש מסלול יחיד שהוא הקצר ביותר להעברת דיסקיות אלה למגדל יחיד.
* בין כל זוג של פיזורים חוקיים של דיסקיות יש מסלול יחיד או שני מסלולים שהם הקצרים ביותר.
* מכל פיזור חוקי של דיסקיות יש יש מסלול יחיד או שני מסלולים (בלי להגיע פעמיים לאותו צומת) שהם הארוכים ביותר.
* בין כל זוג של פיזורים חוקיים של דיסקיות יש מסלול יחיד או שני מסלולים (בלי להגיע פעמיים לאותו צומת) שהם הארוכים ביותר.
* נסמן ב-''N''<sub>''h''</sub> את מספר המסלולים (בלי להגיע פעמיים לאותו צומת) להעברה של ''h'' דיסקיות ממגדל אחד לאחר, ונקבל:
** ''N''<sub>1</sub> = 2
** ''N''<sub>''h''+1</sub> = (''N''<sub>''h''</sub>)<sup>2</sup> + (''N''<sub>''h''</sub>)<sup>3</sup>
:זה נותן ל-''N''<sub>''h''</sub> את הערכים 2, 12, 1872, 6563711232, ... שהם {{OEIS|A125295}}.

==וריאציות של המשחק==
===הכללה של המשימה===
החידה הבסיסית של מגדלי האנוי דורשת להעביר את הדיסקיות ממגדל אחד למגדל אחר תוך שימוש במגדל עזר. הכללה של משימה זו דורשת פתרון למעבר מסידור חוקי כלשהו, מתוך <math>3^n</math> הסידורים האפשריים של דיסקיות על פני שלושת המגדלים, לסידור חוקי אחר על פני שלושת המגדלים.{{הערה|E Staples, [https://dl.acm.org/doi/abs/10.1145/24658.24666 The tower of Hanoi problem with arbitrary start and end positions], '''ACM SIGACT News''', Volume 18 Issue 3, April 1987, pp. 61–64}} ניתן להראות שמכל סידור חוקי ניתן להגדיר מסלול של <math>3^n</math> צעדים, שעובר על כל אחד מהסידורים האפשריים פעם אחת בדיוק, וחוזר לסידור ההתחלתי. עוד ניתן להראות שניתן לפתור את החידה הבסיסית של מגדלי האנוי בכל מספר של <math>\ m</math> צעדים, כאשר <math>2^n-1 \le m \le 3^n-1</math>.{{הערה|{{JSTOR|Dejan Živković|Hamiltonianicity of the Towers of Hanoi problem|43660745|Publikacije Elektrotehničkog fakulteta. Serija Matematika|No. 17, 2006, pp. 31-37}}}}

===הכללה של מספר המגדלים===
בחידה הבסיסית של מגדלי האנוי ישנם שלושה מגדלים. בשנת 1907 החידונאי [[הנרי ארנסט דודני]] הציג בספרו "The Canterbury Puzzles" את החידה כאשר בה ארבעה מגדלים, וביקש לדעת מה מספר הצעדים המזערי הנדרש כאשר יש 8, 10 או 21 דיסקיות. דודני כתב שהתשובה היא 33, 49 או 321 צעדים, בהתאמה, אך לא נתן הוכחה לכך. הוא הוסיף נוסחה למספר הצעדים הנחוץ כאשר מספר הדיסקיות הוא [[מספר משולשי]].{{הערה|Henry Ernest Dudeney, [https://www.gutenberg.org/files/27635/27635-h/27635-h.htm#p1 The Canterbury Puzzles], 1907, הפרק The Reve's Puzzle, ב[[פרויקט גוטנברג]]}}

בשנת 1939 פרסם B. M. Stewart הכללה של החידה למספר כלשהו של מגדלים,{{הערה|{{JSTOR|B. M. Stewart|Advanced Problem 3918|2302907|American Mathematical Monthly|Vol. 46, No. 6, June-July 1939, p. 363}}}} והפתרונות פורסמו בשנת 1941, ללא הוכחה שהם הפתרונות האופטימליים.{{הערה|{{JSTOR|J. S. Frame, B. M. Stewart|Solution to Advanced Problem 3918|2304268|American Mathematical Monthly|Vol. 48, No. 3, March 1941, pp. 216-219}}}}{{הערה|{{cite journal |first=Paul |last=Stockmeyer |title=Variations on the Four-Post Tower of Hanoi Puzzle |journal=Congressus Numerantium |volume=102 |year=1994 |pages=3–12 |url=http://www.cs.wm.edu/~pkstoc/boca.ps |format=Postscript}}{{ש}}{{JSTOR|Paul Isihara and Doeke Buursma|Multi-Peg Tower of Hanoi|10.4169/college.math.j.44.2.110|The College Mathematics Journal|Vol. 44, No. 2, March 2013, pp. 110-116}}}} בשנת 2014 ניתן פתרון אופטימלי לחידה עם ארבעה מגדלים.{{הערה|{{cite journal |first= T.|last=Bousch|title=La quatrieme tour de Hanoi|journal=Bull. Belg. Math. Soc. Simon Stevin|volume= 21|year=2014|pages=895–912 |doi=10.36045/bbms/1420071861|url= https://pdfs.semanticscholar.org/fb87/0a772baf96a2e11901122a2b04c3dd25596d.pdf|archive-url= https://web.archive.org/web/20170921001150/https://pdfs.semanticscholar.org/fb87/0a772baf96a2e11901122a2b04c3dd25596d.pdf|url-status= dead|archive-date= 2017-09-21}}}}

===מגדלי האנוי בשני צבעים===
[[קובץ:BTOHIC.jpg|ממוזער|מצב התחלתי של מגדלי האנוי בשני צבעים (n=4)]]
[[קובץ:BTOHFC.jpg|ממוזער|מצב הסיום של מגדלי האנוי בשני צבעים (n=4)]]
ביולי 1988 הוצגו באליפות צרפת השנייה למשחקים מתמטיים ולוגיים וריאציות אחדות לחידת מגדלי האנוי, שבהן יש שני סטים של דיסקיות, האחד שחור והשני לבן, כך שבכל גודל של דיסקיות יש אחת שחורה ואחת לבנה.{{הערה|{{Cite journal|url=http://rmm.ludus-opuscula.org/PDF_Files/Chaugule_BicolorHanoi_37_48(4_2015)_low.pdf|journal=Recreational Mathematics Magazine|issue= 4|pages=37–48|title=A Recursive Solution to Bicolor Towers of Hanoi Problem|date=2015|issn=2182-1976|author=Prasad Vithal Chaugule}}}}

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

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

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

===מגדלי האנוי מגנטיים===
[[קובץ:Start position three-disk JPEG 110924.jpg|ממוזער|250px|מצב התחלתי של מגדלי האנוי מגנטיים]]
[[קובץ:End position three-disk JPEG 110924.jpg|ממוזער|250px|מצב סיום של מגדלי האנוי מגנטיים]]
וריאציה נוספת, מגדלי האנוי מגנטיים {{אנ|Magnetic Tower of Hanoi}} פותחה על ידי ד"ר אורי לוי מ[[מכון ויצמן למדע]].{{הערה|כיוון=ימין|[https://davidson-web2.weizmann.ac.il/davidson1/davidson_online/mtoh/MTOH.html מגדלי האנוי מגנטיים], באתר של [[מכון דוידסון לחינוך מדעי]]}}{{הערה|Uri Levy, [https://arxiv.org/abs/1003.0225 The Magnetic Tower of Hanoi], [[arXiv]], 9 March 2010}} בווריאציה זו לכל דיסקית יש שני צבעים, למשל כחול ואדום (או שני קטבים מגנטיים). במצב ההתחלתי הדיסקיות מונחות זו על זו באחד מהמגדלים, כך שאין מגע בין שני צבעים זהים (כלומר צדה הכחול של דיסקית מופנה אל צדה האדום של הדיסקית שמתחתיה). המשימה היא להעביר את כל הדיסקיות ממגדל זה אל אחד משני המגדלים האחרים, לפי הכללים הבאים:
* מותר להזיז רק דיסקית אחת בכל פעם - מראש מגדל אחד לראש מגדל אחר.
* אסור להניח דיסקית על דיסקית שקטנה ממנה.
* בעת הרמת דיסקית היא מתהפכת, כך שצבעה העליון וצבעה התחתון מתחלפים.
* אסור לאפשר מגע בין שני צבעים זהים.
המגבלה שנוספה בווריאציה זו מגדילה את מספר הצעדים המזערי הנחוץ לפתרון בהשוואה לחידה הבסיסית. במגדל של שלוש דיסקיות נחוצים 11 צעדים (לעומת 7 בגרסה הבסיסית) ובמגדל של ארבע דיסקיות נחוצים 30 צעדים (לעומת 15 בגרסה הבסיסית).

==ראו גם==
*[[קלונדייק (סוליטר)|קלונדייק]] - משחק הפועל על אותו עיקרון מתמטי.
*[[בעיית סידור הפנקייקים של גודמן]] - בעיה מתמטית העוסקת בסידור ערימת פנקייקים כך שהפנקייק הגדול ביותר יהיה למטה והקטן ביותר למעלה באמצעות היפוך החלק העליון שלה מספר פעמים. בניגוד למגדלי האנוי הפנקייקים נמצאים כל הזמן באותה ערימה ואין הגבלה על כך שפנקייק קטן יהיה מתחת פנקייק גדול ממנו תוך כדי הסידור.

==לקריאה נוספת==
<div class="mw-content-ltr">
* Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, '''The Tower of Hanoi – Myths and Maths''', Birkhäuser, 2013; 2nd edition, 2018. {{אנ|The Tower of Hanoi – Myths and Maths}}
</div>

==קישורים חיצוניים==
{{ויקישיתוף בשורה|שם=Category:Tower of Hanoi|תצוגה=מגדלי האנוי}}
* {{אלף אפס|ישראל אהרוני|ממגדל הנוי למשולש פסקל|26}}
* {{אלף אפס||מגדלי האנוי לניסוי עצמי|6|game}} (דורש תמיכה ב־[[Java]])
* {{לא מדויק|2007/09/07/towers_of_hanoi/|המגדל הלוהט}}
* {{דוידסון|ארז גרטי|מגדלי האנוי מגנטיים|tikshuv/math_and_comp/מגדלי-האנוי-מגנטיים|5 נובמבר 2011}}
* {{אאוריקה|מהם מגדלי האנוי?|42266}}
* {{MathWorld}}
* {{בריטניקה}}
<div class="mw-content-ltr">
* {{JSTOR|David G. Poole|The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)|2690991|Mathematics Magazine|Vol. 67, No. 5, December 1994, pp. 323-344}}
* {{JSTOR|Danielle Arett and Suzanne Dorée|Coloring and Counting on the Tower of Hanoi Graphs|10.4169/002557010x494841|Mathematics Magazine|Vol. 83, No. 3, June 2010, pp. 200-209}}
</div>

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{ערך מומלץ}}
{{בקרת זהויות}}
[[קטגוריה:חידות מתמטיות]]
[[קטגוריה:רקורסיה]]
[[קטגוריה:משחקי חשיבה]]
[[קטגוריה:הוכחות]]