מגדלי האנוי משחק חשיבה

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

המשחק כולל:

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

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