🎛️ حلّ أبراج هانوي وأنت تشاهد الخوارزمية تعمل
اختر عدد الأقراص (من 1 إلى 8) واضغط على «حُلّ». تقوم الخوارزمية العودية بعملها في 2ⁿ − 1 حركة مثلى.
الحركات المنجزة
0
الأمثل : 2ⁿ − 1
15
المدة بحركة واحدة/ثانية
15 sec
n = 4 أقراص : 15 حركة مثلى. اضغط على «حُلّ» لمشاهدة الخوارزمية.
🗼 المسألة (1883، إدوار لوكاس)
فرانسوا إدوار أناتول لوكاس، عالم رياضيات فرنسي، اخترع سنة 1883 لعبة ستصبح المثال الأشهر للعَودية. المشهد :
- ثلاثة أبراج عمودية (نرمز إليها بـ A و B و C).
- على البرج A، n قرصًا مكدسة من الأكبر (في الأسفل) إلى الأصغر (في الأعلى).
- الهدف : نقل جميع الأقراص من A إلى C.
- القواعد :
- لا نحرّك إلا قرصًا واحدًا في كل مرة.
- لا يمكن أبدًا وضع قرص أكبر فوق قرص أصغر.
- نستعمل الأبراج الثلاثة كوسائط.
بقرص واحد، الأمر بديهي : حركة واحدة (A → C). بقرصين، 3 حركات. بثلاثة أقراص، 7 حركات. بأربعة أقراص، 15 حركة. متتالية : 1، 3، 7، 15، 31، 63، …
مبرهنة (العدد الأدنى للحركات)
العدد الأدنى من الحركات لنقل n قرصًا هو :
M(n) = 2n − 1
💡 الفكرة العبقرية : العَودية
كيف نعرف حلّ هانوي بـ 100 قرص ؟ لن تفعل كل شيء يدويًا. ستستعمل العَودية. إليك الخوارزمية :
الخوارزمية Hanoï(n, source, dest, aux) :
- إذا كان n = 1 : حرّك القرص من source → dest.
- وإلا :
- Hanoï(n − 1, source, aux, dest) // حرّك n−1 قرصًا إلى البرج الوسيط
- حرّك القرص الكبير source → dest // حركة واحدة
- Hanoï(n − 1, aux, dest, source) // حرّك n−1 قرصًا إلى الوجهة
هذه الأناقة شبه سحرية. الخوارزمية تستدعي نفسها مرتين، وتحلّ المسألة في عدد أسّي من الحركات. وهذا هو التعريف ذاته لـ العَودية الأسّية.
📐 برهان M(n) = 2ⁿ − 1
تحترم الكلفة الإجمالية علاقة التراجع :
M(n) = 2·M(n − 1) + 1، مع M(1) = 1
برهان بالترجع :
- التهييئ : M(1) = 1 = 2¹ − 1. ✓
- التوارث : نفترض M(n − 1) = 2n−1 − 1. إذن :
M(n) = 2·(2n−1 − 1) + 1 = 2n − 2 + 1 = 2n − 1. ✓
وهو المطلوب. إنه أحد أكثر تمارين الترجع أناقة — ويعود بانتظام في الأولمبياد.
🕉️ أسطورة بوذا بنارس
أرفق لوكاس لعبته بأسطورة رائعة :
كم يستغرق ذلك ؟ احسب : 2⁶⁴ − 1 = 18 446 744 073 709 551 615 حركة. بحركة واحدة في الثانية، سيكون ذلك حوالي 585 مليار سنة. عمر الكون 13.8 مليار سنة. ما زال أمام الراهب البوذي 99.998% من العمل.
⚡ التعقيد الأسّي : جدار لا يُتجاوز
بـ 30 قرصًا : مليار حركة. ممكن في بضع ثوانٍ على حاسوب. بـ 60 قرصًا : 1018 حركة. حتى مليار عملية/ثانية لا تكفي — سيلزم 30 سنة لحاسوب فائق. بـ 100 قرص : مستحيل قبل نهاية الكون.
هانوي هو المثال المثالي لمسألة لها حلّ بسيط (الخوارزمية في 3 أسطر) لكن تعقيد كارثي. إنها بالضبط الحدّ الفاصل بين P و EXPTIME في علوم الحاسوب النظرية. بعد حجم معيّن، مهما كانت قدرة الحساب المتاحة : لن تستطيع الحلّ.
🎯 هانوي ومثلث باسكال (رابط سحري)
صِل بين عددين متتاليين من «حلّ أمثل» لهانوي بـ n قرصًا، فتحصل على مسار في مبيان على شكل سييربينسكي (نعم، المثلث الكسوري من الفئة B). خوارزمية هانوي متماثلة الشكل مع تصفّح شجرة في سييربينسكي متقطع.
هذا الربط المدهش بُرهن سنة 1981 من قبل أندرياس هينتس. إنه الرسم المثالي لـوحدة الرياضيات : العَودية (هانوي)، الكسوري الهندسي (سييربينسكي)، والعدّ التوافقي (تصفّح شجرة) هي في الحقيقة الكائن نفسه من ثلاث زوايا مختلفة.
📐 كيف يظهر في باكالوريا العلوم الرياضية
هانوي ليس في البرنامج الرسمي، لكنه أرضية لعب مثالية للتمرّن على :
- المتتاليات الترجعية : العلاقة M(n) = 2·M(n−1) + 1 هي الحالة النموذجية لمتتالية حسابية-هندسية في الثانية باكالوريا علوم رياضية.
- الترجع القوي : برهان الصيغة M(n) = 2ⁿ − 1 هو تمرين ترجع مثالي للتدرّب.
- الخوارزميات العودية (إضافة لمن يبرمجون) : هانوي هو المثال الأشهر للعَودية في المعلوميات.
- البرهان بالترجع على صيغة صريحة : تقنية مطلوبة في كل دورة من باكالوريا العلوم الرياضية.
🌍 المتغيرات والتعميمات
- هانوي بـ 4 أبراج (مسألة فريم-ستيوارت، 1941) : بـ 4 أبراج بدل 3، الحلّ الأمثل غير معروف في الحالة العامة. مسألة مفتوحة طيلة 80 سنة.
- هانوي ثنائية الألوان : تبديل الأقراص بلونين مع قيود.
- هانوي الدائرية : لا يمكن تحريك الأقراص إلا في اتجاه واحد A → B → C → A.
- هانوي بعدة أقراص في الحركة الواحدة : يمكن أخذ الكومة بأكملها.