המגדל הלוהט

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

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

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

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

הנה המחשה גרפית של פתרון המשחק כאשר יש רק שלוש דיסקיות (והמוטות וירטואליים):

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

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

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

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

עבור 64 דיסקיות תוכלו לעשות את החשבון בעצמכם - כמו במקרה של המספר בן 216 הספרות, תקבלו שנדרש פרק זמן עצום, הרבה יותר מגילו של היקום, כדי לבצע את ההעברות גם אם מעבירים דיסקית בשניה. אמנם, הזמן הזה מתגמד באופן מחריד לעומת הזמן שנדרש כדי לכתוב את כל המספרים בני ה-216 ספרות - עבור מגדלי האנוי צריך \( 2^{64}-1 \) העברות, ועבור המספרים בני 216 הספרות צריך יותר מ-\( 10^{215} \) מספרים, ובכתיב אחר: יותר מאשר \( 2^{700} \) מספרים.

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

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