ما هي العمليات الحسابية وراء شبكة سودوكو الفارغة?

يتم استخدام Sudoku Blank Grid في تناظر Sudoku,يستلزم صفًا وأعمدة 4 × 4،16 × 16 وأكثر مع شبكات صغيرة ومتنوعة.

يمكن دراسة ألغاز Sudoku رياضيًا للإجابة على أسئلة مثل “كم عدد شبكات سودوكو الكاملة?”, “ما هو أقل عدد من التلميحات في لغز حقيقي?” و “كيف يمكن أن تكون شبكات سودوكو متماثلة?” باستخدام النظريات الاندماجية والجماعية.

النتائج الرئيسية هي أن لعبة Sudoku الكلاسيكية, عدد الشبكات المكتملة هو 6,670,903,752,021,072,936,960 (6.67× 1021), التي, مع الاحتفاظ بصلاحية التحول يقلل إلى 5,472,730,538 مجموعات مختلفة بشكل كبير.

هناك 26 أنواع التناظر, ولكن لا يمكن العثور عليها إلا في حوالي 0.005% لجميع الشبكات المملوءة.

يجب أن يحتوي اللغز ذو الحل الفريد على الأقل 17 حلول, ولكل شعرية تم حلها لا يوجد أكثر من 21 حلول. أكبر حد أدنى تم العثور عليه اللغز 40 أدلة.

تُعرف النتائج المماثلة للمتغيرات والشبكات الأصغر. النتائج الدقيقة غير معروفة لـ Sudokus أكثر من شبكة 9 × 9 الكلاسيكية, على الرغم من وجود تقديرات تعتبر دقيقة إلى حد ما.

حلول حسابية لسودوكو

سؤال مثير للاهتمام, كم عدد الطرق التي يمكن أن 9 بواسطة 9 يتم تعبئة شبكة Sudoku لتلبية القاعدة الفردية?

بعبارات أخرى, كم عدد حلول سودوكو المختلفة الموجودة? نصف الطريقة التي استخدمها بيرترام فيلجنهاور وفريزر جارفيس في وقت مبكر 2006 لحساب هذا الرقم.

للحفاظ على مستوى لغتنا, نسمي ثلاثة صفوف من شرائح الكتل لشبكة وثلاثة أعمدة من كتل الكتل. تعتبر الخلية الموجودة في هذا الصف والعمود j في (أنا,ي).

نسمي عدد الشبكات الفردية Sudoku N. أول, نسمي كتل الشبكة على النحو التالي:

كم عدد الطرق المتاحة لملء B1 بطريقة صحيحة? لأن هناك 9 الأحرف التي يمكن أن تملأ B1, واحد في كل خلية, هذا هو 9 خيارات للخلية الأولى.

لكل من هؤلاء 9 خيارات, هناك 8 خيارات للخلية الثانية. لكل من هؤلاء 8 خيارات, هناك 7 ترك للخلية الثالثة.

في الأساس, نحسب عدد التباديل 9 الشخصيات: كم عدد الطرق التي يمكننا وضعها 9 الشخصيات في 9 أماكن, أو كم عدد الطرق التي يمكننا أن نطلبها 9 الأشياء.

هناك 9 طرق لملء B1. بدءا من كتلة B1 صالحة, يمكننا الحصول على أي كتلة B1 صالحة أخرى عن طريق إعادة تعليم الأرقام أو إعادة ترتيبها.

وبالتالي, أول افتراض تبسيط يمكننا القيام به هو أن B1 مليء بالأرقام 1, 2, 3, …, 9 مرتب, كما هو مبين أدناه.

الآن يمكننا حساب عدد نهايات الشبكة الفعلية التي يمتلكها B1 المحدد: دعونا نسميها N1. العدد الإجمالي لشبكات Sudoku الفعلية هو N1 × 9!, لذلك N1 = N / 9!…

دعنا نفكر في طرق ملء الصفوف الأولى في B2 و B3. منذ 1, 2 و 3 تحدث في الصف الأول في B1, لا يمكن أن تحدث هذه الأرقام في الصفوف الأخرى.

وبالتالي, فقط الأرقام 4, 5, 6, 7, 8 و 9 من الصفين الثاني والثالث من B1 يمكن أن يجتمع في الصف الأول في B2 و B3.

ضع قائمة بكل الطرق الممكنة لملء الصفوف الأولى في B2 و B3, حتى إعادة ترتيب الأرقام في كل كتلة. تلميح: هناك عشر طرق للقيام بذلك بحيث يمنحك تبادل B2 و B3 عشر طرق أخرى, ما مجموعه عشرين.

نسمي اثنين من هذه الاحتمالات الخطوط العليا الصافية: عندما ارقام {4,5,6}, مثل الصف الثاني من B1, يتم تخزينها معًا في B2, والأرقام {7,8,9}, مثل الصف الثالث من B1, يتم تخزينها معًا في B3, ونسخة معدلة من هذا.

