برج هانوي

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

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

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

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

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

أصولها

اخترع الرياضياتي الفرنسي إدوارد لوكاس الأحجية عام 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 على مشروع الدليل المفتوح
• لعبة برج هانوي