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

مسألة الوزراء الثمانية أحجية شطرنج يُطلَب فيها وضع 8 وزراء على رقعة أبعادها 8×8 من غير أن يُميت أي منها الآخرين، وهذا يعني عدم وجود وزيرين في الوقت ذاته في: السطر نفسه، والعمود نفسه، والقطر نفسه، وثمة 92 حلًا لهذه المسألة.

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

مسألة الوزراء الثمانية حالة خاصة من مسألة الوزراء النونية التي يُطلب فيها وضع n وزريرًا على رقعة شطرنج مقاساتها n×n. لهذه المسألة حلول من أجل قيم n الطبيعية كلها ما خلا 2 و 3. عدد الحلول الدقيق معروف من أجل القيم دون 27 (n ≤ 27)، يكشف التحليل المقارِب أن نمو عدد الحلول وفقًا لقيم n هو (0.143 n)n.

 وصف المسألة 

الوزير قطعة شطرنج، تُسمَّى أيضًا الفِرْزان ويُترجم اسمه ترجمةً حرفية إلى الملكة ، لذلك يُرمَز له في التأشير الجبري بالرمز Q، كما تُستعمل الأيقونتان (20px، 20px) للإشارة إليه حسب اللون. تتضمن الصيغة الأصيلة للمسألة 8 وزراء على رقعة شطرنج قياسية (8×8)، لذلك تُسمَّى مسألة الوزراء الثمانية، كما تُسمَّى أيضًا ترجمة حرفية من الإنجليزية مسألة الملكات.

يتحرَّك الوزير أفقيًا وعموديًا وقطريًا عددًا غير محدود من المربعات جامعًا بين حركتي الفيل والرخ، لكن لا يمكن للوزير القفز فوق القطع التي تعترض سبيله، لذلك يوصف بأنه أقوى قطعة في الشطرنج. ويمكنه إماتة (أو أسر) أي قطعة أخرى للخصم تقع على أحد مساراته المحتملة فيخرجها من اللعب ويحتل مكانها في الرقعة. يُمكِن لوزير في رقعة فارغة قياسية أن يهاجم من 21 إلى 27 مربعًا من أصل 64 حسب موقعه، ويزداد عدد المربعات مع وجوده في مركز الرقعة.

تطلب مسألة الوزراء الثمانية وضع 8 وزراء على رقعة شطرنج قياسية (8×8) من غير أن يُميت أي منها الآخر. عُمِّمت هذه المسألة لتطلب وضع  وزيرًا على رقعة مُربَّعة نونية () من غير أن يُميت أي منها الآخر.

 نبذة تاريخية 

نشر ، وهو  أحجية الوزراء الثمانية سنة 1848م، ونشر فرانز ناوك أول حلٍ معروف لها سنة 1850م. عمَّم ناوك المسألة أيضًا لتشكل n وزيرًا على رقعة شطرنج أبعادها n×n، وشغلت هذه المسألة عددًا من أساتذة الرياضيات، كان من ضمنهم كارل غاوس.

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

 حل المسألة 
200بك|تصغير|حل المسألة بخوارزمية تعقب رجوعي.
يُمكن حل هذه المسألة بخوارزمية تعقب رجوعي لوضع الوزراء في المواقع المناسبة على الرقعة بالترتيب واحدًا واحدًا.

تبدأ الخوارزمية بالسطر الأول وبالعمود الأول: كلما وضع وزير في سطر يُنتقل إلى السطر التالي وتُفحص إمكانية وضع وزير فيه بدءًا من العمود الأول، وهكذا حتى إيجاد موقع للوزير في السطر، وإذا تعذَّر وضع وزير في ذلك السطر، يُرجَع للسطر السابق ويُحرَّك الوزير فيها عمودًا واحدًا وهكذا. يُولَّد الحل عند وضع وزير في آخر سطر بنجاح.

تصف الخوارزمية التالية حل مسألة الوزراء بخوارزمية تعقب رجوعي:

الخوارزمية السابقة منفذة بلغة سي++:

الخوارزمية السابقة منفذة بلغة جافا:

الخوارزمية السابقة منفذة بلغة بايثون:

 رقعة 8x8 
إيجاد كل حلول مسألة الوزراء الثمانية مُكلِف حسابيًا، ثمة 4,426,165,368 ترتيبًا مختلفًا للوزراء يلزم فحصه، منها 92 فقط تصلح حلًا للمسألة. لكن يُمكن تحسين الأداء بتقنيات حسابية تُجنِّب استعمال منهج البحث الشامل. يُمكن مثلًا خفض الاحتمالات المفحوصة بإقصاء كل الحالات التي تحوي أكثر من وزير في عمودٍ واحدٍ من غير فحصٍ، وهذا يجعل عدد التراتيب التي تحتاج فحصًا 16,777,216 أو 88، يُمكن أيضًا خفض الاحتمالات اللازم فحصها باستعمال التباديل اعتماًدا على فكرة أنه يوجد 8 حالات متاحة في العمود الأول، ثم 7 في الثاني (بعد إضافة الأول)، ثم 6 في الثالث بعد (إضافة الأول والثاني) ليصبح عدد الحالات اللازم فحصها 40,320 أو 8! فقط.