الاحتمالات الأخرى هي الخطوط العليا المختلطة, كما يخلطون المجموعات {4,5,6} و {7,8,9} عند استخدامها لملء الأسطر الأولى من B2 و B3.

بالنظر إلى هذه الاحتمالات العشرين للسطر الأول من الشبكة (حتى إعادة ترتيب الأرقام في كل كتلة), يمكننا معرفة كيفية ملء السطر الأول.

فكر في كيفية إكمال الفرقة الأولى بدءًا من الصف العلوي النقي 1,2,3;{4,5,6};{7,8,9}.

(ملحوظة: نحن نكتب أ,ب,c للدلالة على ثلاثة أرقام مرتبة و {ا,ب,ج} للدلالة عليها بأي ترتيب.)

كم عدد الاحتمالات الإجمالية هناك, حساب عدد الطلبات المختلفة في كل صف في B2 و B3? هل هذا الرقم هو نفسه للصف العلوي النقي الآخر, 1,2,3;{7,8,9};{4,5,6}?

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

اتضح أن هناك (3!)⁶ طرق لإكمال الفرقة الأولى يحدق مع الصف العلوي النقي 1,2,3;{4,5,6};{7,8,9}.

هذا لأننا مضطرون لوضع {7,8,9};{1,2,3} في الصف الثاني في B2 و B3 و {1,2,3};{4,5,6} في الصف الثالث, وبعد ذلك يمكننا إعادة ترتيب الأرقام الثلاثة في كل من الصفوف الستة من B2 و B3 للحصول على جميع التكوينات.

الإجابة هي نفسها بالنسبة للصف العلوي النقي الآخر, لأنه في هذه الحالة كل ما فعلناه هو تبديل B2 بـ B3.

تعتبر حالات الصفوف العليا المختلطة أكثر تعقيدًا. دعونا ننظر في الصف العلوي 1,2,3;{4,6,8};{5,7,9}. يمكن إكمال هذا إلى النطاق الأول كما في الصورة التالية, اين ا, ب, و c هي الأرقام 1, 2, 3 في أي ترتيب.

بعد اختيار ملف, b و c هما الرقمان المتبقيان بأي ترتيب, كما هم في نفس الصف.

نظرًا لوجود ثلاثة خيارات لـ, ويمكن تخطي ثلاثة أرقام في كل مجموعة من المجموعات الست في B2 و B3 للحصول على صفحات أمامية مختلفة صالحة, العدد الإجمالي للتكوينات في هذه الحالة هو 3 ×(3!)6.

يمكنك بالمثل العمل من خلال كل من حالات الصف الأمامي السبعة عشر المتبقية للحصول على نفس الرقم.

الآن لدينا عدد الصفحات الأولى الممكنة التي حددتها B1: هذا 2 ×(3!)6+18× 3 ×(3!)6= 2612736, حيث يكون الجزء الأول من المجموع هو عدد مرات إتمام الصفحة الأولى من الصفوف العلوية الصافية والثاني هو عدد مرات إتمام الصفحة الأولى من الصفوف العلوية المختلطة.

بدلاً من حساب عدد مرات استكمال الصفحة الأولى لكل منها 2612736 الميزات, حدد Felgenhauer و Jarvis الصفحات الأمامية التي بها نفس عدد مرات استكمال الصفحة الأولى من أعلى الصفحة الفارغة.

يقلل هذا التحليل من عدد الصفحات الأولى التي يجب أخذها في الاعتبار عند الحساب.

فيما يلي بعض العمليات التي تترك عدد نهايات شبكة النطاق الأولى دون تغيير: ملاحظة الأرقام, الاستماع إلى أي من الكتل في النطاق الأول, الاستماع إلى الأعمدة في أي كتلة والاستماع إلى صفوف النطاق الثلاثة. مع أي من هذه التغييرات B1, يمكننا إعادة تحديد الأرقام لاستعادة شكلها القياسي.

الترتيب B1, تحافظ B2 و B3 على عدد نهايات الشبكة, لأننا إذا بدأنا بأي شبكة سودوكو فعلية, الطريقة الوحيدة لإبقائها حقيقية هي تحديد B4, B5, B6 و B7, ب 8, B9 على التوالي بحيث تظل الحزم كما هي.

بعبارات أخرى, يعطي كل إنهاء فعلي للشبكة في الصفحة الأولى نهاية شبكة واحدة فعلية بالضبط في الصفحة الأولى, أي. أي B1, B2, التقليب B3.
تأكد من ذلك عند تغيير B2 إلى B3 في شبكة Sudoko التالية, الطريقة الوحيدة للحفاظ على صلاحية الشبكة هي تغيير B5 إلى B6 ومن B7 إلى B8. هذا سيبقي المداخن كما هي, على الرغم من أن موقعهم قد تغير.

إذا كانت لديك شبكة سودوكو صالحة وكنت تتخطى أعمدة في أي من B1, B2 و B3, ما الذي يجب عليك فعله بأعمدة بقية شبكة Sudoku للحفاظ على صلاحيتها? فمثلا, إذا قمت بتغيير الأعمدة 1 و 2 من B2 على الشبكة أعلاه, كيف يمكنك إصلاح الشبكة الناتجة بحيث تتوافق مع القاعدة الواحدة?

