برج هانوي لغز بثلاثة أعمدة وأقراص مختلفة الحجم؛ تنقل القرص العلوي وحده، ولا تضع الأكبر فوق الأصغر، حتى تنقل البرج كاملًا إلى عمود آخر. [1]
سنستخدم الأقراص 1 و2 و3، بحيث يكون 1 أصغرها، والأعمدة A وB وC. سنجرب خطة محددة ثم نحاسبها نقلة بنقلة: هل يسمح الوضع الحالي بالحركة؟ وهل وصلت فعلًا إلى الهدف؟ بهذه الطريقة يصبح الحل سجلًا يمكن التحقق منه، لا سلسلة تعليمات تحفظها دون رؤية ما يتغير.
الخلاصة السريعة
- في مثالنا تنتقل الأقراص الثلاثة من A إلى C في سبع نقلات قانونية.
- بعد النقلة الثالثة يستقر القرصان 1 و2 على B، فيصبح نقل القرص 3 إلى C ممكنًا.
- الفاحص يرفض تحريك قرص مغطى، ويرفض وضع القرص 2 فوق القرص 1.
- قارنا الحل العودي ببحث مستقل للأعداد من صفر إلى سبعة أقراص ولكل اتجاه بين الأعمدة؛ اتفقت المسافات في الحالات الثماني والأربعين.
- إذا استأنفت من حالة وسطية، فاحسب مسارها هي؛ لا تعاملها تلقائيًا كبرج كامل في موضع البداية.
جهز مدخلًا لا يترك الأحجام غامضة
ضع ثلاث بطاقات مرقمة أمامك تمثل A وB وC، وارسم ثلاث قطع بعروض مختلفة واكتب عليها أرقامها. نرتب البداية من الأسفل إلى الأعلى: 3 ثم 2 ثم 1 على A؛ ونجعل العمودين الآخرين فارغين. قبل أول حركة اكتب أن الهدف هو جمع القطع على C بالترتيب نفسه.
الأرقام أسماء لأحجام مرتبة، وليست مواضع الأعمدة. نقل القرص 2 إلى العمود B لا يغير رقمه. هذا التمييز مهم عند تدوين الحل: عبارة «انقل الثاني» غامضة إذا قصد بها القارئ ثاني قطعة من الأعلى؛ لذلك نسجل رقم القرص واسم المصدر واسم الوجهة معًا.
نفذ السبع نقلات واقرأ كل عمود من الأسفل
في الجدول، الرمز «—» يعني عمودًا فارغًا، والسلسلة 321 تعني أن 3 في الأسفل و1 في الأعلى. نعطي حالة البداية ثم الحالة بعد كل حركة؛ بذلك تستطيع مطابقة البطاقات مع الصف الحالي قبل الانتقال إلى التالي. تُقرأ خلايا الأعمدة من اليسار إلى اليمين داخل هذا الجدول.
| خطوة | النقلة | A | B | C |
|---|---|---|---|---|
| 0 | — | 321 | — | — |
| 1 | 1: A→C | 32 | — | 1 |
| 2 | 2: A→B | 3 | 2 | 1 |
| 3 | 1: C→B | 3 | 21 | — |
| 4 | 3: A→C | — | 21 | 3 |
| 5 | 1: B→A | 1 | 2 | 3 |
| 6 | 2: B→C | 1 | — | 32 |
| 7 | 1: A→C | — | — | 321 |
لاحظ وظيفة النقلة الخامسة: نعيد الأصغر إلى A مؤقتًا حتى نكشف القرص 2. رجوع قطعة إلى عمود سابق لا يعني أن الخطة فشلت؛ ما يهم هو الحالة الكاملة. أما حذف هذه النقلة ثم محاولة نقل القرص 2 من B إلى C، فيجعلنا نحاول إخراجه من تحت القرص 1.
اكتب فاحصًا منفصلًا عن مولد الحل
نمثل الحالة بثلاث خانات مرتبة حسب القرص: الأولى لموضع 1، ثم 2، ثم 3. بعد الخطوة الثانية تصبح الحالة (C,B,A). لا تعني هذه القائمة ترتيب القطع فوق بعضها؛ ترتيبها الرأسي معروف من أحجامها، أما الخانات فتخبرنا فقط بالعمود الذي يشغله كل قرص.
قبل تطبيق نقلة، يبحث فاحصنا عن القرص في عمود المصدر، ثم يسأل هل يوجد قرص أصغر منه في المصدر أو في الوجهة. وجود الأصغر في المصدر يعني أن القرص مغطى؛ ووجوده في الوجهة يعني أن الوضع المقترح غير قانوني. كما يرفض المصدر والوجهة المتطابقين أو اسم عمود غير معروف.
أدخلنا أربع نقلات معيبة عمدًا. محاولة نقل 2 من A في البداية رُفضت لأنه مغطى. وبعد نقل 1 إلى C، رُفض نقل 2 فوقه. ورُفضت محاولة أخذ 1 من B وهو على A، وكذلك «نقلة» من A إلى A. هذه اختبارات لسلوك البرنامج؛ لم ندّع إجراء جلسة لعب مادية أو قياس أداء أشخاص.
اجعل المشكلة الأصغر تعود بنفسها
الحل العودي ينقل الأقراص الأصغر إلى العمود المساعد، ثم ينقل الأكبر إلى الهدف، ثم ينقل الأصغر فوقه. نوقف الاستدعاء عند صفر أقراص. الكود التالي صياغة لهذه الخطوات، ويُستدعى لعدد صحيح غير سالب وأسماء ثلاثة أعمدة مختلفة. [2]
def moves(n, source="A", target="C", spare="B"):
if n == 0:
return
yield from moves(n-1, source, spare, target)
yield n, source, target
yield from moves(n-1, spare, target, source)عند استدعاء list(moves(3)) حصلنا على النقلات السبع في الجدول. ترتيب وسيطات الاستدعاء الأول مهم: يصبح العمود المساعد هدفًا مؤقتًا، ويصبح الهدف الأصلي مساعدًا. إذا نسخت أسماء الأعمدة بالترتيب نفسه في كل استدعاء، فلن تكون قد ترجمت الخطة التي نفذناها.
ميّز وجود حل عن إثبات أنه الأقصر
في اللعبة القياسية بثلاثة أعمدة، عدد النقلات الأدنى هو 2ⁿ−1. العلاقة T(n)=2T(n−1)+1 تجمع نقل الكومة الأصغر مرتين ونقلة الأكبر بينهما؛ تنفيذ الخطوات يحقق هذا الحد. [2]
للتحقق الحاسوبي دون الاعتماد على المولد السابق، أنشأنا بحثًا يبدأ من حالة الأقراص، ويولد جميع الحركات القانونية الممكنة. يحفظ أول ظهور لكل حالة، ثم يفحص الحالات حسب عدد النقلات: صفر أولًا، ثم واحدة، ثم اثنتان. أول وصول للهدف عند هذا الترتيب يعطي أقصر مسار لأن كل حركة تكلف نقلة واحدة.
فحصنا من صفر إلى سبعة أقراص مع الاتجاهات الستة الممكنة بين الأعمدة. هذه 48 حالة بداية وهدف. كانت المسافات للأعداد من صفر إلى سبعة: 0 و1 و3 و7 و15 و31 و63 و127، واتفق البحث مع طول الحل العودي في كل اتجاه. هذه المقارنة مستقلة في طريقة توليد المسارات، لكنها تبقى اختبارًا لنطاق صغير؛ لا نستبدل بها البرهان الرياضي العام.
استأنف من الحالة التي تراها
لنفترض أنك توقفت بعد الخطوة الثانية من جدولنا: الأصغر على C، والأوسط على B، والأكبر على A. البحث المستقل وجد خمس نقلات للوصول من هذه الحالة إلى البرج الكامل على C. وهي الخطوات من الثالثة إلى السابعة في السجل. لا تبدأ تطبيق moves(3) من جديد؛ أول تعليماته تفترض الأصغر على A، بينما هو الآن على C.
فحصنا المولد كذلك من صفر إلى ثمانية أقراص عبر الاتجاهات الستة، أي 54 حالة، واختبرنا قانونية كل حركة وبلوغ الهدف وطول السجل. بلغ مجموع التأكيدات المنفذة 3173، ويشمل اختبارات البحث والنقلات المرفوضة. يمكنك تكرار الفحص بتغيير أسماء الأعمدة مع إبقاء الأحجام والأدوار واضحة؛ نجاح حالة البداية لا يبرر تطبيق قائمة نقلات على وضع آخر.
المصادر
الأمثلة والرسوم والفحوص الحاسوبية أُعدت لهذا المقال. أُعد النص بمساعدة الذكاء الاصطناعي، ولا يُنسب إلى مراجعة بشرية مستقلة.