قواعد سودوكو
في ألعاب Sudoku ، الشبكة الكلاسيكية المكونة من تسع قفص تتكون من 9 × 9 = 81 خلية ، وكذلك تشكل 3 × 3 = 9 شبكات صغيرة تسع قفص. مطلوب لملء الأرقام 1 ~ 9 في 81 خلية صغيرة ، ولا يمكن تكرار الأرقام في كل صف وعمود وكل شبكة صغيرة من تسع قفص.
مهارات سودوكو
أفكاري
تصميم الحل والتنفيذ
يتم استخدام صفيف ثنائي الأبعاد فقط لتخزين مخطط Sudoku ، ويتم استخدام صفيف أحادي البعد كمكدس ، ويتم استخدام المتغير المنطقي كتعرف على التراجع.
1. تعريف متغير:
مشكلة var = [// هذا هو مسألة الصعوبة 10.7 المذكورة في الكتاب [8،0،0،0،0،0،0،0] ، [0،0،0،3،0،0،0،0،0،0] ، [0،7،0،0،0،0،0،0،0،0،0] [0،0،0،0،0،5،7،0،0،0] ، [0،0،0،1،0،0،0،3،0] ، [0،0،0،0،0،0،0،6،8] ، [0،0،0،8،5،0،0،0،0،0. = [] ، العلم = خطأ ؛
2. تحديد فعالية الخطة:
يتم استخدام ميزة التجزئة لكائنات JavaScript بالكامل. من أجل تسهيل تصحيح الأخطاء ، تكون قيمة إرجاع الوظيفة 0 عندما تكون صالحة ، وهناك ثلاث حالات عندما تكون غير صالحة: الصراع في الصف ، وصراع العمود ، وتزوير الشبكة المكونة من تسعة أجزاء ، والذي يعود 1 و 2 و 3 على التوالي. لقد استخدمته في الحكم المبكر ، وأضفت لاحقًا الحكم ذي الإطار العشرين ذي الصلة. لم تعد هذه الوظيفة تستخدم عند البحث عن الإجابة.
الوظيفة checkValid (sudo) {let subudo = {} // متغير مساعد مستخدم لتحديد ما إذا كانت الشبكة التاسعة تتعارض مع (Let I = 0 ؛ i <9 ؛ i ++) {let row = {} ، col = {} // auxiliary variable المستخدمة لتحديد الأعمدة والأعمدة (let 0 ؛ sudo [i] [j] ، cur2 = sudo [j] [i] // متغير معتمد من الصف والعمود في نفس الوقت إذا كان (cur1]) // ظهر العنصر الحالي في الصف ، وتم تحسين حكم الصفر. عندما يكون المفتاح 0 ، تكون القيمة 0 ، ولا يلزم حكم إضافي. العودة 1 ؛ // إرجاع رمز خطأ else row [cur1] = cur1 // لا يظهر العنصر الحالي في الصف ويتم تخزينه في المتغير الإضافي إذا (col [cur2]) // يشبه حكم العمود الصف. تم تحسين حكم الصفر. عندما يكون المفتاح 0 ، تكون القيمة 0 ، وليس هناك حاجة إلى حكم إضافي. العودة 2 ؛ آخر العقيد [cur2] = cur2 ؛ اسمحوا key = math.floor (i/3)+'-'+math.floor (j/3) // يتم إنشاء المفاتيح المختلفة لشبكات مختلفة تسع عميل إذا تم تحسين (key [key]) {// حكم الصفر بالفعل ، ويتم تحسين حكم الصفر. عندما تكون المفتاح 0 ، تكون القيمة 0 ، وليس هناك حاجة إلى حكم إضافي إذا (المفتاح الفرعي [المفتاح] الشبكة وحفظ العنصر الأول في IT Subudo [Key] [cur1] = cur1}}} return 0 ؛ // يمكن للبرنامج تشغيل هذا ، مما يشير إلى أن الخطة صالحة} 3. تحديد الفئة العشرين ذات الصلة المبدأ هو نفس الحكم العام ، ويكذب أبرز ما في وضع الشبكة الصغيرة المكونة من تسع قفص. الوظيفة check20grid (sudo ، i ، j) {Let row = {} ، col = {} ، subudo = {} // متغير العرض لـ (Let k = 0 ؛ k <9 ؛ k ++) {let cur1 = sudo [i] ، cur2 = sudo [k] [j] إذا (cur1) عندما يكون المفتاح 0 ، تكون القيمة 0 ، وليس هناك حاجة إلى حكم إضافي إذا كان (ROW [CUR1]) عائد 1 ؛ // إرجاع رمز خطأ olle [cur1] = cur1 // لا يظهر العنصر الحالي في الصف ، ويتم تخزينه في المتغير الإضافي} إذا كان (cur2) {// حكم العمود يشبه الصف. تم تحسين حكم الخسارة الصفر. القيمة هي 0 عندما يكون المفتاح 0. لا توجد حاجة إلى حكم إضافي إذا كان (COL [CUR2]) عائد 2 ؛ آخر العقيد [cur2] = cur2 ؛ } // إحداثيات متغير حلقة التحويل إلى الشبكة التاسعة LET KEY = sudo [Math.Floor (i/3)*3 + Math.Floor (k/3)] [Math.Floor (j/3)*3 + Math.Flo (K ٪ 3)] تم تحسين حكم الخسارة الصفر. القيمة هي 0 عندما يكون المفتاح 0. لا توجد حاجة لإرجاع الحكم الإضافي 3 olling subudo [key] = key} return 0 ؛}4. حل اجتياز
يعد استخدام العناصر ذات القيمة الأولية للصفر في حالة العناصر ميزة معلقة ، وبمساعدة المكدس ، لا يتم فتح مساحة تخزين إضافية.
Function FindAnswer () {for (Let i = 0 ؛ i <9 ؛ i ++) {for (let j = 0 ؛ j <9 ؛) {if (مشكلة [i] [j] === 0 || flag) {// الموضع الحالي هو المعالجة الأولى للعنصر الذي يتم تحديده أو العودة إلى الموضع الحالي. يبدو أن الحالتين مختلفتين ، ولكن في الواقع المعالجة هي نفسها. أضف 1 بنفسك العلم = خطأ ؛ دع k = مشكلة [i] [j] + 1 ؛ // ابحث عن التحرك نحو القيمة القانونية التالية بينما (k <10) {// loop للعثور على مشكلة القيمة القانونية التالية [i] [j] = k ؛ // املأ if (check20grid (مشكلة ، i ، j) == 0) {// الافتراضي قانوني ، والحكم ذي العشرين ذات العشرين هو stack.push ([i ، j ++]) // تخزين نقطة التتبع والخطوة إلى الفتحة ؛ } k ++ ؛ } if (k> 9) {// لا يمكن العثور على القيمة القانونية في الموضع الحالي ، مشكلة التتبع [i] [j] = 0 ؛ // return قبل traceback دع rt = stack.pop () ؛ // استرجع معلومات التتبع في المكدس if (! rt) // لا يوجد حكم حل ، إرجاع 0 return 0 ؛ i = rt [0] // travel j = rt [1] flag = true ؛ }} آخر {// يتم إعطاء رقم الموضع الحالي J ++ ؛ }}} return 1 ؛ // وجدت بنجاح مجموعة من الحلول}