عالم رياضيات يكسر مشكلة شطرنج عمرها 150 عامًا

بالعربي/ ظهرت المشكلة لأول مرة في عام 1869.
تم حل مشكلة الشطرنج التي حيرت علماء الرياضيات لأكثر من 150 عامًا.
بدأت مشكلة n-queens باعتبارها لغزًا أبسط بكثير ، وتم طرحها لأول مرة في عدد 1848 من صحيفة الشطرنج الألمانية Schachzeitung بواسطة ملحن الشطرنج Max Bezzel. سألت عن عدد الطرق التي يمكن من خلالها وضع ثماني ملكات منافسات – وهي أقوى القطع على رقعة الشطرنج وقادرة على تحريك أي عدد من المربعات أفقيًا وعموديًا وقطريًا – على لوحة قياسية من 64 مربعًا دون أن تهاجم أي ملكة أخرى.
الجواب ، الذي تم الكشف عنه بعد عامين فقط ، كان أن هناك 92 تكوينًا أبقت الملكات الثماني عن حلق بعضهن البعض ، مع كون جميع الحلول باستثناء 12 منها عبارة عن دورات بسيطة وانعكاسات لبعضها البعض. لكن في عام 1869 ، سأل عالم الرياضيات فرانز ناوك تكرارًا أكثر إرباكًا للمسألة: بدلاً من تكوين ثماني ملكات على لوحة قياسية 8 × 8 ، ماذا عن 1000 ملكة على لوحة 1000 × 1000؟ ماذا عن المليون أو حتى المليار؟
ما كان في يوم من الأيام لغزًا بسيطًا نسبيًا أصبح مشكلة رياضية أعمق بكثير – مشكلة تتطلب اكتشاف قاعدة عامة لعدد طرق وضع أي عدد (يُشار إليه بـ “n”) من الملكات على لوحة n-by-n .
الآن ، توصل مايكل سيمكين ، عالم الرياضيات في مركز العلوم الرياضية والتطبيقات بجامعة هارفارد ، إلى إجابة شبه نهائية.
على لوحة ضخمة من n-by-n ، هناك تقريبًا (0.143n) ^ n طرق لوضع n ملكات بحيث لا يمكن لأي منها مهاجمة بعضها البعض. هذا يعني أنه على لوحة بمليون بمليون ، فإن عدد التكوينات غير الخطرة التي يمكن ترتيب مليون ملكة فيها هو تقريبًا 1 متبوعًا بـ 5 ملايين صفر.
استغرق Simkin ما يقرب من خمس سنوات للعثور على هذا التقريب الوثيق للمعادلة. عادةً ما يحل علماء الرياضيات المشكلات عن طريق إيجاد طرق لتقسيمها إلى أجزاء أكثر قابلية للإدارة. ولكن نظرًا لأن الملكات التي توضع بالقرب من مركز اللوحة يمكنها مهاجمة المربعات أكثر بكثير مما يمكن للملكات عند الحواف ، فإن مشكلة n-queens غير متكافئة للغاية – وبالتالي فهي مقاومة للتبسيط بعناد.
بالتعاون مع Zur Luria ، عالم رياضيات في المعهد الفيدرالي السويسري للتكنولوجيا في زيورخ ، قام سيمكين في البداية بتبسيط المهمة من خلال التفكير في نسخة أكثر تناسقًا “حلقيًا” من المشكلة ، حيث تلتف مربعات الحافة حول السبورة لتشكيل شكل دائري . يتيح هذا الترتيب للملكات الاختفاء في أعلى اليسار والعودة للظهور في أسفل اليمين ، على سبيل المثال. وهذا يعني أيضًا أنه بغض النظر عن مكان وضعهم ، يمكن لكل ملكة مهاجمة نفس عدد المربعات مثل نظيراتها.
باستخدام اللوح الحلقي كتقريب أولي ، طبق عالما الرياضيات بعد ذلك استراتيجية تسمى “خوارزمية الجشع العشوائي” على المشكلة. وضعوا ملكة بشكل عشوائي ، وسدوا كل المربعات التي هاجموها ؛ ثم يتم اختيار الملكة التالية للجلوس على البقع المتبقية ، مع إغلاق المربعات الهجومية بدورها. استمر الزوجان في القيام بذلك عبر تكوينات متعددة حتى وجدا حدًا أدنى تقريبيًا – أو أقل رقم ممكن – على عدد تكوينات n ملكات على لوح حلقي.
لكن تقديرهم كان بعيدًا عن الكمال. منعتهم الطبيعة الملتفة للوحة من العثور على مواضع الملكة القليلة الأخيرة في بعض التكوينات. بعد إسقاط المشكلة لبضع سنوات ، عاد الثنائي إليها بفكرة تكييف الخوارزمية الخاصة بهما على لوحة عادية ، والتي وفرت المزيد من أماكن الاختباء للملكات النهائية أكثر من اللوحة الحلقية. من خلال تكييف خوارزمية الجشع العشوائي مع لوحة قياسية غير حلقية ، قام الزوج إلى حد ما بتحسين دقة هذا التقدير المنخفض الحد.
لكن إجابتهم لم تكن واضحة تمامًا كما كانوا يأملون – تعمل خوارزمية الجشع العشوائية بشكل أفضل على المشكلات المتماثلة ، حيث يوفر كل مربع لوحة نفس ميزة الهجوم مثل أي مربع آخر. هذا ليس هو الحال بالنسبة للوحة القياسية ، حيث تتمتع مربعات الحافة بقدرة أقل على الهجوم من المربعات الموجودة في الوسط.
لحل هذه المشكلة ، أدرك سيمكين أنه سيحتاج إلى تكييف الخوارزمية. نظرًا لأن معظم التكوينات القابلة للتطبيق على السبورة القياسية تحتوي على عدد أكبر من الملكات عند حواف اللوحة – حيث هاجموا عددًا أقل من المربعات – مقارنةً بمركزها ، فقد صقل سيمكين الخوارزمية العشوائية الجشعة عن طريق ترجيح المربعات. بدلاً من خوارزمية تعيين الملكات بشكل عشوائي ، فإنه يضع ملكات بشكل تفضيلي في المواقع التي من شأنها أن تتفرع إلى أكبر عدد من التكوينات الممكنة. سمح هذا لسيمكين بالتركيز على عدد الملكات التي ستشغل كل قسم من أقسام اللوحة والعثور على صيغة لعدد صالح من التكوينات ، وبالتالي تحسين دقة التخمين الأقل حدًا بشكل أكبر.
“إذا كنت تريد أن تخبرني ،” أريدك أن تضع ملكاتك بطريقة كذا وكذا على السبورة “، فسأكون قادرًا على تحليل الخوارزمية وإخبارك بعدد الحلول التي تتطابق مع هذا القيد ، وقال سيمكين في بيان . “من الناحية الرسمية ، فإنه يقلل من المشكلة إلى مشكلة التحسين.”
لكن إيجاد الحد الأدنى لعدد لا يزال يترك مجموعة لا نهائية من الأعداد أكبر من ذلك. للوصول إلى الحل حقًا ، احتاج سيمكين لإيجاد حد أعلى. لحل هذا النصف الثاني من المشكلة ، لجأ إلى استراتيجية تسمى “طريقة الانتروبيا” ، والتي تتضمن تدوين عدد المربعات التي لم تتعرض للهجوم بعد وضع ملكة جديدة على السبورة. باستخدام هذه الطريقة ، أنتج معادلة الحد الأقصى التي تبصق رقمًا يطابق تقريبًا رقم حده الأدنى ؛ خلص سيمكين إلى أنه قد ضرب الصيغة بالفعل على وشك الانتهاء.الإعلانات
قد يحاول العمل المستقبلي تقريب الحدين من بعضهما البعض ، لكن سيمكين ، بعد أن اقترب أكثر من أي شخص قبله ، يرضى بترك هذا التحدي لشخص آخر للتغلب عليه.
قال سيمكين: “أعتقد أنني قد انتهيت شخصيًا من مشكلة n-queens لفترة من الوقت”. “ليس لأنه لا يوجد أي شيء أفعله به ، ولكن فقط لأنني كنت أحلم بالشطرنج وأنا مستعد للمضي قدمًا في حياتي.”
نشر Simkin عمله ، الذي لم يخضع بعد لمراجعة الأقران ، إلى قاعدة بيانات ما قبل الطباعة arXiv .
المصدر/ livescience.comالمترجم/barabic.com
يجب أنت تكون مسجل الدخول لتضيف تعليقاً.