♛ التراجع في العمل على رقعة الشطرنج
تضع الخوارزمية ملكة واحدة في كل عمود، من اليسار إلى اليمين. وعندما تعلق، تتراجع إلى الوراء (backtrack) وتجرب خانة أخرى. شاهدها وهي تكشف الحلول الـ 92.
الحلول الموجودة
0 / 92
الملكات الموضوعة
0 / 8
مرات التراجع
0
رقعة فارغة. اضغط على «حُلّ» لإطلاق التراجع، أو «الحل التالي» للتقدم نحو الوضعية الصحيحة المقبلة.
♛ التحدي (ماكس بيتسل، 1848)
في عام 1848، طرح لاعب الشطرنج الألماني ماكس بيتسل سؤالًا يبدو بريئًا في مجلة متخصصة: هل يمكن وضع 8 ملكات على رقعة شطرنج 8 × 8 بحيث لا تهاجم أي منها الأخرى؟
في الشطرنج، الملكة (الوزير) هي أقوى قطعة: فهي تكتسح كامل سطرها وكامل عمودها وكلا قطريها. وبذلك تعود المسألة إلى ترتيب 8 ملكات دون أن تتقاسم اثنتان منها أبدًا سطرًا أو عمودًا أو قطرًا. سهلة الصياغة، عسيرة الحل باليد.
اهتم بها العظيم كارل فريدريش غاوس منذ عام 1850، وأحصى حلولها بعد بعض التجريب وخطأ أولي. وصارت النتيجة النهائية شهيرة: يوجد بالضبط 92 حلًا.
النتيجة الأساسية
على رقعة شطرنج 8 × 8، يوجد بالضبط
92 حلًا → 12 حلًا أساسيًا بالتناظر
🔢 لماذا هي مسألة في التأليفيات
كم عدد طرق وضع 8 ملكات على 64 خانة؟ إذا اخترنا بحرية 8 خانات من بين 64، فإن عدد الوضعيات هائل:
C(64, 8) = 4 426 165 368 ≈ 4,4 مليار
أكثر من 4 مليارات وضعية ينبغي فحصها! إن اختبار كل واحدة على حدة سيكون عبثيًا. لكن ملاحظة بسيطة تغير كل شيء: في الحل الصحيح، توجد ملكة واحدة بالضبط في كل عمود (وإلا تقاسمت ملكتان عمودًا). وبذلك يمكننا الاكتفاء بأن نختار، لكل عمود من الأعمدة الثمانية، أحد الأسطر الثمانية. وهذا يقلص فضاء البحث إلى:
88 = 16 777 216 ≈ 16,8 مليون
ننتقل من 4,4 مليار إلى ~16,8 مليون فقط باستثمار قيد بديهي. وإذا أضفنا «ملكة واحدة في كل سطر أيضًا»، نصل إلى !8 = 40 320 تبديلًا ينبغي اختبارها. وهذا أقل بكثير — لكن يمكننا أن نفعل أفضل بما لا نهاية بفضل التراجع.
↩️ التراجع (backtracking): جرّب، أخفق، ارجع
يُعد التراجع واحدًا من أكثر الأفكار الخوارزمية أساسية في المعلوميات. فبدلًا من توليد كل الوضعيات ثم تصفيتها، نقوم بـ بناء الحل خطوة بخطوة ونتخلى عن أي مسار حالما يصبح ميؤوسًا منه.
خوارزمية ضع(العمود c):
- إذا كان c = 8: امتلأت كل الأعمدة → تم العثور على حل!
- لكل سطر r من 0 إلى 7:
- إذا كانت الخانة (r, c) غير مهاجَمة من أي ملكة موضوعة مسبقًا → نضع الملكة.
- ننادي ضع(c + 1).
- نسحب الملكة (التراجع) ونجرب السطر r التالي.
- إذا لم يعد أي سطر مناسبًا → نرجع إلى العمود السابق.
تأتي الأناقة من التشذيب: فحالما تُحدث ملكة تعارضًا، لا نضيع الوقت بعدها في استكشاف الأعمدة التالية — إذ يُقطع فرع كامل من شجرة الإمكانيات دفعة واحدة. ففي حين تفحص القوة الغاشمة ملايين الوضعيات، لا يزور التراجع منها سوى بضعة آلاف. إنه الفرق بين تفتيش كل حبة رمل واتباع خريطة كنز.
اختبار «هل الخانة مهاجَمة؟» فوري: ملكتان في (r₁, c₁) و(r₂, c₂) متعارضتان إذا كان r₁ = r₂ (نفس السطر)، أو إذا كان |r₁ − r₂| = |c₁ − c₂| (نفس القطر). وبما أننا نضع ملكة واحدة في كل عمود، فلا يمكن أن يحدث تعارض الأعمدة أبدًا.
🌍 وماذا عن n ملكة؟ الانفجار التأليفي
تتعمم المسألة بشكل طبيعي إلى مسألة n ملكة على رقعة n × n. ونعلم أن حلًا يوجد لكل n ≥ 4. لكن إحصاء عدد الحلول يصبح مدوخًا:
- n = 8: 92 حلًا.
- n = 10: 724 حلًا.
- n = 12: 14 200 حلًا.
- n = 27: 234 907 967 154 122 528 حلًا (رقم قياسي حسابي تم بلوغه عام 2016).
انتبه إلى فكرة شائعة خاطئة: العثور على حل ليس صعبًا من صنف NP. فهناك طرق مباشرة تبني حلًا بسرعة لكل n. ما ينفجر هو إحصاء جميع الحلول: فلا تُعرف أي صيغة مغلقة، وعدد الوضعيات التي ينبغي استكشافها ينمو أسرع من أي دالة أسية بسيطة. إنه ميدان اختبار مفضل لخوارزميات إرضاء القيود.
🤖 أكثر بكثير من لعبة: مسائل إرضاء القيود (CSP)
صارت مسألة الملكات الثماني المثال النموذجي لعائلة من المسائل الكبرى في الذكاء الاصطناعي: مسائل إرضاء القيود (CSP، Constraint Satisfaction Problems). والمخطط دائمًا هو نفسه: متغيرات (أين توضع كل ملكة)، ومجالات (الأسطر الممكنة)، وقيود (ألا تتهاجم).
إن الآلية نفسها بالضبط — متغيرات، مجالات، قيود، تراجع — تحل مسائل واقعية تمامًا:
- التخطيط: الجداول الزمنية المدرسية، مواقيت القطارات، توزيع القاعات دون تداخل.
- تخصيص الموارد: إسناد الترددات الإذاعية إلى الهوائيات دون تشويش، تلوين خريطة بأقل عدد من الألوان.
- التهيئة الصناعية: تجميع منتج مع احترام جميع قيود التوافق بين المكونات.
- سودوكو والألغاز المنطقية: السودوكو ليس سوى مسألة إرضاء قيود كبيرة تُحل بالتراجع ونشر القيود.