مسألة الوزراء الثمانية
المحتويات

بدايةً، مسألة الوزراء الثمانية أحجية شطرنج يُطلَب فيها وضع 8 وزراء على رقعة أبعادها 8×8 من غير أن يُميت أي منها الآخرين، وهذا يعني عدم وجود وزيرين في الوقت ذاته في: السطر نفسه، والعمود نفسه، والقطر نفسه، وثمة 92 حلًا لهذه المسألة. ونتناول فيما يلي مزيدًا من التفاصيل.
في هذا الإطار، مسألة الوزراء الثمانية حالة خاصة من مسألة الوزراء النونية التي يُطلب فيها وضع n وزريرًا على رقعة شطرنج مقاساتها n×n. لهذه المسألة حلول من أجل قيم n الطبيعية كلها ما خلا 2 و 3. عدد الحلول الدقيق معروف من أجل القيم دون 27 (n ≤ 27)، يكشف التحليل المقارِب أن نمو عدد الحلول بحسب قيم n هو (0.143 n)n.
ومن جهة أخرى، طُرِحت هذه المسألة أولًا في منتصف القرن التاسع عشر، وما تزال تُستعمل اليوم في أثناء تعليم تقنيات البرمجة.
حل المسألة
- تصف الخوارزمية التالية حل مسألة الوزراء بخوارزمية تعقب رجوعي:
- الخوارزمية السابقة منفذة بلغة سي++:
- الخوارزمية السابقة منفذة بلغة جافا:
- الخوارزمية السابقة منفذة بلغة بايثون:
من جهة ثانية، تبدأ الخوارزمية بالسطر الأول وبالعمود الأول: كلما وضع وزير في سطر يُنتقل إلى السطر التالي وتُفحص إمكانية وضع وزير فيه بدءًا من العمود الأول، وهكذا حتى إيجاد موقع للوزير في السطر، وإذا تعذَّر وضع وزير في ذلك السطر، يُرجَع للسطر السابق ويُحرَّك الوزير فيها عمودًا واحدًا وهكذا. يُولَّد الحل عند وضع وزير في آخر سطر بنجاح.
وفي هذا الصدد، يُمكن حل هذه المسألة بخوارزمية تعقب رجوعي لوضع الوزراء في المواقع المناسبة على الرقعة بالترتيب واحدًا واحدًا.
التطبيقات
- انظر كذلك
- هوامش
- المراجع
- فهرس الإحالات
- المنشورات
- بالعربية
- بالإنجليزية
- الوب
- بالعربية
- بالإنجليزية
- ثبت المراجع
- المقالات المُحكَّمة
- بالإنجليزية
- الكتب
- بالعربية
- بالإنجليزية
علاوةً على ذلك، من التقانات التي يُمكن أن تستعمل مسألة الوزراء لتوضيحها: خورازمية الإصلاح التكراري، وهي خوارزمية جشعة تبدأ من وضعية يوجد فيها كل الوزراء على الرقعة، أي 8 وزراء على رقعة 8 × 8 مثلًا مع وجود وزير في كل عمود. ثم تحاول الخوارزمية تحسين مواقع الوزراء بتفضيل المواقع التي يكون عدد الإماتات فيها أقل ما يمكن في كل عمود. مع أن هذه الخوارزمية لا تضمن الوصول إلى حلٍ دومًا من أجل أي وضع ابتدائي للوزراء، إلا أنها قد تجد حلولًا لأبعاد كبيرة جدًا للرقعة، مثلًا مليون وزير على رقعة مليونية الأبعاد.
وفي هذا الصدد، إيجاد كل حلول مسألة الوزراء الثمانية تحدٍ بسيط ولكنه ليس سهلًا بالوقت نفسه، لهذا تُستعمل هذه المسألة لطرح أمثلة عن تقنيات برمجة متنوعة وتعليمها، منها مثلًا برمجة منطقية والخوارزميات الوراثية، ويُمكن كذلك طرح هذه المسألة عند الحديث عن الخوارزميات العودية. وعندها تُفحص الاحتمالات بتتبع الحلول في أجزاء من الرقعة: وحدانية الوزير بالأعمدة والقطرين عادةً، وصولًا إلى الرقعة كاملة.
نبذة تاريخية
وفي السياق ذاته، استعمل أيدسكر دايكسترا هذه المسألة سنة 1972م لتوضيح نجاعة ما سماه البرمجة المهيكلة، ونشر وصفًا بالغ الدقة لخوارزمية تحل المسألة بخوارزمية تعقب رجوعي بتفضيل العمق.
وفي السياق ذاته، نشر ، وهو أحجية الوزراء الثمانية سنة 1848م، ونشر فرانز ناوك أول حلٍ معروف لها سنة 1850م. عمَّم ناوك المسألة كذلك لتشكل n وزيرًا على رقعة شطرنج أبعادها n×n، وشغلت هذه المسألة عددًا من أساتذة الرياضيات، كان من ضمنهم كارل غاوس.
أبعاد أعلى
إضافةً إلى ذلك، تُطرَح المسألة نفسُها في الشطرنج بأبعاد أعلى من 2، مثلًا تكون الرقعة مُكوَّنة من مكعَّب طول ضلعه n، كما يمكن وضع عدد أكثر من الوزراء في الأبعاد أعلى من 2، مثلًا يُمكِن وضع 4 وزراء في فضاء ثلاثي الأبعاد 3×3×3.
الوزراء وقطع أخرى
وفي هذا السياق، يُطلَب في هذه المسألة وضع عدد من الوزراء مع عدد من قطع أخرى على رقعة الشطرنج من غير أن يُميت أي منها الآخرين. يُمكن مثلًا طلب وضع m وزير وm حصان على رقعة (n×n)، أو طلب وضع عدد من الوزراء والبيادق من غير أن يُميت أحدها الآخرين.
وجود الحلول
من جانب آخر، إذا كانت n = 20 (الباقي 2)، تكون القائمة: 2، 4، 6، 8، 10، 12، 14، 16، 18، 20، 3، 1، 7، 9، 11، 13، 15، 17، 19، 5.
إذا كانت n = 8 (باقي القسمة 2)، ينتج الحل الرئيس 1.
علاوةً على ذلك، يُمكن لخوارزميات البحث الشامل حساب عدد الحلول ضمن قدرات حسابية مقبولة حتى ، وتعجز عن حساب عدد الحلول عندما .
كذلك، يمكن توليد حل خَطَوي درجي على رقعة شطرنج n × n، فيها مُربَّع (j ،i)، أي يُوجد في العمود i والسطر j وفق الخوارزمية التالية:
كذلك، إذا كانت n = 15 (الباقي 3)، تكون القائمة: 4، 6، 8، 10، 12، 14، 2، 5، 7، 9، 11، 13، 15، 1، 3.
عدد الحلول
بعض من الأمثلة:
ومن جهة أخرى، إذا كانت n = 14 (الباقي 2)، تكون القائمة: 2، 4، 6، 8، 10، 12، 14، 3، 1، 7، 9، 11، 13, 5.
علاوةً على ذلك، ثمة حلول للرُقَع n × n من أجل n ≥ 4، يُمكن بسهولة توليد أحد الحلول باتباع نمط خَطَوي درجي لمواقع الوزراء كما تظهر الأشكال التالية لرُقَع قيمة n فيها 8 و9 و10 على الترتيب:
إتمام مسألة وزراء نونية
من جانب آخر، هذه المسألة حالة خاصة من المسألة الوزراء النونية، يُعلم فيها موقع عدد من الوزراء على رقعة n×n، ويُطلَب إيجاد مواقع سائر الوزراء على الرقعة من غير أن يُميت أي منها الآخرين.
بقطع أخرى مغايرة للوزير
ومن جهة أخرى، يُمكن طرح المسألة بقطع أخرى من الشطرنج، فعلى رقعة قياسية أبعادها (8×8) يُمكن وضع 32 حصانًا و 14 فيلًا و16 ملكًا و8 رخاخ. وضع الأحصنة سهل، ويكفي وضعها على المربعات من لون واحد على الرقعة، لأنها تتحرك فقط إلى مربعٍ مغاير لونًا للمربع الذي تقف فيه. أما الملوك، فتُقسَم الرقعة أولًا إلى 16 مربعًا كبيرًا (2×2) في كل منها 4 مربعات صغيرة ملونة، ثم يُوضَع الملك في أحد هذه المربعات في الصغيرة في المربعات الكبرى كلها. أما وضع 8 رخاخ على الرقعة فيمكن تمثيله مصفوفة تبديلية أبعادها 8×8.
رقعة 8x8
وفي السياق ذاته، إيجاد كل حلول مسألة الوزراء الثمانية مُكلِف حسابيًا، ثمة 4,426,165,368 ترتيبًا مختلفًا للوزراء يلزم فحصه، منها 92 فقط تصلح حلًا للمسألة. لكن يُمكن تحسين الأداء بتقنيات حسابية تُجنِّب استعمال منهج البحث الشامل. يُمكن مثلًا خفض الاحتمالات المفحوصة بإقصاء كل الحالات التي تحوي أكثر من وزير في عمودٍ واحدٍ من غير فحصٍ، وهذا يجعل عدد التراتيب التي تحتاج فحصًا 16,777,216 أو 88، يُمكن كذلك خفض الاحتمالات اللازم فحصها باستعمال التباديل اعتماًدا على فكرة أنه يوجد 8 حالات متاحة في العمود الأول، ثم 7 في الثاني (بعد إضافة الأول)، ثم 6 في الثالث بعد (إضافة الأول والثاني) ليصبح عدد الحالات اللازم فحصها 40,320 أو 8! فقط.
كذلك، لكل حلِّ من الحلول الرئيسة 8 تنويعات: الحل الرئيس نفسه وتدوير الرقعة 90° و°180 و°270 ثُمَّ عكس كل حلِّ من الحلول انعكاسًا مرآتيًا. يشذ الحل 12 عن سائر الحلول الآخرى بأن تدويره °180 يعيد إنتاج الحل الرئيس، لذلك فإن عدد تنويعاته الفريدة 4 فقط، وهذا يعني أن عدد الحلول الإجمالي: 11×8 + 1×4 = 92 حلًا.
وفي هذا الصدد، الحل 10 له خاصية فريدة تميزه عن سائر الحلول: إذا نظر لرقعة الشطرنج على أنها شبكة مُصبَّعات فإنه .
في هذا الإطار، لمسألة الوزراء الثمانية 92 حلًا متمايزًا، ينتج أغلبها عن حلول أخرى بتدوير رقعة الشطرنج أو إيجاد انعكاسها، أما عدد الحلول الفريدة غير المرتبطة بعلاقات التناظر من دوران وانعكاس فهو 12 حلًا فقط، تُسمَّى الحلول الرئيسة.
رُقَع مغايرة لـ 8x8
الهيمنة
وفي السياق ذاته، تسأل هذه الأحجية عن عدد الهيمنة، وهو عدد القطع الأدنى اللازم وضعه على الرقعة لإماتة أي قطعة عليها، يُمكن مثلًا الهيمنة على رقعة شطرنج (8×8) بوضع 5 وزراء فقط.
العدد الدقيق
من جانب آخر، لا تُعرَف صيغة رياضية لحساب عدد الحلول لمسألة الوزارء النونية. أحصي عدد الحلول الإجمالي من أجل ، يُظهر الجدول التالي عدد الحلول الرئيسة والإجمالية، أي التي تشمل التدوير والانعكاس، لمسألة الوزراء النونية من أجل قيم n الطبيعية دون 28 بحسب موسوعة المتتاليات الصحيحة على الإنترنت.
يُعرَف كذلك عدد الحلول التي من أجل قيم .
العدد التقريبي
في هذا الإطار، وفيه ثابتٌ قيمته بين 1.939 و1.945 وo(1) يُمثِّل تدوين o الصغرى .
وفي هذا السياق، ثَبُت رياضيًا أن عدد حلول مسألة الوزراء من أجل قيم كبيرة لـ n مساوٍ على وجه التقريب للقيمة: ، أو يساوي بدقة التالي:
مسائل ذات صلة
وصف المسألة
علاوةً على ذلك، تطلب مسألة الوزراء الثمانية وضع 8 وزراء على رقعة شطرنج قياسية (8×8) من غير أن يُميت أي منها الآخر. عُمِّمت هذه المسألة لتطلب وضع وزيرًا على رقعة مُربَّعة نونية من غير أن يُميت أي منها الآخر.
ومن جهة أخرى، الوزير قطعة شطرنج، تُسمَّى كذلك الفِرْزان ويُترجم اسمه ترجمةً حرفية إلى الملكة ، لذلك يُرمَز له في التأشير الجبري بالرمز Q، كما تُستعمل الأيقونتان للإشارة إليه حسب اللون. تتضمن الصيغة الأصيلة للمسألة 8 وزراء على رقعة شطرنج قياسية (8×8)، لذلك تُسمَّى مسألة الوزراء الثمانية، كما تُسمَّى كذلك ترجمة حرفية من الإنجليزية مسألة الملكات.
علاوةً على ذلك، يتحرَّك الوزير أفقيًا وعموديًا وقطريًا عددًا غير محدود من المربعات جامعًا بين حركتي الفيل والرخ، لكن لا يمكن للوزير القفز فوق القطع التي تعترض سبيله، لذلك يوصف بأنه أقوى قطعة في الشطرنج. ويمكنه إماتة (أو أسر) أي قطعة أخرى للخصم تقع على أحد مساراته المحتملة فيخرجها من اللعب ويحتل مكانها في الرقعة. يُمكِن لوزير في رقعة فارغة قياسية أن يهاجم من 21 إلى 27 مربعًا من أصل 64 حسب موقعه، ويزداد عدد المربعات مع وجوده في مركز الرقعة.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