يخبرنا التمرين الأخير أن كل تعبئة لشبكة الصف الأمامي تعطي تعبئة فريدة لشبكة الصف الأمامي مع تخطي الأعمدة داخل الكتل.

تسمح لنا هذه الاعتبارات بتقليل عدد الصفحات الأمامية المحددة التي يجب أخذها في الاعتبار عند العد.

بعد فيلجنهاور وجارفيس, نقوم بالتمرير خلال العمودين B2 و B3 بحيث تكون إدخالات الصف العلوي لكل عمود بترتيب تصاعدي, ثم قم بتبديل B2 و B3 إذا لزم الأمر بحيث يكون إدخال B2 الأول أصغر من إدخال B3.

وهذا ما يسمى بالاختصار المعجمي.

منذ كل من الكتلتين 6 إعادة ترتيب الأعمدة وطريقتان لإعادة ترتيب الكتل, الاختصار المعجمي يخبرنا بذلك, بالنظر إلى الصفحة الأولى, هناك 62 × 2 = 72 صفحة أمامية أخرى بنفس عدد نهايات الشبكة.

إذن لدينا الآن 2612736/72 = 36288 صفحة أولية فقط للنظر فيها.

لكل من هذه الاحتمالات ، دعونا نلقي نظرة على إعادة ترتيب الكتل الثلاثة العلوية: هناك 6. لكل منهم هناك 63 إعادة ترتيب الأعمدة داخل كل كتلة.

بعد إجراء هذه العمليات, نقوم بإعادة العلامة لإرجاع B1 إلى شكله القياسي.

وبالمثل, يمكننا تجاوز الأسطر الثلاثة الأولى من المجموعة وإعادة وضع العلامات لإرجاع B1 إلى النموذج القياسي. توفر هذه العمليات عدد مرات استكمال شبكة الصف الأمامي.

استخدم فيلجنهاور وجارفيس برنامج كمبيوتر لتحديد أن هذه العمليات تقلل من عدد الصفحات الأولى التي يجب أخذها في الاعتبار 36288 فقط 416.

دعونا ننظر في هذه المجموعة الأولى.

قم بإجراء عمليات مختلفة عليها تحفظ عدد نهايات الشبكة الخاصة بها. يمكنك البدء بما يلي: استبدال الصف الأول والثاني. أعد تعليمه بحيث يكون B1 في شكله القياسي. قلل هذه الشبكة بشكل معجمي.

الشيء الرئيسي هو أن المجموعة التي بدأت بها والمجموعة الأخرى التي انتهيت منها لديهم نفس عدد الإكمالات حتى شبكة Sudoku الكاملة.

وهكذا, بدلاً من حساب عدد نهايات الشبكة لكل مجموعة من هذه المجموعات, يمكننا حسابه لواحد منهم فقط.

هناك المزيد من الخطوات التي تقلل عدد الشبكات التي يجب مراعاتها. إذا كان لدينا زوج من الأرقام {ا,ب} في عمود واحد مع وجود a في صف i و b في صف j, ونفس الزوج في عمود آخر مع b في صف i و a في صف j, سيكون لكل زوج شريط بنفس عدد نهايات الشبكة مثل الأصل.

هذا لأن كل زوج يقع في نفس العمود, وعندما يتم تغيير كليهما في نفس الوقت, يتم حفظ قاعدة واحدة, والذي يرضي أيضًا الصفوف المعنية.

كمثال, انظر إلى الأرقام 8 و 9 في العمودين السادس والتاسع من المثال أعلاه. النظر في جميع الحالات المحتملة من هذا اليسار Felgenhauer وجارفيس 174 من الأول 416 مجموعات للمتابعة معها.

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

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

كل من هذه 44 العصابات لها نفس عدد النهايات للشبكة الكاملة.

دع C تشير إلى أحد هؤلاء 44 شرائط. ثم يمكنك حساب عدد الطرق التي يمكن لـ C أن يكملها لشبكة Sudoku الكاملة: نسميها nc.

نحتاج أيضًا إلى عدد صفحات mC الأمامية التي تشترك في هذا العدد من نهايات nC للشبكة. ثم, العدد الإجمالي لشبكات Sudoku هو N = ΣCmCnC فقط, أو مجموع mCnC للجميع 44 شرائط.

كتب فيلجنهاور وجارفيس برنامج كمبيوتر لإجراء الحسابات النهائية.

قاموا بحساب عدد الإكمالات الصالحة N1 مع B1 في شكل قياسي, بدءا من 44 الممرات. ثم قاموا بضرب هذا الرقم في 9! للحصول على إجابة.

وجدوا أن عدد ممكن 9 بواسطة 9 شبكات Sudoku هي N = 6670903752021072936960, أي حوالي 6.671 × 1021.

المادة والصورة الائتمان:

HTTP://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html