أبراج هانوي

شروط اللغز

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

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

حرك القرص n من A إلى C

لعبة برج هانوي

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

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

وصلات خارجية

حرك n−1 الأقراص من B إلى C بحيث يكونو فوق القرص n

الحل

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

ليكن عدد الأقراص n

• رقّم الأقراص من 1 (الأصغير، في الأعلى) إلى n (الأكبر، في الأسفل)
• لنقل كل الأقراص من العمود A إلى العمود C:
• حرك n-1 الأقراص من A إلى B. اترك القرص n على العمود A

أصولها

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

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

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

حل تعاودي

علِّم الأعمدة ب A, B, C

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

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

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

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