برج هانوي

نموذج لأبراج هانوي بثمانية أقراص

برج هانوي أو برج براهما هي لعبة رياضية أو أحجية. تحتوي الأحجية على ثلاثة قضبان، وعدد من الأقراص بأحجام مختلفة والتي يمكن أن تنزلق على أي من هذه القضبان. تبدأ الأحجية مع الأقراص مرتبين في كومة بشكل تصاعدي من ناحية الحجم على قضيب واحد، الأصغر في الأعلى، مشكلةً بذلك شكلاً مخروطياً.

هدف الأحجية هو نقل كامل الكومة لقضيب آخر، باتباع القوانين التالية:

• مسموح نقل قرص واحد فقط بكل مرة.
• كل حركة هي عبارة عن نقل القرص العلوي من قضيب واحد وانزالها في قضيب آخر، فوق الأقراص الأخرى الموجودة مسبقاً على ذلك القضيب.
• لا يمكن وضع قرص ما فوق قرص أصغر منه حجماً.

مع ثلاثة أقراص، بالإمكان حل الأحجية بسبع حركات.

أصولها

اخترع الرياضياتي الفرنسي إدوارد لوكاس الأحجية عام 1883. هنالك أسطورة حول معبد هندي بداخله غرفة كبيرة فيها ثلاثة أعمدة مع 64 قرصاً ذهبياً. ويتصرف الكهنة البراهمة امتثالاً لنبؤة قديمة تقضي بأن يحركوا هذه الأقراص وفقاً لقواعد الأحجية، منذ ذلك الوقت. ولذك تعرف الأحجية أيضا ببرج برهمن. وتنصّ الأسطورة على أن انتهاء العالم سيكون مع الحركة الأخيرة. ليس من المعلوم ما إذا اخترع لوكاس هذه الأسطورة أو استوحى منها.

إن صدقت الأسطورة، وإذا كان باستطاعة الكهنة نقل الأقراص بمعدل قرص بالثانية، باستخدام أقل عدد ممكن من الحركات، فسيستغرق الأمر 2⁶⁴−1 ثانية أي ما يعادل 585 مليار سنة تقريبًا أو 18,446,744,073,709,551,615 حركة للانتهاء.

هنالك العديد من الاختلافات في هذه الأسطورة. على سبيل المثال، في بعض الأقاويل، المعبد هو دير والكهنة هم رهبان. ويقال أن المعبد أو الدير موجود في أماكن مختلفة في العالم - بما في ذلك هانوي، الفيتنام، وقد يرتبط مع دين ما. تشتمل بعض النسخ من الأسطورة على عناصر أخرى، مثل أن البرج قد شيد في بداية العالم، أو أن الكاهن أو الراهب قد يؤدي حركة واحدة فقط في اليوم.

شروط اللغز

يجب أن تنقل حلقة واحدة في كل خطوة

لا تستطيع وضع حلقة كبيرة فوق حلقة صغيرة

خطوات عمل اللغز

يجب عليك احضار سطح مستوي ويركب 3 أعمدة عمودين في الأطراف وعمود في النصف ثم تحتضر عدد من الحلقات باحجام مختلفة

وتضع الحلقة الكبرى في الأسفل وفوقها الأصغر منها ثم الأصغر وهكذا حتى تصل إلى اصغر واحدة

الحل

حل الأحجية من ثلاثة أقراص.

حل الأحجية من أربعة أقراص.

بالإمكان لعب الأحجية بكل عدد ممكن من الأقراص، مع أنه في أغلب نسخ الألعاب من الأحجية تحتوي على سبعة إلى تسعة أقراص. قد تبدو اللعبة مستحيلة لبعض المبتدئين، لكنها قابلة للحل باستخدام خوارزمية بسطية. عدد الحركات المطلوبة لحل أحجية برج هانوي هي 2ⁿ -1، وتمثل n عدد الأقراص.

حل تعاودي

المفتاح لحل الأحجية هو ملاحظة أن بالإمكان حلها عن طريق تقسيم المسألة إلى مجموعة من مسائل أصغر، وكذلك تقسيم تلك المسائل كذلك إلى مسائل أصغر حتى نصل إلى الجواب النهائي. الطريقة التالية توضح الأسلوب.

• علِّم الأعمدة ب A, B, C
• ليكن عدد الأقراص n
• رقّم الأقراص من 1 (الأصغير، في الأعلى) إلى n (الأكبر، في الأسفل)

لنقل كل الأقراص من العمود A إلى العمود C:

1. حرك n-1 الأقراص من A إلى B. اترك القرص n على العمود A
2. حرك القرص n من A إلى C
3. حرك n−1 الأقراص من B إلى C بحيث يكونو فوق القرص n

ما ورد أعلاه هو خوارزمية عودية: لتنقيذ الخطوات 1 و 3، طبق نفس الخوارزمية مجددا على n−1. العملية كلها تأخذ عدد محدود من الخطوات، لأن الخوارزمية في مرحلة ستصل إلى n = 1. هذه العملية، تحريك قرص واحد من العمود A إلى العمود B، هي بسيطة.

لهذا الحل يوجد ميزة بأنه بسيط جداً للتطبيق بواسطة الحاسوب، ويتم استخدام هذه الطريقة كمثال للاستدعاء الذاتي عند تدريس البرمجة. من ناحية أخر من الصعب تطبيق هذا الحل بواسطة البشر.

وصلات خارجية

• إيريك ويستاين، Tower of Hanoi، ماثوورلد Mathworld (باللغة الإنكليزية).

• Tower of Hanoi على مشروع الدليل المفتوح
• لعبة برج هانوي