لمسألة الوزراء الثمانية 92 حلًا متمايزًا، ينتج أغلبها عن حلول أخرى بتدوير رقعة الشطرنج أو إيجاد انعكاسها، أما عدد الحلول الفريدة غير المرتبطة بعلاقات التناظر من دوران وانعكاس فهو 12 حلًا فقط، تُسمَّى الحلول الرئيسة.

لكل حلِّ من الحلول الرئيسة 8 تنويعات: الحل الرئيس نفسه وتدوير الرقعة 90° و°180 و°270 ثُمَّ عكس كل حلِّ من الحلول انعكاسًا مرآتيًا. يشذ الحل 12 عن سائر الحلول الآخرى بأن تدويره °180 يعيد إنتاج الحل الرئيس، لذلك فإن عدد تنويعاته الفريدة 4 فقط، وهذا يعني أن عدد الحلول الإجمالي: 11×8 + 1×4 = 92 حلًا.

الحل 10 له خاصية فريدة تميزه عن سائر الحلول: إذا نظر لرقعة الشطرنج على أنها شبكة مُصبَّعات فإنه .

 رُقَع مغايرة لـ 8x8 
 وجود الحلول 

يُمكن لخوارزميات البحث الشامل حساب عدد الحلول ضمن قدرات حسابية مقبولة حتى ، وتعجز عن حساب عدد الحلول عندما .

ثمة حلول للرُقَع n × n من أجل n ≥ 4، يُمكن بسهولة توليد أحد الحلول باتباع نمط خَطَوي درجي لمواقع الوزراء كما تظهر الأشكال التالية لرُقَع قيمة n فيها 8 و9 و10 على الترتيب:

يمكن توليد حل خَطَوي درجي على رقعة شطرنج n × n، فيها مُربَّع (j ،i)، أي يُوجد في العمود i والسطر j وفق الخوارزمية التالية:

بعض من الأمثلة:
 إذا كانت n = 8 (باقي القسمة 2)، ينتج الحل الرئيس 1.
 إذا كانت n = 14 (الباقي 2)، تكون القائمة: 2، 4، 6، 8، 10، 12، 14، 3، 1، 7، 9، 11، 13, 5.
 إذا كانت n = 15 (الباقي 3)، تكون القائمة: 4، 6، 8، 10، 12، 14، 2، 5، 7، 9، 11، 13، 15، 1، 3.
 إذا كانت n = 20 (الباقي 2)، تكون القائمة: 2، 4، 6، 8، 10، 12، 14، 16، 18، 20، 3، 1، 7، 9، 11، 13، 15، 17، 19، 5.

 عدد الحلول 
 العدد الدقيق 
لا تُعرَف صيغة رياضية لحساب عدد الحلول لمسألة الوزارء النونية. أحصي عدد الحلول الإجمالي من أجل ، يُظهر الجدول التالي عدد الحلول الرئيسة والإجمالية، أي التي تشمل التدوير والانعكاس، لمسألة الوزراء النونية من أجل قيم n الطبيعية دون 28 وفقًا لموسوعة المتتاليات الصحيحة على الإنترنت.
 n  الرئيسة  الإجمالية  n  الرئيسة  الإجمالية 1 1 1 2 0 0 3 0 0 4 1 2 5 2 10 6 1 4 7 6 40 8 12 92 9 46 352 10 92 724 11 341 2,680 12 1,787 14,200 13 9,233 73,712 14 45,752 365,596 15 285,053 2,279,184 16 1,846,955 14,772,512 17 11,977,939 95,815,104 18 83,263,591 666,090,624 19 621,012,754 4,968,057,848 20 4,878,666,808 39,029,188,884 21 39,333,324,973 314,666,222,712 22 336,376,244,042 2,691,008,701,644 23 3,029,242,658,210 24,233,937,684,440 24 28,439,272,956,934 227,514,171,973,736 25 275,986,683,743,434 2,207,893,435,808,352 26 2,789,712,466,510,289 22,317,699,616,364,044 27 29,363,495,934,315,694 234,907,967,154,122,528   

يُعرَف أيضًا عدد الحلول التي  من أجل قيم .

 العدد التقريبي 

ثَبُت رياضيًا أن عدد حلول مسألة الوزراء من أجل قيم كبيرة لـ n مساوٍ تقريبًا للقيمة: ، أو يساوي بدقة  التالي:

وفيه  ثابتٌ قيمته بين 1.939 و1.945 وo(1) يُمثِّل تدوين o الصغرى .

 مسائل ذات صلة 
