ما هو الحد الأدنى لعدد الأدلة التي يمكن أن يحتويها السودوكو؟
آخر تحديث
valid Sudoku - الذي له exactly one solution - يتطلب على الأقل 17 given digits. هذه نتيجة رياضية مثبتة. أي puzzle بـ 16 أو fewer clues إما أن يكون له multiple solutions أو لا حل على الإطلاق.
إثبات 2012
في عام 2012، نشر غاري ماكغواير، وباستيان توغيمان، وجيل سيفاريو في كلية دبلن الجامعية دليلاً على أنه لا يوجد سودوكو صالح بـ 16 دليلاً. كان عملهم حسابيًا في المقام الأول: لقد بحثوا في المساحة الكاملة لشبكات 16 دليلاً الممكنة وتحققوا من أن أياً منها لم ينتج حلاً فريدًا. تطلب البحث حوالي 7 ملايين ساعة أساسية من الحساب.
قبل ذلك، كان يُعتقد على نطاق واسع أن 17 هو الحد الأدنى وتم العثور على آلاف الألغاز بـ 17 دليلاً تجريبيًا. قدم فريق ماكغواير أول دليل صارم على أن 16 مستحيل.
كيف تبدو ألغاز 17-Clue
ألغاز ذات 17 دليلًا نادرة جدًا - 17 رقمًا معطى في 81 خلية، تاركة 64 فارغة. إنها من أصعب الألغاز في الحل وتتطلب عادة تقنيات متقدمة. إيجاد ألغاز صالحة ذات 17 دليلًا بحد ذاتها تطلب عقودًا من الجهد الحاسوبي. حتى وقت كتابة هذا النص، أكثر من 49,000 لغز سودوكو مختلف جوهريًا ذو 17 دليلًا معروفة.
ما يعنيه هذا لتصميم الألغاز
الألغاز المنشورة الموجهة للحلّالين البشريين نادرًا ما تقل عن 22 دليلاً. ألغاز الخبير والمستوى المتقن تستخدم عادةً 22-27 رقمًا معطى، بينما الألغاز السهلة تستخدم 36-45. الحد الأدنى النظري البالغ 17 دليلاً هو حد نظري - في الممارسة، قابلية الحل بتقنية جيدة ومسار حل ممتع يهمان أكثر بكثير من عدد الأدلة وحده.