تكنولوجيا

خوارزمية حل السودوكو

لعبة السودوكو” تتألف من 81 خلية، ويتم تخصيص الأرقام من 1 إلى 9 في هذه الخلايا بشكل متكرر، حيث يتم تكرار كل رقم تسع مرات بالضبط. على الرغم من أن لعبة السودوكو تبدو صعبة بسبب وجود الأرقام فيها، إلا أنها في الواقع لا تعتمد على الرياضيات، فحتى إذا كنت تعتقد أنك ضعيف في الرياضيات، فلا يزال بإمكانك أن تؤدي جيدا في لعبة السودوكو .

أصل كلمة سودوكو

يعتبر تاريخ السودوكو طويلا ومثيرا للإعجاب بحد ذاته، وكلمة sodoku هي كلمة يابانية الأصل وتتألف من الأحرف اليابانية Su (التي تعني الرقم) و Doku (بمعنى مفرد)، ولكنه لم يتم اختراعه في اليابان، بل نشأ في سويسرا وانتقل إلى اليابان عن طريق أمريكا .

مؤسس لعبة السودوكو

اخترع العالم الرياضي السويسري ليونارد يولر (1707-1783) هذا اللغز في سنواته الأخيرة، وأطلق عليه اسم `المربع اللاتيني`، ولكن من غير المعروف كيف حصل ليونارد على تلك الفكرة .

مع ذلك، فإن مفهوم السودوكو قد ظهر منذ فترة أطول بكثير، حيث ظهرت لغز مشابه في النقش الذي أطلق عليه ألبريشت دورر اسم “Melencolia” في بداية القرن السادس عشر .

تُعرف هذه الألغاز باسم `المربعات السحرية`، وفي هذه المربعات يكون مجموع الأرقام في الأعمدة والصفوف والقطرين متماثلًا .

تأسيس السودوكو بمفهومه الحديث

تم تصميم سودوكو الحديث من قبل هوارد جارنز، المهندس المعماري المتقاعد البالغ من العمر 74 عاما ومبتكر الألغاز المستقلة من ولاية إنديانا، وتم نشره لأول مرة في مجلات ديل في عام 1979، وتوفي جارنز في عام 1989 قبل أن يحصل على فرصة لرؤية هذه اللعبة تنتشر حول العالم كظاهرة .

تم نشر اللغز في عام 1986 من قبل شركة الالغاز اليابانية نيكولي ، تحت اسم سودوكو ، في عام 1997 ، رأى قاض متقاعد من هونغ كونغ يدعى وين جولد في أوائل الخمسينات من عمره لغز سودوكو في مكتبة يابانية ، على مدى ست سنوات ، قام بتطوير برنامج كمبيوتر لإنتاج الألغاز بسرعة ، وقد قام بالترويج لسودوكو في التايمز في بريطانيا ، التي أطلقتها في 12 نوفمبر 2004 .

تم نشر الرسالة الأولى إلى صحيفة التايمز في 13 نوفمبر من قبل إيان باين من برينتفورد. اشتكى في الرسالة من أن لغز سودوكو حال دون ركوبه للقطار. في الولايات المتحدة، كانت The Conway Daily Sun (نيو هامبشاير) أول صحيفة تنشر لغز سودوكو بواسطة وين جولد في عام 2004 .

رياضيات سودوكو

الشبكة المكتملة لسودوكو هي نوع خاص من المربع اللاتيني مع خاصية إضافية، حيث لا تحتوي على قيم متكررة في أي من الوحدات التسع من الخلايا 3 × 3 المتجاورة. أصبحت العلاقة بين النظريتين معروفة تماما الآن، بعد أن أثبت دينيس بيرتييه في كتابه (The Hidden Logic of Sudoku) في مايو 2007 أن الصيغة من الدرجة الأولى صالحة لسودوكو إذا كانت صالحة فقط للمربعات اللاتينية .

تم نشر أول حساب معروف لعدد شبكات حل السودوكو الكلاسيكية بحجم 9 × 9 على مجموعة rec.puzzles في USENET في سبتمبر 2003، وكانت النتيجة تساوي 6،670،903،752،072،936،960.

سر حل لغز السودوكو

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

– يمكن أن يحتوي كل صف وعمود ووحدة تساعد على وضع رقم واحد (عادةً من 1 إلى 9) فقط .
يجب أن يتطابق مجموع جميع الأرقام الموجودة في أي وحدة تساعية أو صف أو عمود مع الرقم الصغير المطبوع في زاوية الوحدة .

تقنيات لحل السودوكو

تقنية المسح

من الممكن تحديد الاحتمالات الرقمية التي يجب كتابتها في الفراغات، أي أنه يمكن معرفة الأرقام المفقودة ومكان وضعها بحيث يتم الحصول على أقل عدد من الاحتمالات الممكنة، ويمكن القيام بذلك عبر القيام بالأمور الثلاثة التالية بالترتيب الذي تختاره:

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

تقنية استبعاد الاحتمالات

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

إذا كان هناك احتمال غير متوفر في الصف أو العمود ذاته، فإن ذلك يجعله الاحتمال الصحيح .
– إذا تكررتْ الاحتمالاتُ فلابدَّ من دراسةِ باقي الخلايا حتى يتمَّ التوصلُ للاحتمالاتِ الأقلِّ.
يجب أن نبدأ في العمل من الصف والعمود والمربع الذي يحتوي على أقل عدد من الأرقام الناقصة.
يجب البدء بالخلية التي تحتوي على احتمال واحد وهو الحل الصحيح لها.
بعد كل حل يتم تثبيته، يتم حذفه من الاحتماليات الرصاصية في كل من صفه وعموده ومربعه.

المراجع

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى