قام عالم رياضيات من جامعة هارفارد بحل مشكلة شطرنج ملحمية عمرها 150 عامًا

(هايدي والي / Unsplash)

على مستوى واحد ، تبدو لعبة الشطرنج وكأنها لعبة بسيطة: 64 مربعًا فرديًا أسود أو أبيض ، و 16 قطعة لكل جانب ، ومنافسان يسعىان إلى الغزو.

ومع ذلك ، ابحث بشكل أعمق قليلاً ، وتقدم اللعبة إمكانيات معقدة بشكل لا يصدق ، مما يشكل تحديات لمنظري الشطرنج وعلماء الرياضيات التي يمكن أن تظل دون حل لعقود أو حتى قرون.

في يوليو 2021 ، تم حل أحد هذه التحديات أخيرًا - على الأقل ، إلى حد ما. عالم الرياضيات مايكل سيمكين ، من جامعة هارفارد في ماساتشوستس ، وضع ما في ذهنه مشكلة n-queens كان هذا الأمر محيرًا للخبراء منذ أن تم تخيله لأول مرة في أربعينيات القرن التاسع عشر.

إذا كنت تعرف لعبة الشطرنج الخاصة بك ، فأنت تعلم أن الملكة هي أقوى قطعة على اللوحة ، وقادرة على تحريك أي عدد من المربعات في أي اتجاه. تسأل مشكلة n-queens هذا: مع عدد معين من الملكات (n) ، كم عدد الترتيبات الممكنة حيث تكون الملكات متباعدة بدرجة كافية بحيث لا يمكن لأي منهما أن يأخذ أيًا من الملكات الأخرى؟

بالنسبة لثماني ملكات على لوحة قياسية 8 × 8 ، فإن الإجابة هي 92 ، على الرغم من أن معظمها يتم تدويرها أو عكسها في متغيرات من 12 حلًا أساسيًا فقط.

لكن ماذا عن 1000 ملكة على لوح يساوي 1000 × 1000 مربع؟ ماذا عن مليون ملكة؟ حل سيمكين التقريبي للمشكلة هو (0.143 ن)ن- عدد الملكات مضروبًا في 0.143 ، مرفوعًا إلى أس n.

ما تبقى لديك ليس هو الإجابة الدقيقة ، لكنه أقرب ما يمكن الحصول عليه الآن. مع وجود مليون ملكة ، يظهر الرقم في صورة عدد مكون من خمسة ملايين خانة بعده - لذلك لن نعيد إنتاجه لك هنا.

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

إذا أخبرتني أنني أريدك أن تضع ملكاتك بطريقة كذا وكذا على السبورة ، فسأكون قادرًا على تحليل الخوارزمية وإخبارك بعدد الحلول التي تتطابق مع هذا القيد ، يقول سيمكين .

'من الناحية الرسمية ، فإنه يقلل من المشكلة إلى مشكلة التحسين.'

في وقت مبكر ، كان سيمكين وزميله زور لوريا يعملان في المعهد الفيدرالي السويسري للتكنولوجيا في زيورخ تعاونت على تباين في مشكلة n-queens تُعرف باسم المشكلة الحلقية أو المعيارية. في هذا الشكل ، تلتف الأقطار حول اللوح ، بحيث يمكن للملكة أن تتحرك قطريًا بعيدًا عن الحافة اليمنى للوحة وتعاود الظهور على اليسار ، على سبيل المثال.

يمنح هذا كل ملكة تناظرًا للهجوم ، لكن ليس هذا هو الكيفية التي تعمل بها رقعة الشطرنج العادية: فالملكة الموجودة في زاوية اللوحة ليس لديها العديد من زوايا الهجوم مثل تلك الموجودة في المركز.

في النهاية ، الزوج العمل على المشكلة الحلقية المتوقفة (على الرغم من أنهم نشروا بعض النتائج) ، لكن انتهى سيمكين بتكييف بعض ثمار هذا العمل في حله النهائي.

مع زيادة حجم المجالس وزيادة عدد الملكات ، أظهر البحث أنه في معظم التكوينات المسموح بها ، تميل الملكات إلى التجمع على طول جوانب اللوحة ، مع وجود عدد أقل من الملكات في الوسط ، حيث يتعرضن للهجوم. تتيح هذه المعرفة اتباع نهج أكثر ترجيحًا.

من الناحية النظرية ، يجب أن تكون الإجابة الأكثر دقة على لغز n-queen ممكنة - لكن Simkin جعلنا أقرب من أي وقت مضى ، وهو سعيد بنقل التحدي إلى شخص آخر لمزيد من الدراسة.

أعتقد أنني قد انتهيت شخصيًا من مشكلة n-queens لفترة من الوقت ، ليس لأنه لا يوجد أي شيء آخر أفعله بها ولكن لمجرد أنني كنت أحلم بالشطرنج وأنا مستعد للمضي قدمًا في ذلك. حياتي،' يقول سيمكين .

ورقة Simkin حول الحل متاحة على خادم ما قبل الطباعة arXiv .

من نحن

نشر حقائق تقارير مستقلة ومثبتة عن الصحة والفضاء والطبيعة والتكنولوجيا والبيئة.