מגדלי האנוי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
משחק מגדלי האנוי עשוי עץ לבוד

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

המשחק הומצא על ידי המתמטיקאי הצרפתי אדוארד לוקאס בשנת 1883‏‏[1]. לוקאס שיווק את המשחק בתוספת אגדה על מקדש בראהמי שבו הכהנים עוסקים בהעברת מגדל בן 64 דיסקיות. על פי האגדה, כאשר הכהנים יסיימו את עבודתם, יגיע סוף העולם.

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

חוקי המשחק[עריכת קוד מקור | עריכה]

המשחק כולל:

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

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

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

היתכנות פתרון המשחק - הוכחה באינדוקציה[עריכת קוד מקור | עריכה]

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

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

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

פתרון החידה ברקורסיה (הפתרון הנסיגתי)[עריכת קוד מקור | עריכה]

פתרון לשלוש דיסקיות
פתרון לארבע דיסקיות

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

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

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

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

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

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

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

מספר הצעדים הנחוצים לפתרון[עריכת קוד מקור | עריכה]

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

אם נסמן את מספר הצעדים הדרושים להעביר מגדל בעל n דיסקיות ב-\ H(n) אזי מכיוון שהפתרון מורכב משלושה שלבים - העברת מגדל בעל n-1 דיסקיות, העברת הדיסקית התחתונה, ושוב העברת מגדל בעל n-1 דיסקיות, אזי מתקבלת נוסחת הנסיגה הבאה:

\ H(n)=2\times H(n-1)+1

מכיוון ש-\ H(1)=1 (לוקח מהלך אחד להעביר מגדל בעל דיסקית אחת), אזי ניתן להשתמש בנוסחאת הנסיגה בשביל לחשב את הסדרה: \ H(n)=1, 3, 7, 15, 31, .... סדרה זאת נקראת מספרי מרסן, והיא כוללת מספרים השווים לחזקה של 2 פחות אחת, כלומר \ H(n)=2^n-1. את השוויון האחרון ניתן שוב להוכיח באמצעות אינדוקציה שכן:

H(n+1)=2\times H(n)+1=2\times(2^n-1)+1=2^{n+1}-1

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

בהקשר של האגדה של לוקאס, מספר הצעדים שלוקח להעביר מגדל בעל 64 דיסקיות הינו \ 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 היא הספרה השלישית.

הקשר למשולש שרפינסקי[עריכת קוד מקור | עריכה]

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ‏אם כי ישנן טענות שלפיהם לוקאס גנב את המשחק מהריסון הית', מומחה למשחקי לוח.‏
ערך מומלץ
Article MediumPurple.svg