العلم وراء لعبة سودوكو
العلم وراء لعبة سودوكو(*)
لا يتطلب حلُّ إحدى أحجيات لعبة سودوكو الاستعانة بعلم الرياضيات، ولا حتى بعلم الحساب.
ومع ذلك، تطرح هذه اللعبة عددا من المسائل الرياضياتية المثيرة.
<P.J.ديلاهاي>
قد يتوقع المرء أنّ لعبة تتطلب استعمال المنطق، لا تستهوي سوى عددٍ جدّ قليل من الناس ـ ربما كانوا رياضياتيين أو من هواة الحواسيب أو من المقامرين المحترفين. بيد أن لعبة سودوكو Sudoku اكتسبت خلال مدة قصيرة جدا شعبية استثنائية، مذكِّرة بالهوس الذي أثاره مكعب رُوبِكْ Rubik’scube في مطلع الثمانينات من القرن الماضي.
وخلافا لمكعب روبك الثلاثي الأبعاد، فإن أحجيةَ سودوكو شبكةٌ مستوية مربّعةُ الشكل. تحوي، نموذجيا، 81 خلية (تسعة أسطر وتسعة أعمدة)، ثم إنها مقسمة إلى تسعة مربعات جزئية، يتضمن كل منها تسع خلايا، سنسمّيها شبكات جزئية subgrids. وتبتدئ اللعبة بأعداد مطبوعة في بعض الخلايا، وعلى اللاعب ملء الخلايا الفارغة الأخرى بأعداد من 1 إلى 9، بحيث لا يظهر رقمٌ مرتين في نفس السطر أو العمود أو الشبكة الجزئية. ولكل أحجية حل وحيد.
ومع أن لعبة سودوكو لعبةُ أعداد، من المثير للعجب أنه لا يحتاج من يحاول حلها إلى أيَّ قدْر من الرياضيات. وفي الحقيقة، لا تساعد أيٌّ من العمليات الحسابية ـ من ضمنها الجمع أو الضرب ـ على إتمام شبكة ما، إذ إن كل ما هو مطلوب، نظريا، ملء الشبكة بأي مجموعة من تسعة رموز مختلفة (حروف، ألوان، أيقونات، وهلم جرا). ومع ذلك، تطرح سودوكو على الرياضياتيين وعلماء الحاسوب مجموعة من المسائل التي تتسم بالتحدي.
شجرة العائلة(**)
بيد أن ثمة شيئا صار معروفا؛ ألا وهو جذور اللعبة. فَسَلَفُ سودوكو، ليس كما يُظَنّ على نطاق واسع، المربعَ السحريَّ ـ وهو مصفوفة تتصف بأن لجميع الأعداد الصحيحة، الموجودة في أيِّ سطر وأيّ عمودٍ وأيّ قطرٍ من المصفوفة، المجموع نفسه. وفي الحقيقة، فإذا استثنينا الأعداد والشبكة، فلا وجود تقريبا لشيء يربط سودوكو بالمربع السحري ـ لكن ما هو وثيق الصلة بسودوكو هو المربع اللاتيني(1) [انظر الإطار في الصفحة 24].
والمربعُ اللاتينيُّ من المرتبة(2) n هو مصفوفة مكونة من n2 خلية (n خلية في كل جانب) مملوءة برموزٍ عددها n، بحيث لا يظهر الرمز نفسه مرتين في السطر نفسه أو في العمود نفسه (وهكذا يُستَعمل كل واحد من هذه الرموز n مرّة بالضبط). ويعود أصل هذه الشبكات إلى القرون الوسطى؛ وفي وقت لاحق، سماها عالم الرياضيات <L.أولر> (1707-1783) المربعات اللاتينية، وانكبّ على دراستها.
|
نظرة إجمالية/ الجانب العلمي في لعبة سودوكو(***) سودوكو هي أكثر من مجرد لعبة منطق مسلّية، فهي، إضافة إلى ذلك، تطرح على الرياضياتيين مجموعة واسعة من المسائل العميقة. تتضمن هذه المسائل ما يلي: كم شبكة سودوكو يمكن تكوينها؟ ما هو أصغر قدر من أعداد البدء التي تسمح بحل وحيد؟ هل تنتمي سودوكو إلى صنف المسائل الصعبة التي يُطلق عليها اسم المسائل التامة NP. تَوصَّل خبراء الأحجيات إلى مجموعة من الأساليب تساعد على حل أحجيات سودوكو وإلى أشكال مختلفة مسلية من هذه اللعبة. |
تشبه لعبة سودوكو العادية مربعا لاتينيا من المرتبة التاسعة، ولا تختلف عنه إلاّ بمتطلب إضافي هو أن تحوي كلُّ شبكة جزئية الأعداد من 1 إلى 9. وكان الظهور الأول لهذه اللعبة في عدد الشهر 5/1979 من المجلة Dell Pencil Puzzles and Word Games. وفي بحث أجراه <W.شُورْتْز> [المشرف على زاوية الكلمات المتقاطعة في مجلة New York Times] ذكر أن مبتكر هذه اللعبة هو مهندسٌ معماريٌّ متقاعد اسمه <H. گارنز>. وقد مات <گارنز> في إنديانابوليس ـ والروايات مختلفة في تاريخ وفاته، إذ إن بعضها يذكر أنه توفي عام 1989وبعضها الآخر عام 1981 ـ وحدثت وفاته قبل أن يشهد النجاح العالميَّ لاكتشافه بمدة طويلة.
وقد انتقلت اللعبةُ، التي نُشِرَتْ في المجلة Dell بعنوان «موقع عدد»(3)، إلى مجلة يابانية عام 1984، أطلقت عليها، في النهاية، اسم «سودوكو» Sudoku، الذي هو ترجمة غير دقيقة لِ«أعداد مفردة»(4). هذا وقد أدخلت المجلةُ الاسمَ «سودوكو» في سجل العلامات التجارية، لكنّ محبِّي التقليد في اليابان أطلقوا عليها اسم «موقع العدد». بعد ذلك، وفي مفارقة أخرى تتصل بسودوكو، سمّى اليابانيون الأحجية باسمها الإنكليزي، وأطلق عليها المتكلمون بالإنكليزية اسمَها اليابانيَّ.
وتعزو سودوكو الفضل في نجاحها اللاحق إلى <W.گولْد> ـ وهو قاض متقاعد من هونگ كونگ يهوى المشي والتجوال ـ كان اطّلع على اللعبة مصادفة خلال زيارة قام بها إلى اليابان عام 1997، وكتب برنامجا حاسوبيا يولِّد شبكات سودوكو بطريقة آلية، وفي أواخر عام 2004 قبلت صحيفة التايمز اللندنية اقتراحه بنشر أحجيات فيها. وفي الشهر 1/2005، حذت صحيفة Daily Telegraphحذوها. ومنذ ذلك الحين شرعت عدة دستات من الصحف اليوميّة، التي تصدر في جميع أنحاء العالم، في نشر هذه اللعبة، حتى إن بعض الصحف صار يشير إليها على صفحة غلافها لتعزيز ترويجها. وقد برزت مجلات وكتب مخصصة لهذه الأحجية المسلية، وخُصِّصَتْ لها مسابقات ومواقع على الوِبWeb.
إن التحدي الذي يواجهك هو إدخال عدد يقع بين 1 و 9 في كل خلية، دون أن تكرِّر أيا من هذه الأرقام في نفس السطر أو العمود أو الشبكة الجزئية (المربع 3x3). إن حلول أحجية سودوكو المتوسطة الصعوبة، المعروضة في وسط هذه الصفحة، وكذلك حلول الأحجيات الأخرى الواردة في هذه المقالة، موجودة في الموقع www.sciam.com، وفيه أيضا أحجيات إضافية. |
شبكات بعدد الكائنات البشرية(****)
لم يتأخر الرياضياتيون بالشروع في طرح مسألة «كم عدد»(5) شبكات لعبة سودوكو. فمثلا، طرحوا بسرعة السؤال عن عدد الشبكات المملوءة بطريقة صحيحة، وسموها «شبكات الحل»(6). وبالطبع، فإن هذا العدد يجب أن يكون أصغر من عدد المربعات اللاتينية، وذلك بسبب التقييدات الإضافية المفروضة على الشبكات الجزئيّة.
يوجد 12 مربعا لاتينيا فقط من المرتبة 3 و576 من المرتبة 4، لكنْ هناك5,524,751,496,156,842,531,225,600 مربع لاتيني من المرتبة 9. إلا أن نظرية الزمر(7)تنص على أن الشبكة التي يمكن اشتقاقها من أخرى هي مكافئة للشبكة الأصلية. فعلى سبيل المثال، إذا قُمْتَ منهجيا بالاستعاضة عن كل عدد بعدد آخر (مثلا: 1 أصبح 2 و2 أصبح 7، وهكذا)، أو إذا بادلت بين سطرين أو عمودين، فإن النتائج النهائية ستكون بالضرورة نفسها. لذا فإذا أحصينا الصيغ المختزلة فقط، أصبح عدد المربعات اللاتينية من المرتبة التاسعة مساويا377,597,570,964,258,816. وهذه نتيجة وردت عام 1975 في كتاب Discrete Mathematics، الذي ألفه <E.S.بامِّلْ> و<J.روثْسْتَايْنْ> [اللذان كانا حينذاك في جامعة أوهايو الحكوميّة].
أما تحديد عدد شبكات سودوكو الممكن تشكيلها، فمسألة يصعب جدا حلها. وفي هذه الأيام، فإن الاقتصار على استعمال المنطق (لتبسيط المسألة) والحواسيب (لتفحُّص الإمكانات بطريقة منهجية)، يسمح بتقدير عدد شبكات حل سودوكو الصحيحة وهو 6,670,903,752,021,072,936,960. ويتضمن هذا العدد جميع تلك الشبكات التي اشتُقّتْ من أي شبكة خاصة باستعمال العمليات الابتدائية. هذا وإن صحة هذه النتيجة ـ التي توصّل إليها <B.فلكنهاور> [من جامعة درسدن التقنية بألمانيا] و <F.جارفيس> [من جامعة شفيلد بإنكلترا] جرى تحقّقها عدة مرات. (التحقق مهم في الحالات التي يجري الحصول فيها على النتائج بهذه الطريقة.)
وإذا أحصينا مرة واحدة فقط تلك الشبكات التي يمكن اختزالها إلى تشكيلات متكافئة(8) تقلَّصَ عددُها إلى 5,472,730,538 وهذا عدد أصغر قليلا من عدد سكان الأرض. وعلى الرغم من هذا الانخفاض، فمازال العدد كبيرا، وعلى المتحمسين لسودوكو ألاّ يخشوا أي نقص في الأحجيات.
|
أسلاف اللعبة سودوكو(*****) شبكة سودوكو هي نوع خاص من المربع اللاتيني. المربعات اللاتينية ـ التي أَطْلَقَ عليها اسمَها <L.أولر> [أحدُ كبار علماء رياضيات القرن الثامن عشر] ـ هي مصفوفات nxn مملوءة بـ n عددا مختلفا. بحيث لا يظهر العدد نفسه مرتين في السطر نفسه أو العمود نفسه. والمربعان المعروضان هما مثالان على ذلك. وشبكة سودوكو المكمَّلة المألوفة [التي تسمى، أيضا، شبكة حل] هي مربع لاتيني9×9 يحقق شرطا إضافيا، هو أن يَحوي كلٌّ من شبكاته الجزئية التسع الأرقام من 1 إلى 9.
مربع لاتيني، يمثل أيضا شبكةَ سودوكو مُكَمَّلة [n = 9]
ليونارد أولر |
لاحِظ أنه يمكن التوصل إلى حلٍّ كامل لسودوكو بأكثر من طريقة أيا كانت شبكة البدء (أي الشبكة غير الكاملة التي لها حل كامل مفروض). ولم يفلح أحدٌ حتى الآن في تحديد عدد شبكات البدء المختلفة. يضاف إلى ذلك أن شبكة البدء في سودوكو لا تثير حقا اهتماما رياضياتيا إلا إذا كانت أصغرية minimal ـ أي إذا كان حذف عدد واحد يعني أن الحل لم يعد وحيدا. هذا ولم يستطع أحد حتى الآن، تعيين عدد الشبكات الأصغرية الممكنة، الذي قد يرقى إلى العدد الإجمالي لأحجيات سودوكو المختلفة. ويمثل تعيين هذا العدد تحديا من المؤكد التصدي له في المستقبل القريب.
ثمة مسألة أخرى تتعلق بالأصغرية minimality لم تحلّ أيضا بعد، ألا وهي: ما هو أصغر عدد من الأرقام التي يمكن لمصمم أحجية وضْعها في شبكة بدء، ويضمن مع ذلك، حلا وحيدا لها؟ يبدو أن الجواب هو 17. فقد جمّع <G.رُويْل> [من جامعة ويسترن ـ أستراليا] أكثر من 000 38 مثال يحقق هذا الشرط، بحيث لا يمكن الانتقال من واحد منها إلى آخر بإجراء العمليات الأولية.
وحاليا، يُجري < G.ماك كوِيْر> [من جامعة إيرلندا الوطنية في ماي نوث] بحثا عن أحجية شبكةُ بدئها تحوي 16 عددا ولها حل وحيد؛ لكنْ حتى الآن لم يوفّق في مساعيه. ومن ناحية أخرى، تمكّن رويل وآخرون، يعمل كل منهم بمعزل عن الآخر، من إيجاد أحجية واحدة شبكة بدئها تحوي 16 عددا ولها حلان اثنان. ولم يعثر الباحثون حتى الآن على أمثلة إضافية.
تُرى، هل ثمة أحد قريب من البرهان على عدم وجود أحجية سودوكو صحيحة شبكة بدئها تحوي 16 عددا فقط؟ يجيب <ماك كوير> عن هذا السؤال بقوله: «لا». وهو يلاحظ أنه لو تمكّنا من تحليل شبكة واحدة كلَّ ثانية بحثا عن أحجية صحيحة شبكةُ بدئها تحوي 16 عددا، «فبمقدورنا إنجاز هذا العمل في173 سنة. ولسوء الحظ، فما نزال غير قادرين على هذا العمل، حتى لو استعنّا بحاسوب سريع.» ويضيف: «قريبا، ربما يكون بالإمكان البحث في شبكة واحدة خلال دقيقة واحدة بالاستعانة بحاسوب قوي، لكن إجراء المحاولة بهذه السرعة يَستغرق 380 10 سنة؛ ثم يقول: «حتى لو وزعنا العمل على 000 10حاسوب، لَتَطَلَّبَ إنجازه نحو سنة. لذا نحن بحاجة إلى تقدم هائل بحيث نجعل البحث في جميع هذه الشبكات شيئا مقبولا. فما نحتاج إليه إما تصغير فضاء البحث، وإما إيجاد خوارزمية للبحث أفضل بكثير.»
إن الرياضياتيين يعرفون فعلا حلّ عكس مسألة تحديد التعداد الأصغري لأعداد شبكة البدء، أي الإجابة عن السؤال: ما هو أكبر تعداد لأعداد شبكة البدء لا يضمن حلا وحيدا؟ الجواب هو 77. فبتعدادات مثل: 80، 79 أو 78 لمجموعات شبكات البدء، إذا وُجد حل، كان هذا الحل وحيدا. لكن هذا لا يمكن تأكيده عندما يكون تعداد الأعداد المفروضة 77 [انظر الإطار في أسفل الصفحة 28].
(******)الحل بالاستعانة بالحواسيب
إضافة إلى الأسئلة المتعلقة بالتعداد، يفكر علماء الرياضيات والحاسوب مليّا فيما تَقْدِر ولا تَقْدِر، على فعله الحواسيب عندما يتعلق الأمر بحل أحجيات سودوكو أو توليدها. وفي أحجيات سودوكو المألوفة (9×9)، من السهل نسبيا كتابة برامج حاسوبية لحلّ جميع شبكات البدء الصحيحة.
|
ما هو مقدار التخفيض الذي يمكنك تحقيقه؟(*******) يبدو أن أصغر عدد من الرموز التي يمكن لأحجية سودوكو9×9 البدء بها، والتي توفر شبكة حل وحيدة، هو 17 . ونبين أدناه مثالا على ذلك. وإحدى الشبكات الخاصة المملوءة، التي ينعتها هواة سودوكو بأنها مألوفة بصورة مستغربة (Strangely Familier (SF ، تخفي29 رقعة غير متكافئة، على كل منها17 رمزا (عددا) ابتدائيا – وهذا عدد كِبَرُهُ غير عادي. وقد اعتبرت الشبكات SF في وقت سابق أنها أكثر الشبكات احتمالا لتصميم أحجية ذات 16 رمزًا ابتدائيا، ولها حل وحيد، لكن بحثا مستفيضا عنها خيب هذا الأمل. ونبين أدناه أحجية سودوكو الوحيدة التي تنطلق من 16 رمزا (عددا)، والتي لها حلان فقط،ونرى في الشبكات الجزئية النهائية تبادلا بين الأعداد8 والأعداد 9.
|
يمكن للبرامج الحاسوبية استعمال عدة أساليب، لكن أكثرها انتشارا هو النهج المعاكس backtracking، وهو صيغة منهجية لطريقة المحاولة والخطأ، تسمح باقتراح حلول جزئية، ثم القيام بإجراء تعديلات طفيفة عليها حالَ اكتشاف خطأ هذه الحلول.
وطريقة عمل الخوارزمية الأساسية للنهج المعاكس هي كما يلي: يضع البرنامجُ العددَ 1 في أول خلية فارغة، فإذا كان هذا الخيار منسجما مع الأعداد الموجودة في الشبكة، انتقل إلى الخلية الفارغة الثانية التي يضع فيها العدد 1. وعندما يواجه تعارضا conflict (وهو ما يمكن حدوثه بسرعة كبيرة)، يمحو العددَ1 الذي وضعه أخيرا، ويجرب 2 أو 3 إذا واجه 2 تعارضًا، وهكذا… وبعد وضع أول عدد ممكن (لا يواجه تعارضا)، ينتقل البرنامج إلى الخلية التالية، ويبدأ ثانية بالعدد 1.
| مسألة اخرى : ما هو اصغر عدد من الارقام التى يمكن وضعها في شبكة بدء بحيث يكون الحل وحيدا ؟ |
وإذا كان العدد الذي يتعين تغييره 9 (وهو عدد لا يمكن أن يضاف إليه 1 في شبكات سودوكو المألوفة 9×9)، فإن البرنامج يقوم بالنهج المعاكس ويزيدُ العددَ الموجودَ في الخلية السابقة (التي تلي آخر عدد جرى وضعه) واحدًا. بعد ذلك يتقدم البرنامج إلى الأمام إلى أن يواجه تعارضا. (أحيانا، يتبع البرنامج نهجا معاكسا عدة مرات قبل التقدم إلى الأمام). وفي برنامج مكتوبٍ جيدا، يَستكشف هذا الأسلوب جميع الفرضيات الممكنة، وينتهي بالعثور على الحل، إن وُجِدَ حل فعلا. وإذا كانت هناك عدة حلول، كما يحدث في أحجية مغلوطة، فإن البرنامج يجدها جميعا.
|
أساليب الحل(********) نورد هنا بضعَ طرائقَ لمحاولة حلِّ إحدى أحجيات سودوكو. الطريقتان1 و 2 هما أبسط الطرق وتُستعملان عادة ترادفيا (إحداهما بعد الأخرى). ولكن، لسوء الحظ، هاتين الطريقتين لا تساعدان دائما اللاعب على قطع مسافة طويلة من الحل، لذا فهو يستعمل الطريقة 3، وإذا تبين أن ذلك غير كاف، فمن الممكن استعمال الطريقة 4 التي تنجح كل مرة، من دون أن يكون تطبيقها سهلا بالضرورة. ويمكنك، أيضا، انتهاج أساليبَ من ابتكارك، وتجريبَ الطرائقِ الكثيرةِ المعروضة على الوِب.
الطريقة 2 الطريقة 3 فمثلا، تُبيّن الشبكة c كيف تبدو الشبكة a إذا عُلِّمَتْ من دون تفكير، من دون أن تُطَبَّقَ أولا الطريقتان 1 و 2. في العمود الثالث، يَكون ترتيبُ إمكانات الخلايا الثانية والثالثة والرابعة والخامسة والسادسة، هو على التوالي: {7,6,3,2}، {9,6,3}، {2,6}، {2,6}، {7,6}. ويجب أن يحوي هذا العمود العدد 2 والعدد 6، لذا يجب أن يكون هذان العددان موجودين في الخليتين اللتين إمكاناتهما فقط العددان 2 و 6 الموجودان في الترتيب الأول {7,6,3,2}. لذا فإن 2 و 6لا يمكن أن يوجدا في أي مكان آخر في هذا العمود ويمكن استبعادهما من خلايا العمود الأخرى [الحمراء]. وهكذا يُبَسَّطُ مدى الإمكانات لهذا العمود لتصبح {7,3}، {9,3}، {6,2}، {6,2}، {7}. لكن هذا ليس كل شيء. فتحديد موقع 7 يُملي بدوره موقعَ 3 وموقعَ 9 [الترتيب الثاني 3}،{9]. والإمكانات الأخيرة هي: {3}، {9}، {6,2}، {6,2}، {7}. ويبقى ارتياب وحيد في معرفة أين يجب أن يكون موقعا 2 و 6. والقاعدة العامة لتبسيط الإمكانات هي التالية: إذا وَجَدْتَ، ضمن مجموعة من الإمكانات [لسطر أو عمود أو خلية جزئية]، m خلية تحتوي على مجموعة جزئية مؤلفة من m عددا فقط [لكن ليس من الضروري وجودها جميعا في كلّ خليّة]، فإن الأرقام الموجودة في المجموعة الجزئية يمكن استبعادها، بوصفها إمكانات، من الخلايا الأخرى في المجموعة التي هي أكبر منها. وعلى سبيل المثال، يمكن في d تبسيط الترتيب {3,2} ، {3,1}، {5,4,2,1} ليصبح {3,2}، {3,1}، {2,1}، {5,4}، {7,5} لأن الخلايا {3,2}، {3,1}، {2,1} تَنْتُجُ جميعُها من المجموعة الجزئية{3,2,1} وليس فيها أعداد أخرى. الطريقة 4 ولسوء الحظ، يتعيّن عليك أحيانا القيامُ بعدةِ جولاتٍ من المحاولة والخطأ، وعليك أن تكون مستعدا لتطبيق النهج المعاكس إذا كان تخمينُك غيرَ صحيحٍ. وفي الحقيقة، فإنّ الفكرة الكامنة في طريقة المحاولة والخطأ، هي الفكرة نفسها التي تستعملُها خوارزمياتُ النهج المعاكسِ، التي يمكن للحواسيب تطبيقُها بسهولة، لكنها تسبب إرهاقا لأدمغة الناس. ومن المثير للعجب أن تكون الطرائقُ، التي أثبتت أنها أكثر الطرائق فعالية لآلة، هي الأقلّ فعاليّة للكائنات البشرية. |
وبالطبع، فإن التحسينات ممكنة، وهي تُسرِّعُ اكْتشاف الحلِّ الوحيد. ويسمّى أحد التحسينات المفضّلة: «التوليد المقيد»، الذي يعني أنه بعد وضع كل عدد جديد، يولّد البرنامجُ قائمة بالأعداد الممكنة المتبقية في كل خلية فارغة، ولا يتعامل إلاّ مع الأعداد الواردة في القائمة.
يمكن تكويد encode تقنيات النهج المعاكس ببرنامج حلول قصيرة إلى حد ما. وفي الحقيقة، كُتِبَتْ برامجُ مختصرة للعبة سودوكو في Prolog، وهي لغة حاسوبيّة تَستعمل خوارزميّةَ نهج معاكس. وقد ابتكرت هذه اللغةَ في أواخر السبعينات بجامعة مارسيليا في فرنسا.
وفيما يتعلق بلاعبي سودوكو، فإن تقنيات النهج المعاكس، التي تطبقها البرامج الحاسوبية، غير عملية؛ لأنها تستلزم صبرا استثنائيا. لذا يَستعمل الناس قواعدَ أكثر تنوعا وبراعة، وهي أقرب ما تكون إلى أسلوب المحاولة والخطأ كملاذ أخير. وتحاول بعض البرامج تقليدَ الطرائق التي يسلكها الناسُ إلى حد ما؛ فمع أنها أطول من البرامج الأخرى، لكنها تعمل بنفس مستوى جودتها. هذا وإن البرامج التي تحاكي التفكير البشري مفيدة أيضا لتقييم تعقيد شبكاتِ البدء، التي تتدرج صعوبتها من شبكات «سهلة» (لا تتطلب سوى تكتيكات بسيطة)، إلى ما يُطلِق عليها كثير من الناس اسمَ الشبكات «الشيطانية»(9) (بسبب حاجتها إلى تطبيق قواعد منطقية تُجهد أذهان مستعمليها).
إحدى الطرق التي يفكر في اتباعها علماء الحاسوب لحل أحجية سودوكو هي النظر إليها كمسألة تلوين بيان(10) graph-coloring problem، حيث لا يمكن أن يكون فيها لخليتين متجاورتين (تسميان أحيانا «رأسين مشتركين بحافة») اللون نفسه، والتي يكون فيها عدد الألوان المتاحة تسعة. ويحتوي الرسم، في هذه الحالة، على 81 رأسا vertex، بعضها ملون بداية. إن مسألة التلوين هي في واقع الأمر معقدة جدا لأن لكل شبكة 9×9 مئات من الحافات edges. فكل خلية هي جزء من سطر يحتوي ثمانيَ خلايا أخرى، ومن عمود يضم ثمانيَ خلايا أيضا، ومن شبكة جزئيّة تضمّ ثمانيَ خلايا (أربعة منها سبق حسابها في سطر الخلية وعمودها). لذا فإن كل خلية من الخلايا الإحدى والثمانين ترتبط بعشرين (4+8+8) خلية أخرى، وهذا يكوّن مجموعا ضخما من الخلايا قدره 1620 (أي 20مضروبا في 81) خلية تشترك بحافة مع أحد جيرانها ـ وهذا يعني، بدوره، أن العدد الإجمالي للحافات هو 810 (أي 1620 مقسوما على 2).
وإمكان تحويل أحجيات لعبة سودوكو إلى مسألةِ تلوينٍ، له دلالة عند العلماء، لأن هذه السّمة تربط هذه الأحجيات بنوع من المسائل المهمة. ولا سيما فقد أثبت حديثا، <T.ياتو> و <T.سيتا> [من جامعة طوكيو] أن أحجية سودوكو تنتمي إلى طائفة المسائل التامة (NP(11، وهي من المسائل التي يُحْتَمَل أن يستحيل حلّها في إطارٍ زمنيّ واقعيّ. ومن الأمثلة المشهورة عليها مسألة الألوان الثلاثة التي تدرس ما إذا كان بالإمكان تظليل كلِّ عقدة node في بيان(10)بثلاثة ألوان، بحيث لا يكون لأي عقدتين مشتركتين بحافة واحدة اللون نفسه. وفي حالة سودوكو، من الواضح أن التحدي المستحيل هو تصميم برنامج فعّال يسمح بحلّ أحجية سودوكو من جميع الحجوم ـ أي عندما تكون الشبكة من الحجم n2Xn2، من دون أن تكون مقصورة على الحجم المألوف . 9×9) 32 x 32) ومن المرجح أن لن ينجح أيُّ برنامجٍ لحلّ هذه الأحجيات نجاحا حقيقيّا، لأن الزمن اللازم لإيجاد الحل يتزايد تزايدا دراميا مع تزايد n.
وإذا كان لديك خوارزمية تحلّ أحجيات سودوكو المعهودة، فيمكنك استعمالها للحصول على خوارزمية لتصميم تلك الأحجيات المتعلقة بسودوكو من جميع الحجوم. وفي الحقيقة، فمع أن الأحجيات كانت تُصَمَّمُ في بدايات عهدها يدويّا، فإن جميعها تقريبا يُنَفَّذ في هذه الأيام ببرامج حاسوبية استنادا إلى الطريقة التالية أو إلى ما يشبهها: توضع الأعداد عشوائيا على رقعة الشبكة وتُطبَّق خوارزميةُ حلٍّ (النهج المعاكس، مثلا). فإذا كان للأحجية حل وحيد، توقف البرنامج. وإذا لم يكن للمسألة المكمَّلةِ جزئيَّا حلٌّ، حُذِفَ عددٌ واحد من التشكيل الابتدائي، واستُهلَّ البرنامجُ ثانية. وإذا كان للأحجية حلول مختلفة، اختير أحدُها، وعندئذ تضيف الخوارزميةُ القدرَ اللازمَ من الأعداد إلى أعداد البدء للتوثق من وحدانية الحل المختار.
| يمكن تحويل احجيات لعبة سودوكو الي مسألة تلوين تربط هذه اللعبة بنوع من المسائل الرياضية المهمة |
استراتيجيات بشرية (*********)
يمكن للهواة الذين يستمتعون بحل أحجيات سودوكو يدويّا أن يختاروا من بين الكثير من التكتيكات، بيد أن ثمة أسلوبين أساسيين يوفران نقطة بدء مقبولة. أولهما البحث عن أكثر الخلايا الفارغة تقييدا، وهي تلك التي تنتمي إلى سطر مملوء جيدا أو عمود مملوء جيدا أو شبكة جزئية مملوءة جيدا. وأحيانا، يقودك حذف المستحيلات (الأعداد التي تملأ الخلايا في نفس السطر أو العمود أو الشبكة الجزئية) إلى اكتشاف العدد الوحيد الملائم لخلية معينة. وعلى أيّ حال، يجب أن يسهمَ هذا الأسلوبُ في تضييقٍ شديدٍ للخيارات.
|
تغيرات في أحد المواضيع(**********) هل ثمة حاجة إلى شيء أكثر من شبكات شيطانية؟ في الأحجيات الواردة هنا يمكن تطبيق القواعد العادية، مع بعض التغييرات. ففي a تَحِلُّ حروف الكلمتين GRAND TIME محلَّ الأعداد، ويُستعاض عن الشبكات الجزئية المربعة بأشكال هندسية أخرى. مبتكر هذه الشبكة يسميها أحجيةDu-Sum-Oh. وفي b، التي تحوي ست شبكات جزئية مثلثة الشكل، من الممكن تقاطع الأسطر والأعمدة المائلة في مركز الشكل، ثم إنه عندما يكون لسطرٍ أو عمودٍ ثماني خلايا فقط، تقوم الخلية القريبة، التي تشكّل رأسا «للنجمة»، مقام الخلية التاسعة. وفيc يكون للأعداد الثلاثة في الأسطر المعلّمة (بإشارتي + ، =) في الشبكتين الجزئيتين مجموعٌ يساوي العدد الموجود في الشبكة الجزئية الثالثة. وفي d، تدلّ إشارتا «أكبر من» و «أصغر من» على المواقع التي تنتمي إليها الأرقام. وفي e، يجب وضع أحجار الدومينو الموجودة في الأسفل في الأمكنة الفارغة. وفي f، تتراكب ثلاث رقع للَّعب بعضها على بعض. وللاطلاع على الحلول ومزيد من اللُّعب، قم بزيارة للموقعwww.sciam.com
|
الأسلوب الثاني هو البحث عن المكان الملائم لقيمة مفروضة في عمود معين أو سطر معيّن أو شبكة جزئية معينة (مثلا، ابْحثْ عن الأمكنة الوحيدة التي قد تكون ملائمة للعدد 3 في السطر الرابع). وأحيانا، يكون لهذا البحث إجابة وحيدة ممكنة. وفي أحيان أخرى، فإن مجرد معرفةِ أنّ العددَ 3 ليس ملائما إلاّ لموقعين معينين أو ثلاثة مواقع، هي معرفة مفيدة. ولمزيد من التفصيلات، انظر الإطار في الصفحتين 26 و 27. أيضا، قم بزيارة المواقع على الوِب المدرجة في «مراجع للاستزادة» للعثور على عدد من الاستراتيجيات لبعضها أسماء مثيرة مثل swordfish (سمك سيف البحر) وgolden chain (السلسلة الذهبية).
وثمة عدد من البرامج الحاسوبية، التي يمكن العثور عليها بسهولة على الإنترنت، تولّد رُقعا ذات درجة محدَّدة من الصعوبةِ، وتساعدك على إيجاد الحلول (ولكن، بالطبع، من دون أن تَحُلَّ الأحجيةَ التي تسعى لحلها!). فمثلا، يسمح لك بعضها بوضع علامات مؤقتة في الخلايا ومحوها، وهذا يجعل القلم والممحاة غير ضروريين. حتى أن بعضها الآخر يمكّنك من إيجاد روابط بين الخلايا. فلا تُغفل هذه البرامج الحاسوبية، إذ بإعفائها لك من بعض الممارسات المملّة، مثل المحو، فهي تحثّك على مزيد من التفكير العميق والبراعة الفنية الفائقة في لعبةِ المنطق هذه.
وحال شعورك بالضجر والملل من أحجيات لعبة سودوكو المعهودة، يمكنك الانتقال إلى البحث عن أنماط مطوّرة لهذه اللعبة لا تعدّ ولا تُحصى، بعضها يحوي عدة شبكات متراكبة، وبعضها الآخر يستعيض عن الشبكات الجزئية، التي هي مربعة، بأخرى لها أشكال مغايرة؛ ومنها ما يفرض تقييدات إضافية. وستحظى هذه البدائل بإعجابك، ذلك أنها تجبرك على استكشافِ استراتيجيات منطقية جديدة. يُضافُ إلى ذلك أن المتحمسين، الذين لا يُمضُون أكثر من ربع ساعة في حلّ أحجية معهودة، يقضون سحابة يومهم كلّه في الاستمتاع بجمع الخلايا والأعداد لإنشاء نماذج ضخمة من أحجيات سودوكو. والآن يكفي ما قيل، ولننتقل إلى الشبكة التالية!
|
رموز قليلة جدا(***********) إن77 رمزا لن تكفي بالضرورة لإيجاد حل وحيد. فمع وجود أربع فقط من الخلايا الفارغة فإن لهذه الشبكة حلين. هذا وإن العددين 1 و 2 غير الموجوديْن في أول عموديْن من الشبكة قابلان للمبادلة.
|
المؤلف
Jean – Paul Delahaye
أستاذ علوم الحاسوب في جامعة ليل للعلوم والتقانة بفرنسا، وباحث في مختبر ليل لعلوم الحاسوب [LIFT] التابع للمركز الوطني للأبحاث العلمية [CNRS]. تتركز أبحاثه على نظرية اللُّعَبِ الحاسوبية [مثل معضلة السجين المكررة(12)]، نظرية التعقد(13) [مثل التعقد الكولموگروکي(14)]، وتطبيقات هاتين النظريتين في التحليل الجينيّ، وحديثا في علم الاقتصاد. وهذه المقالة هي تفصيل لمقالة نشرها ديلاهاي في عدد الشهر 12/2005 من مجلة Pour la Science، وهي الترجمة الفرنسية لمجلة ساينتيفيك أمريكان.
مراجع للاستزادة
1st World Sudoku Championship:www.wsc2006.com/eng/index.php
Math Games.Ed Pegg,Jr.:www.maa.org/editorial/mathgames/mathgames_09_05_05.html
The Mathematics of Su Doku.Sourendu Gupta:http://theory.tifr.res.in/~sgupta/sudoku/Mathematics of Sudoku.Tom Davis:
SadMan Software Sudoku techniques:www.simes.clara.co.uk/programs/sudokutechniques.htm
sudoku, an overview: www.sudoku.com/howtosolve.htm
sudoku, form Wikipedia:http://en.wikipedia.org/wiki/Sudoku
A Variety of Sudoku Variants: www.sudoku.com/forums/viewtopic.php?t=995
(*) THE SCIENCE BEHIND SUDOKU
(**) Family Tree
(***) Overview/ Scientific Sudoku
(****) As Many Gride as Humans
(*****)Sudoku’s Predecessors
(******) Computer Solvers
(*******) How Low Can You Go?
(********) Solution Methods
(*********) Human Strategies
(*********)Variations on a Theme
(**********) Too Few Clues
(1) Latin square.
(2) order
(3) number place
(4) single numbers
(5) how many.
(6) solution grids
(8) أي إذا أحصينا عدد صفوف تكافؤ مجموعة الشبكات ( التحرير )
(9) disbolical
(10) graph أو مِبْيان، وهو بنية بيانات لها عدد من العقد nodes وعدد من الحافات edges تربط أزواجا من هذه العقد
(11) NP-complete problems، انظر: «حدود البحث عن سبب»،العلوم ، العددان3/7 (2006) ، ص 11.
(12) iterated prisoner’s dilemma
(13) complexity theory
(14) Kolmogorov complexity
