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

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

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

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

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

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

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

الباقي ليس هو الإجابة الدقيقة ، ولكن أقرب ما يمكنك الحصول عليه الآن. مع وجود مليون ملكة ، يتضح أن هذا الرقم يتكون من خمسة ملايين رقم – لذلك لن نقوم بإعادة إنشائه هنا من أجلك.

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

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

“من الناحية الرسمية ، هذا يقلل من المشكلة إلى مشكلة التحسين.”

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

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

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

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

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

“أنا شخصياً أعتقد أنه يمكنني إنهاء مشكلة N-Queens لفترة من الوقت ، ليس لأنه ليس لدي المزيد لأفعله ، ولكن لأنني كنت أحلم بالشطرنج ، وأنا مستعد للمضي قدمًا. حياتي أيضًا.” يقول سيمكين.

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