ما هو الحد الأدنى لعدد الأدلة التي يمكن أن يحتويها السودوكو؟

في عام 2012، نشر غاري ماكغواير وباستيان توغيمان وجيل سيفاريو في كلية دبلن الجامعية دليلاً على عدم وجود لغز سودوكو صالح بـ 16 قرينة. كان عملهم حسابياً بشكل أساسي: لقد بحثوا في المساحة الكاملة لشبكات الـ 16 قرينة الممكنة وتحققوا من أن أياً منها لم ينتج حلاً فريداً. تطلب البحث حوالي 7 ملايين ساعة أساسية من الحوسبة.

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

ألغاز ذات 17 دليلاً نادرة جدًا - 17 رقمًا معطى في 81 خلية، تاركة 64 فارغة. إنها من بين أصعب الألغاز في الحل وتتطلب عادةً تقنيات متقدمة. إيجاد ألغاز صالحة ذات 17 دليلاً بحد ذاتها تطلب عقودًا من الجهد الحاسوبي. حتى وقت كتابة هذا، أكثر من 49,000 لغز سودوكو مختلف جوهريًا ذو 17 دليلاً معروفة.

الألغاز المنشورة الموجهة للحلّالين البشريين نادرًا ما تقل عن 22 قرينة. ألغاز Expert و Master عادةً ما تستخدم 22-27 رقمًا معطى، بينما ألغاز Easy تستخدم 36-45. الحد الأدنى النظري البالغ 17 قرينة هو حد نظري - في الممارسة، قابلية الحل بتقنية جيدة ومسار حل ممتع يهمان أكثر من عدد القرائن وحده.