تصغير|200بك|رقعة شطرنج ثلاثية الأبعاد (8×8×8)
أبعاد أعلى
تُطرَح المسألة نفسُها في الشطرنج بأبعاد أعلى من 2، مثلًا تكون الرقعة مُكوَّنة من مكعَّب طول ضلعه n، كما يمكن وضع عدد أكثر من الوزراء في الأبعاد أعلى من 2، مثلًا يُمكِن وضع 4 وزراء في فضاء ثلاثي الأبعاد 3×3×3.
بقطع أخرى مغايرة للوزير

يُمكن طرح المسألة بقطع أخرى من الشطرنج، فعلى رقعة قياسية أبعادها (8×8) يُمكن وضع 32 حصانًا و 14 فيلًا و16 ملكًا و8 رخاخ. وضع الأحصنة سهل، ويكفي وضعها على المربعات من لون واحد على الرقعة، لأنها تتحرك فقط إلى مربعٍ مغاير لونًا للمربع الذي تقف فيه. أما الملوك، فتُقسَم الرقعة أولًا إلى 16 مربعًا كبيرًا (2×2) في كل منها 4 مربعات صغيرة ملونة، ثم يُوضَع الملك في أحد هذه المربعات في الصغيرة في المربعات الكبرى كلها. أما وضع 8 رخاخ على الرقعة فيمكن تمثيله مصفوفة تبديلية أبعادها 8×8.
الهيمنة
 تسأل هذه الأحجية عن عدد الهيمنة، وهو عدد القطع الأدنى اللازم وضعه على الرقعة لإماتة أي قطعة عليها، يُمكن مثلًا الهيمنة على رقعة شطرنج (8×8) بوضع 5 وزراء فقط.
الوزراء وقطع أخرى
يُطلَب في هذه المسألة وضع عدد من الوزراء مع عدد من قطع أخرى على رقعة الشطرنج من غير أن يُميت أي منها الآخرين. يُمكن مثلًا طلب وضع m وزير وm حصان على رقعة (n×n)، أو طلب وضع عدد من الوزراء والبيادق من غير أن يُميت أحدها الآخرين.
إتمام مسألة وزراء نونية
هذه المسألة حالة خاصة من المسألة الوزراء النونية، يُعلم فيها موقع عدد من الوزراء على رقعة n×n، ويُطلَب إيجاد مواقع سائر الوزراء على الرقعة من غير أن يُميت أي منها الآخرين.

 التطبيقات 
تصغير|180بك|حل مشكلة الوزراء الثمانية بخوارزمية إصلاح تكراري: تبدأ الخوارزمية بثمانية وزراء على الرقعة بوضع ابتدائي ما.
إيجاد كل حلول مسألة الوزراء الثمانية تحدٍ بسيط ولكنه ليس سهلًا بالوقت نفسه، لهذا تُستعمل هذه المسألة لطرح أمثلة عن تقنيات برمجة متنوعة وتعليمها، منها مثلًا برمجة منطقية والخوارزميات الوراثية، ويُمكن أيضًا طرح هذه المسألة عند الحديث عن الخوارزميات العودية. وعندها تُفحص الاحتمالات بتتبع الحلول في أجزاء من الرقعة: وحدانية الوزير بالأعمدة والقطرين عادةً، وصولًا إلى الرقعة كاملة.

من التقانات التي يُمكن أن تستعمل مسألة الوزراء لتوضيحها: خورازمية الإصلاح التكراري، وهي خوارزمية جشعة تبدأ من وضعية يوجد فيها كل الوزراء على الرقعة، أي 8 وزراء على رقعة 8 × 8 مثلًا مع وجود وزير في كل عمود. ثم تحاول الخوارزمية تحسين مواقع الوزراء بتفضيل المواقع التي يكون عدد الإماتات فيها أقل ما يمكن في كل عمود. مع أن هذه الخوارزمية لا تضمن الوصول إلى حلٍ دومًا من أجل أي وضع ابتدائي للوزراء، إلا أنها قد تجد حلولًا لأبعاد كبيرة جدًا للرقعة، مثلًا مليون وزير على رقعة مليونية الأبعاد.

 انظر أيضًا 







 هوامش 

 المراجع 
 فهرس الإحالات 
المنشورات
بالعربية

بالإنجليزية

الوب
بالعربية

بالإنجليزية

 ثبت المراجع 
المقالات المُحكَّمة
بالإنجليزية














الكتب
بالعربية




بالإنجليزية





 وصلات خارجية 
 مسألة الوزراء على موقع عالم الرياضيات.
 حل مسألة الوزراء بأكثر من 100 لغة برمجة.

تصنيف:مسائل رياضيات مرتبطة بالشطرنج
تصنيف:توافيقيات تعدادية
تصنيف:الشطرنج في 1848
تصنيف:مسائل رياضيات