सुडोकू 17 सुराग विशेषज्ञ

सुडोकू 17 सुराग कैसे खेलें

सुडोकू एक तर्क-आधारित संख्या-प्लेसमेंट पहेली है। इसका उद्देश्य 9x9 ग्रिड को 1-9 नंबरों से भरना है, ताकि प्रत्येक पंक्ति, कॉलम और 3x3 सबग्रिड में सभी नौ नंबर बिल्कुल एक बार शामिल हों।

2009 में, गैरी मैकगायर और उनकी टीम ने साबित कर दिया कि 16 सुराग वाली किसी भी सुडोकू पहेली में कम से कम दो समाधान होने चाहिए। उन्होंने "डेड पैटर्न" नामक तकनीक का उपयोग करके ऐसा किया।

डेड पैटर्न एक सुडोकू कॉन्फ़िगरेशन है जिसमें दो या अधिक संभावित समाधान होते हैं। मैकगायर और उनकी टीम ने पाया कि 16 सुराग वाली किसी भी सुडोकू पहेली में कम से कम एक मृत पैटर्न अवश्य होना चाहिए। इसलिए, इन पहेलियों के कम से कम दो समाधान होने चाहिए।

इस नतीजे के कई निहितार्थ हैं. सबसे पहले, इसका मतलब है कि अद्वितीय समाधान वाली 16-सुराग वाली सुडोकू पहेली जैसी कोई चीज़ नहीं है। दूसरा, इसका मतलब है कि किसी भी 16-सुराग वाली सुडोकू पहेली को कई तरीकों से हल किया जा सकता है। तीसरा, इसका मतलब है कि 16-सुराग वाली सुडोकू पहेलियाँ अनंत संख्या में हैं।

यहां इस प्रमाण की अधिक तकनीकी व्याख्या दी गई है कि सुडोकू पहेलियों में एक अद्वितीय समाधान के लिए कम से कम 17 सुराग होने चाहिए:

प्रमाण की शुरुआत 16 सुरागों वाली सुडोकू पहेली पर विचार करने से होती है। हम इस पहेली को उन संख्याओं पर बाधाओं के एक सेट के रूप में सोच सकते हैं जिन्हें खाली वर्गों में रखा जा सकता है।

फिर हम पहेली का समाधान खोजने के लिए "बैकट्रैकिंग" नामक तकनीक का उपयोग कर सकते हैं। बैकट्रैकिंग एक पुनरावर्ती एल्गोरिदम है जो खाली वर्गों में संख्याओं के सभी संभावित संयोजनों का प्रयास करता है जब तक कि उसे कोई समाधान नहीं मिल जाता।

यदि पहेली का कोई अनोखा समाधान है, तो बैकट्रैकिंग अंततः इसे ढूंढ लेगा। हालाँकि, यदि कई समाधान हैं, तो पीछे हटने से कभी भी समाधान नहीं मिल सकता है।

मैकगायर और उनकी टीम ने यह दिखाने के लिए बैकट्रैकिंग का उपयोग किया कि यदि एक अद्वितीय समाधान के साथ 16-सुराग वाली सुडोकू पहेली है, तो बैकट्रैकिंग एल्गोरिदम को इस तरह से शुरू करने का एक तरीका होना चाहिए कि यह हमेशा समाधान ढूंढ सके।
फिर उन्होंने दिखाया कि यह संभव नहीं है. उन्होंने 16 सुरागों का एक सेट बनाकर ऐसा किया जो एक मृत पैटर्न की ओर ले जाता है। इस मृत पैटर्न का मतलब है कि पहेली के दो संभावित समाधान हैं, और बैकट्रैकिंग एल्गोरिदम को इस तरह से शुरू करने का कोई तरीका नहीं है कि यह हमेशा एक ही समाधान ढूंढे।
यह परिणाम दर्शाता है कि किसी भी 16-सुराग वाली सुडोकू पहेली में कम से कम दो समाधान होने चाहिए।