كيفية حل؟ سودوكو، نظرية الرسم البياني والمسائل المفتوحة في الرياضيات

في دراسة نشرت في مجلة الجمعية الرياضية الأمريكية، استخدم الباحثون أدوات من نظرية الرسم البياني لتحليل ألغاز سودوكو بشكل منهجي واكتشفوا أن سودوكو تؤدي إلى مشاكل غير محلولة في نظرية الرسم البياني

حل لغز سودوكو. الأرقام باللون الأسود هي البيانات.

هل سبق لك أن حاولت حل سودوكو، وفجأة سيطر عليك شعور باليأس: "ربما ليس لها حل؟". وحتى لو وجدت الحل، كيف يمكنك أن تعرف أنه الحل الوحيد؟ ماذا لو كنت قد كتبت قبل نصف ساعة 5 بدلاً من 3، ربما كنت ستصل إلى حل مختلف تمامًا؟

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

في إطار التوراة، "الرسم البياني" هو مصطلح لمجموعة من النقاط (أو العقد) المرتبطة بأجزاء (تسمى الأقواس). تُسمى الرسوم البيانية أحيانًا أيضًا "الشبكات". يمكنك التفكير في 81 مربعًا في أحجية سودكو، على أنها 81 عقدة في الرسم البياني. علاوة على ذلك، سيتم تمثيل كل رقم من الأرقام من 1 إلى 9 بلون مختلف: 1 سيكون أحمر، 2 أزرق، 3 أخضر، وهكذا؛ لذلك تحصل كل عقدة على لون، تمامًا كما تحتوي كل فتحة على رقم. هنا، قمنا بإنشاء تمثيل رسومي لسودوكو، دعنا نسميه "سودوكو الرسم البياني". إذا كان في لغز سودوكو، يوجد مربعان في نفس الصف، أو نفس العمود، أو نفس المربع 3 × 3، فسيتم رسم قوس بين العقدتين اللتين تمثلهما. نظرًا لأنه وفقًا لقواعد سودوكو، لا يوجد رقمان متماثلان في نفس الصف أو العمود أو المربع 3x3، ولا توجد عقدتان من نفس اللون متصلتين. (مثال سيساعد في توضيح المعنى. لنفترض أننا خصصنا اللون الأحمر للرقم 1. إذا كانت عقدتين باللون الأحمر متصلتين ببعضهما البعض، فهذا يعني أن هناك مربعين (هما العقد) مع الرقم 1) (وهو اللون الأحمر) في نفس الصف أو في نفس العمود أو داخل نفس المربع بحجم 3 × 3 (لأننا هكذا عرفنا الاتصال باستخدام القوس)، وهذا ممنوع حسب قواعد سودوكو).

في نظرية الرسم البياني، يسمى تلوين الرسم البياني بحيث لا توجد أقواس بين العقد من نفس اللون "التلوين المناسب". ولذلك، يحاول محبو سودوكو في جميع أنحاء العالم توسيع الرسم البياني الملون جزئيًا (يحتوي اللغز الأصلي على مربعات فارغة، أي عقد غير ملونة) إلى رسم بياني ملون بالكامل.

من خلال هذا التشابه بين الرسوم البيانية وألغاز سودوكو، تمكن هيرزبرج ومورتي من استخدام الأدوات الرياضية من نظرية الرسم البياني لإثبات النظريات حول سودوكو. على سبيل المثال، أثبتوا أن عدد الطرق لتوسيع الرسم البياني الملون جزئيًا يُعطى بواسطة كثير الحدود. إذا كانت قيمة كثير الحدود هي 0 في لغز سودوكو معين، فلن يكون للغز حل، وإذا كانت قيمة كثير الحدود هي 1، فهناك حل واحد، وهكذا. اختبار آخر أثبته الثنائي، ويمكن للقارئ أن يؤديه بنفسه: لغز سودوكو معين سيكون له حل فريد فقط إذا ظهرت ثمانية أرقام على الأقل من التسعة (1-9) في اللغز. إذا ظهرت سبعة أرقام فقط من الأرقام التسعة، فسيكون للغز حلين محتملين على الأقل. وهنا وصلنا إلى مشكلة مفتوحة في الرياضيات: "سيكون من الرائع معرفة الظروف التي يمكن فيها توسيع الرسم البياني الملون جزئيًا إلى لون فريد [مناسب]"، كما كتب هيرزبرج ومورتي.

بعض الألغاز أكثر صعوبة من غيرها، والأصعب منها يحتوي على عدد كبير من المربعات الفارغة. "ما هو الحد الأدنى لعدد المربعات المعطاة، والذي يضمن أن الكلمات المتقاطعة لها ترتيب يؤدي إلى حل فريد؟" أعطى هيرزبيرج ومورتي مثالاً على لغز الكلمات المتقاطعة مع حل فريد، حيث تم إعطاء 17 مربعًا. ولذلك، فإن الحد الأدنى للعدد سيكون أقل من أو يساوي 17. ولكن ما هو الحد الأدنى للعدد؟ لا أحد يعرف ذلك. قد تعتقد أن لغز الكلمات المتقاطعة الذي يحتوي على عدد أكبر من المربعات المعطاة لديه فرصة أكبر لحل واحد. الأمر ليس كذلك؛ أعطى هيرزبيرج وموريتي مثالاً على الكلمات المتقاطعة مع حلين محتملين، حيث يوجد 29 مربعًا.

وإذا كنت تتساءل متى سينفد مخزون سودوكو الخاص بصحيفتك المحلية، يقول الباحثون إن هناك حوالي 5.5 مليار من ألغاز سودوكو المختلفة - وهو ما يكفي لإبقاء عشاق سودوكو حول العالم مشغولين لفترة طويلة.

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

مقالة مربعات سودوكو ومتعددات الحدود اللونية يمكن الاطلاع على نسخة عبر الإنترنت على موقع إعلانات AMS.