" सॉल्विंग सुडोकू एक वेब कैमरा का उपयोग करते हुए " लेख में, अधिकांश समाधान बहुत ही खूबसूरती से लागू किए जाते हैं, केवल सॉल्वर को छोड़कर। मेरी पुरानी परियोजनाओं में से एक, "सुडोकू सॉल्वर", मानक सुडोकू समस्या (क्षेत्र 9x9) को हल करने के लिए उत्तराधिकार के एक सेट के साथ एक एल्गोरिथ्म खोजने का प्रयास था। प्रत्यक्ष संपूर्ण खोज पर विचार नहीं किया गया है।


उनके आवेदन के लिए कई आंकड़े (एल्गोरिदम 1-4) और एक मेटा-एल्गोरिदम प्रस्तावित हैं। प्रयोगों से पता चला कि जटिलता के स्तर की परवाह किए बिना सभी प्रस्तावित समस्याओं को हल किया गया था, हालांकि मेरे पास कठोरता, पूर्णता और अभिसरण का कोई औपचारिक प्रमाण नहीं है।

सुडोकू नियम

• 9x9 कोशिकाओं के एक क्षेत्र का उपयोग किया जाता है, आगे 3x3 कोशिकाओं के 3x3 ब्लॉकों में विभाजित होता है।
• प्रत्येक सेल में 1 से 9 तक की संख्या हो सकती है
• यह अनुमति नहीं है कि दो या अधिक समान अंक लंबवत, क्षैतिज रूप से और 3x3 ब्लॉकों में से प्रत्येक के अंदर खड़े हों
• उद्देश्य : आंशिक रूप से भरे क्षेत्र में पूरी तरह से भरने के लिए

शब्दावली

फ़ील्ड - सुडोकू 9x9 का संपूर्ण क्षेत्र
पूर्ण सेल - वह सेल जिसके लिए मान निर्धारित किया गया है। यह समस्या के बयान के दौरान दिया गया एक आंकड़ा हो सकता है, या एल्गोरिथ्म के संचालन के दौरान पाया जा सकता है।
एक खाली सेल एक सेल है जिसके लिए अभी तक कोई मूल्य नहीं मिला है।
एक ब्लॉक 3x3 ब्लॉकों में से एक है, जो एक सेल के अंतर्गत आता है।
पूर्वानुमान - खाली कोशिकाओं के लिए संभावित मूल्यों की एक सूची।
भविष्यवाणी की लंबाई - खाली कोशिकाओं के लिए संभावित मानों की संख्या।

एल्गोरिदम संख्या 0. पूर्वानुमान पुनर्गणना

सुडोकू नियमों और प्रत्येक खाली सेल के लिए पूर्ण और खाली कोशिकाओं की वर्तमान स्थिति के अनुसार, संभावित मूल्यों की एक सूची एकत्र करें। यदि सेल में केवल एक पूर्वानुमान आंकड़ा बचा है, तो इसे इस आंकड़े से भरें।

एल्गोरिथम संख्या 1. मूल नियम नियंत्रण

प्रत्येक खाली सेल के लिए: पूर्वानुमान से हम संबंधित पूर्ण कोशिकाओं (क्षैतिज, लंबवत और ब्लॉक में) से संख्याओं को हटाते हैं। यदि सेल में केवल एक पूर्वानुमान आंकड़ा बचा है, तो इसे इस आंकड़े से भरें।

एल्गोरिथम संख्या 2. हम डुप्लिकेट की तलाश कर रहे हैं

प्रत्येक खाली सेल के लिए, हम एक ही पूर्वानुमान के साथ अन्य कोशिकाओं की तलाश करते हैं - पंक्ति, स्तंभ और ब्लॉक के लिए। यदि ऐसी कोशिकाओं की कुल संख्या (एक स्तंभ, पंक्ति या ब्लॉक के लिए) पूर्वानुमान की लंबाई के बराबर है, तो हम उन सभी को छोड़कर अन्य सभी कक्षों से पूर्वानुमान संख्या को हटा देते हैं। यदि सेल में केवल एक पूर्वानुमान आंकड़ा बचा है, तो इसे इस आंकड़े से भरें।

एल्गोरिथम संख्या 3. पूर्वानुमान के ऊपर

इस सेल में प्रत्येक पूर्वानुमान आकृति के लिए प्रत्येक खाली सेल + के लिए, हम कम से कम एक अन्य खाली सेल (एक पंक्ति, स्तंभ या ब्लॉक में) की तलाश करते हैं, जहां यह आंकड़ा भी मौजूद है। यदि नहीं मिला है, तो इस नंबर के साथ सेल भरें।

एल्गोरिथम संख्या 4. नकारात्मक नियंत्रण के साथ आंशिक संपूर्ण खोज

हम प्रत्येक पूर्वानुमान के आंकड़े के लिए सबसे कम पूर्वानुमान के साथ पहली सेल लेते हैं: इस सेल को भरें, एलगोरिदम 0 के निष्पादन को तब तक दोहराएं जब तक कि क्षेत्र की सभी कोशिकाओं के लिए पूर्वानुमान लंबाई> 0 और फ़ील्ड सुडोकू नियमों के अनुसार सही ढंग से न भर जाए। यदि हम एक नकारात्मक परिणाम का सामना करते हैं, तो हम मानते हैं कि आधार के रूप में अपनाए गए पूर्वानुमान का आंकड़ा एक मृत अंत की ओर जाता है और इसे पूर्वानुमान से हटा देता है। यदि परिणाम सकारात्मक है, लेकिन क्षेत्र पूरी तरह से भरा नहीं है, तो अगले पूर्वानुमान का आंकड़ा या अगला क्षेत्र लें।

मेटा एल्गोरिदम

क्रमिक रूप से एल्गोरिदम प्रदर्शन 1-4। यदि किसी एल्गोरिथ्म का परिणाम कोशिकाओं को भरने का कारण बना है, तो क्षेत्र की पूर्णता की जांच करें। यदि यह पूरी तरह से भरा नहीं है, तो वापस एल्गोरिथ्म 0. पर जाएं। यदि यह भरा हुआ है, तो सुडोकू नियमों के अनुसार भरने की शुद्धता की जांच करें और काम पूरा करें।

प्रस्तावित ह्यूरिस्टिक एल्गोरिथ्म में मुख्य दोष है - अभिसरण की कोई गारंटी नहीं है। इसके अलावा, प्रस्तावित चार उत्तराधिकारी पर्याप्त नहीं हो सकते हैं या वे बहुत प्रभावी नहीं होंगे। मैं एल्गोरिथ्म में सुधार करने, इसकी संपूर्णता का मूल्यांकन करने और उत्तराधिकार पर नए विचारों पर किसी भी विचार को स्वीकार करने के लिए आभारी रहूंगा।