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

تتضمن

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

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

الرياضيات

، فلا يزال بإمكانك القيام بعمل جيد في لعبة السودوكو .

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

يعد تاريخ السودوكو الطويل والمثير للإعجاب لغزًا بحد ذاته ، وكلمة sodoku هي كلمة يابانية الأصل وتتألف من الأحرف

اليابانية

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

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

إن

عالم الرياضيات

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

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

النقش

الذي أطلق عليه ألبريشت دورر اسم “Melencolia” منذ بداية القرن السادس عشر .

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

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

صمم السودوكو الحديث من قبل هوارد جارنز ،

المهندس المعماري

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

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

نُشرت الرسالة الأولى إلى التايمز عن سودوكو في 13 نوفمبر من إيان باين من برينتفورد ، واشتكى من أن

اللغز

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

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

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

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

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

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

الحلول التقليدية

واضحة تماما وهي :

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

– يجب أن يتطابق مجموع جميع الأرقام الموجودة في أي وحدة تساعية أو صف أو عمود مع الرقم الصغير المطبوع في زاويته .

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

تقنية المسح

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

– مسح الصف ومعرفة الأرقام الناقصة فيه، وبذلك تكون هذه هي الاحتمالات الأساسية.

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

– مسح المربع لاستبعاد وضع احتمال لأي رقم موجود في هذا المربع

– تتبقى مجموعة احتمالات تشتمل على الحل الصحيح الذي يتم الوصول إليه في النهاية مع المهارة التالية .

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

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

– عند تواجد احتمال بين الاحتمالات الغير متوفر في الصف أو العمود ذاته فهذا يجعله الاحتمال الصحيح .

– إذا تكررت الاحتمالات فلابد من دراسة باقي الخلايا حتى يتم التوصل للاحتمالات الأقل.

– لابد أن نبدأ من الصف والعمود والمربع الذي يتضمن أقل نقص في الأرقام.

– لابد أن نبدأ من الخلية التي تتضمن احتمال واحد وهو الحل الأكيد لها.

– مع كل حل يتم تثبيته لابد أن يتم حذفه من الاحتمالات الرصاصية في كل من صفه وعموده ومربعه.