איך משחקים במגדלי האנוי
- בחרו כמה דיסקים רוצים (3 עד 8). כולם מתחילים מוערמים ביתד 1, הגדול למטה והקטן למעלה.
- געו ביתד כדי לבחור את הדיסק העליון שלו ואז ביתד שאליו רוצים להעביר. אפשר גם לגרור את הדיסק ליתד האחר.
- הזיזו דיסק אחד בכל פעם ואף פעם אל תניחו דיסק על דיסק קטן ממנו.
- מנצחים כשכל המגדל נמצא ביתד אחר. המונה מראה את המהלכים שלכם ואת המינימום האפשרי; אם נתקעתם, כפתור פתרון מציג את הפתרון הקצר ביותר.
קלאסיקה של לוגיקה ורקורסיה
מגדלי האנוי הם חידה מתמטית שהמציא הצרפתי אדואר לוקאס ב-1883. עם n דיסקים, מספר המהלכים המינימלי הוא 2 בחזקת n פחות 1: 7 עם שלושה דיסקים, 15 עם ארבעה, 31 עם חמישה ו-255 עם שמונה. כל דיסק שמוסיפים מכפיל את העבודה ומוסיף אחד.
יש דרך שיטתית לפתור. כדי להעביר מגדל של n דיסקים, קודם מעבירים את n−1 הדיסקים העליונים ליתד הנותר, אחר כך מעבירים את הדיסק הגדול ביותר ליעד ולבסוף מעבירים את n−1 הדיסקים עליו. זו דוגמה קלאסית לרקורסיה. כלל מעשי נוסף: הדיסק הקטן ביותר זז בכל מהלך אי-זוגי, תמיד לאותו כיוון (עם מספר אי-זוגי של דיסקים הוא הולך מיתד 1 ל-3, מ-3 ל-2 ומ-2 ל-1; עם מספר זוגי, מ-1 ל-2, מ-2 ל-3 ומ-3 ל-1); במהלכים הזוגיים יש רק מהלך אפשרי אחד בין שני היתדות האחרים.
האגדה מספרת על נזירים שמזיזים מגדל של 64 דיסקים מזהב; יידרשו יותר מ-18 קווינטיליון מהלכים, כלומר מאות מיליארדי שנים במהירות של מהלך בשנייה. הכול מתרחש בדפדפן: שום דבר לא נשלח לשרת ורק התוצאה הטובה ביותר שלכם נשמרת במכשיר.
טוב לדעת
- השיא (הכי פחות מהלכים) נשמר לפי מספר הדיסקים, רק בדפדפן הזה: אם תמחקו את נתוני האתר, הוא יאבד.
- אם משתמשים בפתרון, המשחק לא נספר לשיא. הכפתור מחשב את הפתרון הטוב ביותר מהמצב שבו אתם נמצאים, לא מההתחלה.
- עם 8 דיסקים נדרשים לפחות 255 מהלכים; הפתרון האוטומטי מציג אותם בקצב נוח, ואפשר לעצור אותו בכל רגע.
שאלות נפוצות
מה המטרה במגדלי האנוי?
להעביר את כל הדיסקים מיתד 1 ליתד אחר, דיסק אחד בכל פעם, בלי להניח דיסק גדול על דיסק קטן.
כמה מהלכים נדרשים לכל הפחות?
2 בחזקת מספר הדיסקים פחות 1: 7 עם 3 דיסקים, 15 עם 4, 31 עם 5, 63 עם 6, 127 עם 7 ו-255 עם 8. המונה למעלה מציג את המינימום של המשחק.
איך מזיזים דיסקים בנייד?
געו ביתד המקור ואז ביתד היעד, או גררו את הדיסק העליון באצבע ליתד האחר. במחשב אפשר גם להשתמש במקשים 1, 2 ו-3.
למה משמש כפתור הפתרון?
הוא מציג שלב אחר שלב את הפתרון הקצר ביותר מהמצב הנוכחי. הוא עוזר ללמוד את הדפוס; אחר כך אפשר להתחיל משחק חדש ולנסות לבד.
יש טריק כדי לא ללכת לאיבוד?
כן: הדיסק הקטן ביותר זז במהלכים האי-זוגיים ותמיד לאותו כיוון; במהלכים הזוגיים יש רק מהלך חוקי אחד בין שני היתדות האחרים.
זה בחינם? צריך להתקין משהו?
זה בחינם, בלי הרשמה ובלי התקנה, ועובד בנייד ובמחשב. שום נתון לא מועלה לשרת.