أبراج هانوي (Towers of Hanoi): شرح مبسّط للخوارزمية والتكرار

أبراج هانوي (Towers of Hanoi) هي أُحجية رياضية تُستخدم في علوم الحاسوب كـ"المثال الذهبي" لتعليم مفهوم التكرار (Recursion): أي حلّ مشكلة كبيرة عن طريق استدعاء الدالة لنفسها على نسخة أصغر من المشكلة. باختصار: لديك ثلاثة أعمدة وعدد من الأقراص المتدرّجة في الحجم، والمطلوب نقلها كلها من العمود الأول إلى العمود الثالث بأقل عدد ممكن من النقلات مع الالتزام بقاعدتين. إذا كنت تدرس المادة، فالهدف الحقيقي من اللغز ليس اللعب، بل فهم كيف يفكّر الحاسوب بشكل تكراري وكيف نحلّل تكلفة الخوارزمية.

ما هي قواعد اللعبة؟

اللغز بسيط في تعريفه، صعب في تنفيذه يدويًا عندما يزيد عدد الأقراص:

1. تُنقل قرص واحد فقط في كل حركة.
2. تأخذ القرص العلوي من أحد الأعمدة وتضعه على عمود آخر.
3. لا يجوز أبدًا وضع قرص أكبر فوق قرص أصغر.

العمود الثالث هو الوجهة، والعمود الأوسط مجرد "عمود مساعد" مؤقت. هذه القيود البسيطة هي التي تجعل اللغز مثاليًا لشرح الخوارزميات: الحل يبدو معقّدًا للعين البشرية، لكنه ينهار إلى قاعدة واحدة أنيقة عند التفكير فيه تكراريًا.

لماذا يُدرّس في الخوارزميات وهياكل البيانات؟

المفتاح هو الفكرة التالية: لكي أنقل n قرصًا، يكفي أن أعرف كيف أنقل n−1 قرصًا. أي أننا نُعرّف الحل بدلالة نسخة أصغر منه، وهذا هو جوهر التكرار.

الفكرة الذهنية للحل مع n قرصًا:

1. انقل الأقراص العلوية الـ n−1 من العمود المصدر إلى العمود المساعد (باستخدام العمود الهدف كوسيط مؤقت).
2. انقل القرص الأكبر (رقم n) مباشرةً من المصدر إلى الهدف — نقلة واحدة.
3. انقل الأقراص الـ n−1 من العمود المساعد إلى الهدف (باستخدام العمود المصدر كوسيط).

لاحظ أننا لم نشرح "كيف" نُنفّذ الخطوة الأولى والثالثة تفصيليًا؛ نتركهما للدالة نفسها لتحلّهما بنفس المنطق على مستوى أصغر. حالة التوقف (Base Case) هي عندما يتبقى قرص واحد فقط: عندها ننقله مباشرةً دون أي تعقيد، وهذا ما يمنع الاستدعاء من الاستمرار للأبد.

الحل بالبرمجة (مثال بايثون)

هذه دالة تكرارية قصيرة تطبع كل نقلة مطلوبة:

def hanoi(n, source, target, auxiliary):
    if n == 1:                       # حالة التوقف
        print(f"انقل القرص 1 من {source} إلى {target}")
        return
    hanoi(n - 1, source, auxiliary, target)   # الخطوة 1
    print(f"انقل القرص {n} من {source} إلى {target}")  # الخطوة 2
    hanoi(n - 1, auxiliary, target, source)   # الخطوة 3

hanoi(3, 'A', 'C', 'B')

المنطق نفسه ينطبق على أي لغة (C++‎، Java، JavaScript)؛ ما يتغيّر هو الصياغة فقط. ملاحظة عملية شائعة يقع فيها المبتدئون: ترتيب الأعمدة الثلاثة (المصدر، الهدف، المساعد) يختلف بين الاستدعاءين الداخليين. في الخطوة الأولى يصبح "الهدف" وسيطًا مؤقتًا، وفي الخطوة الثالثة يصبح "المصدر" وسيطًا. الخلط بين هذين الترتيبين هو الخطأ الأول الذي يجعل الحل لا يعمل، فانتبه له جيدًا.

التحليل الزمني: لماذا ينمو بشكل أُسّي؟

أقل عدد ممكن من النقلات لحل اللغز بـ n قرصًا هو:

T(n) = 2ⁿ − 1

من أين جاءت؟ لحل n قرصًا نحتاج إلى حلّ (n−1) مرتين، بالإضافة إلى نقلة واحدة للقرص الأكبر، أي: ‎T(n) = 2·T(n−1) + 1، وحلّ هذه العلاقة يعطي ‎2ⁿ − 1. عمليًا هذا يعني تعقيدًا زمنيًا من الرتبة O(2ⁿ)، وهو نموّ أُسّي "متفجّر":

عدد الأقراص n	عدد النقلات 2ⁿ−1
3	7
10	1023
20	1,048,575
64	نحو 1.8 × 10¹⁹

هنا تظهر أسطورة اللغز الشهيرة: لو نقل الرهبان قرصًا واحدًا كل ثانية لـ 64 قرصًا، لاحتاجوا مئات المليارات من السنين. الدرس الهندسي المهم: خوارزمية أبراج هانوي مثالية للتعليم، لكنها كارثية للأداء. إنها تُذكّرك بأن الحلول الأنيقة تكراريًا ليست بالضرورة سريعة، وأن التعقيد الأُسّي يجب تجنّبه في التطبيقات الحقيقية كلما أمكن.

أبراج هانوي وبقية الخوارزميات التكرارية

أبراج هانوي بوابة لفهم عائلة كاملة من الخوارزميات القائمة على "فرّق تسُد" (Divide and Conquer)، مثل البحث الثنائي (Binary Search)، وفرز الدمج (Merge Sort)، والفرز السريع (Quick Sort). الفرق الجوهري: تلك الخوارزميات تقسم المشكلة لتصل إلى تعقيد لوغاريتمي أو ‎n log n، بينما تُضاعف أبراج هانوي حجم العمل في كل مستوى، فتصل إلى تعقيد أُسّي. مقارنة الحالتين تعلّمك متى يكون التكرار كفؤًا ومتى يكون فخًّا.

الأسئلة الشائعة

هل يمكن حل أبراج هانوي بدون تكرار؟ نعم، هناك حلّ تكراري تقليدي (Iterative) باستخدام حلقات ومكدّس (Stack) صريح بدل استدعاء الدالة لنفسها. النتيجة نفسها وعدد النقلات نفسه، لكن نسخة التكرار (Recursion) أوضح وأسهل قراءةً، ولهذا تُدرّس أولًا.

من أين جاء اسم اللعبة؟ ابتكرها عالم الرياضيات الفرنسي إدوارد لوكاس عام 1883 وباعها كلعبة، ونسج حولها أسطورة معبد هندي فيه 64 قرصًا ذهبيًا. الأسطورة دعائية، لكن الرياضيات وراءها حقيقية تمامًا.

ما أقل عدد نقلات لحل 4 أقراص؟ ‎2⁴ − 1 = 15 نقلة. أي حل بعدد أكبر يعني أنك كررت خطوات دون داعٍ.

لماذا يُطلب هذا السؤال في مقابلات العمل؟ لأنه يكشف بسرعة إن كنت تفهم التكرار وحالة التوقف وتحليل التعقيد الزمني، وهي مهارات أساسية قبل الانتقال إلى مسائل أصعب في هياكل البيانات.