حل الألغاز باستخدام بحث A*
تعلم كيفية حل لغز الشبكة 3x3 المكون من 8 أرقام باستخدام بحث A*.
سنغطي ما يلي...
اخترع نويز بالمر تشابمان لغز الثمانية، المعروف أيضًا باسم لغز الانزلاق، في سبعينيات القرن التاسع عشر، واكتسب شعبية واسعة بعد أن روّج له سام لويد، الذي ادّعى زورًا أنه هو من اخترعه. في البداية، اعتُبرت لعبة بسيطة لكنها صعبة، ثم اكتسبت أهمية في مجال علوم الحاسوب والذكاء الاصطناعي كمسألة كلاسيكية لاستكشاف خوارزميات البحث مثل A*.
موضوعي
لنطبّق خوارزمية البحث A* لحل لغز تقليدي: لغز 8. سيساعدك هذا التمرين على فهم كيفية تطبيق A* لحل مسائل يكون الهدف منها ترتيب القطع بترتيب محدد.
نظرة عامة على اللغز
تتكون لعبة الألغاز الثمانية من شبكة ٣×٣ تحتوي على ٨ قطع مرقمة ومساحة فارغة. الهدف هو تحريك القطع حتى تصبح بترتيب معين. تبدأ اللعبة في حالة خلط، وعليك تحريك القطع للوصول إلى حالة الهدف.
خطوات حل اللغز
إليكم دليلًا مفصلًا لفهم وحل مسألة الألغاز الثمانية باستخدام الكود المُرفق. سنُقسّمها إلى خطوات منطقية، ثم نستكشف كيفية ترابط كل جزء برمجيًا.
تحديد حالات اللغز
يُمثَّل اللغز كحالة تُرتَّب فيها المربعات والمساحة الفارغة (المُمَثَّلة بالصفر) في شبكة 3×3. سنستخدم قائمة متداخلة، حيث تُمثِّل كل قائمة فرعية صفًا في الشبكة. إليك التكوين الأولي للغز:
start_state = [[1, 2, 3],[4, 0, 5],[7, 8, 6]]
حركة الفضاء الفارغ
في لغز الثمانية، يمكن تحريك المساحة الفارغة (الممثلة بالرقم 0) لأعلى، لأسفل، لليسار، أو لليمين داخل الشبكة. كل حركة تُغيّر موقع الرقم 0 وتُبدّله بقطعة مجاورة. تعتمد الحركات الصحيحة على الموقع الحالي للمساحة الفارغة. إليك كيفية حساب الحركات الممكنة للمساحة الفارغة:
تحديد الموقف:
تحويل فهرس القائمة المسطحة للمساحة الفارغة إلى موضع شبكة ثنائي الأبعاد (صف، عمود) باستخدام
divmod.
إنشاء التحركات الممكنة:
التحرك لأعلى: إذا لم تكن المساحة الفارغة في الصف العلوي (الصف > 0)، فيمكنها التحرك لأعلى.
التحرك للأسفل: إذا لم تكن المساحة الفارغة في الصف السفلي (الصف < 2)، فيمكنها التحرك للأسفل.
التحرك إلى اليسار: إذا لم ...