सुडोकू के लिए एक कृत्रिम बुद्धिमत्ता-आधारित समाधान

29 जनवरी को राष्ट्रीय पहेली दिवस है, और जश्न में, हमने एक मजेदार ब्लॉग बनाया है जिसमें बताया गया है कि कृत्रिम बुद्धिमत्ता (एआई) का उपयोग करके सुडोकू को कैसे हल किया जाए।

परिचय

से पहले शब्द, सुडोकू पहेली यह बहुत लोकप्रिय था और यह अभी भी बहुत लोकप्रिय है। हाल के वर्षों में, का उपयोग इष्टतमीकरण पहेली को सुलझाने के तरीके एक प्रमुख विषय रहे हैं। देखना “अर्कीवा में अनुकूलन का उपयोग करके सुडोकू पहेली को हल करना".

वर्तमान समय में, एआई का उपयोग मशीन लर्निंग पर केंद्रित है जिसमें लैस्सो रिग्रेशन से लेकर सुदृढीकरण सीखने तक की विस्तृत श्रृंखला शामिल है। AI का उपयोग हुआ है फिर से लिखा हुआ जटिल से निपटने के लिए समयबद्धन चुनौतियाँ। एक विधि, बैकट्रैकिंग के साथ खोज, आमतौर पर उपयोग की जाती है और सुडोकू के लिए एकदम सही है।

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

सुडोकू की मूल बातें

विकिपीडिया से: सुडोकू एक तर्क-आधारित, संयोजनात्मक संख्या-प्लेसमेंट पहेली है। इसका उद्देश्य 9×9 ग्रिड को अंकों से भरना है ताकि प्रत्येक कॉलम, प्रत्येक पंक्ति और प्रत्येक नौ 3×3 उप-ग्रिड जो ग्रिड बनाते हैं (जिन्हें "बॉक्स", "ब्लॉक", "क्षेत्र" भी कहा जाता है) या "उप-वर्ग") में 1 से 9 तक के सभी अंक शामिल हैं। पहेली सेटर आंशिक रूप से पूर्ण ग्रिड प्रदान करता है, जिसमें आमतौर पर एक अद्वितीय समाधान होता है। पूर्ण की गई पहेलियाँ हमेशा एक प्रकार का लैटिन वर्ग होती हैं जिसमें अलग-अलग क्षेत्रों की सामग्री पर एक अतिरिक्त बाधा होती है। उदाहरण के लिए, एक ही पूर्णांक एक ही 9×9 प्लेइंग बोर्ड पंक्ति या कॉलम में या 3×3 प्लेइंग बोर्ड के नौ 9×9 उपक्षेत्रों में से किसी में दो बार दिखाई नहीं दे सकता है।

तालिका 1 में एक उदाहरण समस्या है. कुल 9 कक्षों के लिए 9 पंक्तियाँ और 81 स्तंभ हैं। प्रत्येक को 1 और 9 के बीच नौ पूर्णांकों में से एक और केवल एक की अनुमति है। प्रारंभिक समाधान में, एक सेल में या तो एक एकल मान होता है - जो इस सेल में मान को उस मान पर स्थिर करता है, या सेल रिक्त होता है, जो दर्शाता है कि हमें इसकी आवश्यकता है इस सेल के लिए एक मान खोजने के लिए। सेल (1,1) का मान 2 है और सेल (6,5) का मान 6 है। सेल (1,2) और सेल (2,3) खाली हैं, और एल्गोरिदम इन सेल के लिए एक मान ढूंढेगा।

जटिलता

एक और केवल एक पंक्ति और स्तंभ से संबंधित होने के अलावा, एक सेल एक और केवल 1 बॉक्स से संबंधित होता है। 9 बॉक्स हैं, और उन्हें तालिका 1 में रंग द्वारा दर्शाया गया है। तालिका 2 प्रत्येक बॉक्स या ग्रिड की पहचान करने के लिए 1 और 9 के बीच एक अद्वितीय पूर्णांक का उपयोग करती है। पंक्ति मान (1, 2 या 3) और स्तंभ मान (1, 2 या 3) वाले सेल बॉक्स 1 से संबंधित हैं। बॉक्स 6 पंक्ति मान (4, 5, 6) और स्तंभ मान (7, 8) हैं , 9). बॉक्स आईडी सूत्र BOX_ID = {3x(फ़्लोर((ROW_ID-1) /3)} + सीलिंग (COL_ID/3) द्वारा निर्धारित की जाती है। सेल (5,7) के लिए, 6 = 3x(फ़्लोर(5-1) ))/3) + छत (8/3)= 3×1 + 3 = 3+3।

पहेली का दिल

प्रत्येक अज्ञात सेल के लिए 1 और 9 के बीच एक पूर्णांक मान ज्ञात करना, जैसे कि पूर्णांक 1 से 9 का उपयोग प्रत्येक कॉलम, प्रत्येक पंक्ति और प्रत्येक बॉक्स के लिए एक बार और केवल एक बार किया जाता है।

आइए सेल (1,3) को देखें जो खाली है। पंक्ति 1 में पहले से ही मान 2 और 7 हैं। इस सेल में इनकी अनुमति नहीं है। कॉलम 3 में पहले से ही मान 3, 5,6, 7,9 हैं। इनकी अनुमति नहीं है. बॉक्स 1 (पीला) में मान 2, 3 और 8 हैं। इनकी अनुमति नहीं है। निम्नलिखित मानों की अनुमति नहीं है (2,7); (3, 5, 6, 7, 9); (2). जिन अद्वितीय मानों की अनुमति नहीं है वे हैं (3, 8, 2, 3, 5, 6, 7)। एकमात्र उम्मीदवार मान (8) हैं।

एक समाधान दृष्टिकोण यह होगा कि सेल (1) को अस्थायी रूप से 1,3 निर्दिष्ट किया जाए और फिर किसी अन्य सेल के लिए उम्मीदवार मान खोजने का प्रयास किया जाए।

एक बैकट्रैकिंग समाधान: शुरुआती घटक

सारणी संरचना

प्रारंभिक स्थान स्रोत समस्या को संग्रहीत करने और खोज का समर्थन करने के लिए एक सरणी संरचना पर निर्णय लेना है। तालिका 3 में यह सरणी संरचना है। कॉलम 1 प्रत्येक सेल के लिए एक अद्वितीय पूर्णांक आईडी है। मान 1 से 81 तक हैं। कॉलम 2 सेल की पंक्ति आईडी है। कॉलम 3 सेल की कॉलम आईडी है। कॉलम 4 बॉक्स आईडी है। कॉलम 5 सेल में मान है। ध्यान दें कि बिना किसी मान वाले सेल को रिक्त या शून्य के बजाय शून्य मान दिया जाता है। यह इसे "केवल पूर्णांक सरणी" रखता है - प्रदर्शन के लिए कहीं बेहतर।

एपीएल में, इस सरणी को 2-आयामी सरणी में संग्रहीत किया जाएगा जहां आकार 81 गुणा 5 है। मान लें कि तालिका 3 के तत्व चर MAT में संग्रहीत हैं। उदाहरण कार्य हैं:

कमांड MAT[1 2 3;]MAT की पहली 3 पंक्तियों को पकड़ लेता है
1 1 1 1 2
2 1 2 1 0
3 1 3 1 0
मैट[1 2 3; 4 5] पंक्तियों 1, 2, 3 और केवल कॉलम 4 और 5 को सुरक्षित करता है
1 2
1 0
1 0
(MAT[;5]=0)/MAT[;1] उन सभी कोशिकाओं को ढूंढता है जिनके लिए मान की आवश्यकता होती है।

तालिका 3 सम्मिलित करें

विवेक जांच: डुप्लिकेट

खोज शुरू करने से पहले, विवेक की जाँच करना महत्वपूर्ण है! यही शुरुआती समाधान संभव है. सुडोकू के लिए व्यवहार्य, अब किसी भी पंक्ति, स्तंभ या बॉक्स में डुप्लिकेट हैं। वर्तमान प्रारंभिक समाधान, उदाहरण के लिए, 1 संभव है। तालिका 4 में एक उदाहरण है जहां शुरुआती समाधान में डुप्लिकेट हैं। पंक्ति 1 में दो मान 2 हैं। क्षेत्र 1 में दो मान 2 हैं। फ़ंक्शन "SANITY_DUPE" इस तर्क को संभालता है।

विवेक जांच: बिना मान वाले सेल के लिए विकल्प

बिना किसी मूल्य वाले सेल के सभी संभावित मान जानकारी का एक बहुत ही उपयोगी हिस्सा होंगे। यदि कोई उम्मीदवार नहीं है तो यह पहेली हल नहीं हो सकती। एक सेल उस मूल्य को ग्रहण नहीं कर सकता जिस पर उसके पड़ोसी ने पहले से ही दावा किया है। सेल (1,'1,3' - यह अंतिम 1 बॉक्सिड है) के लिए तालिका 1 का उपयोग करते हुए, इसके पड़ोसी पंक्ति 1, कॉलम 3, और बॉक्स 1 हैं। पंक्ति 1 में मान (2,7) हैं; कॉलम 3 में मान (3,5,6,7,9) हैं; बॉक्स 1 में मान (2,3,8) हैं। सेल (1,3.1) निम्नलिखित मान (2,3,5,6,7,8,9) नहीं ले सकता। सेल (1,3,1) के लिए एकमात्र विकल्प (1,4) हैं। सेल (4,1,2) के लिए मान 1, 2, 3, 5, 6, 7, 9 पहले से ही पंक्ति 4, कॉलम 1, और/या बॉक्स 4 में उपयोग किए जा चुके हैं। एकमात्र उम्मीदवार मान (4,8) हैं . क्रिया "SANITY_CAND" इस तर्क को संभालती है।

तालिका 5 उम्मीदवारों को दिखाती है, उदाहरण के लिए, खोज प्रक्रिया की शुरुआत में 1। यदि किसी सेल को प्रारंभिक स्थितियों (तालिका 1) में पहले से ही एक मान निर्दिष्ट किया गया है, तो यह मान दोहराया जाता है और लाल रंग में दिखाया जाता है। यदि किसी सेल को मान की आवश्यकता है तो केवल एक ही विकल्प है, यह सफेद रंग में दिखाया गया है। सेल (8,7,9) का एकल मान सफेद रंग में 7 है। (2,5,8,4,3) का दावा पड़ोसी कॉलम 7 द्वारा किया जाता है। (1, 2, 9) पंक्ति 8 द्वारा। (3,2,6) बॉक्स 9 द्वारा। केवल मान 7 दावा रहित है।

विवेक जांच: संघर्षों की तलाश

उन कोशिकाओं के लिए सभी विकल्पों की पहचान करने वाली जानकारी जिन्हें मूल्य की आवश्यकता है (तालिका 4 में पोस्ट की गई है), हमें खोज प्रक्रिया शुरू करने से पहले एक संघर्ष की पहचान करने में सक्षम बनाती है। टकराव तब होता है जब दो सेल जिन्हें मूल्य की आवश्यकता होती है उनमें केवल एक ही उम्मीदवार होता है, उम्मीदवार का मूल्य समान होता है, और दोनों सेल पड़ोसी होते हैं। तालिका 4 से हम जानते हैं कि एकमात्र सेल जिसके लिए मान की आवश्यकता है और जिसका केवल एक ही उम्मीदवार है वह सेल (8,7,9) है। उदाहरण 1, कोई विरोध नहीं है।

संघर्ष क्या होगा? यदि सेल (3,7,3) के लिए एकमात्र संभावित मान 7 (1, 6, 7 के बजाय) था, तो एक विरोध है। सेल (8,7) और सेल (3,7) पड़ोसी हैं - एक ही कॉलम। हालाँकि, यदि सेल (4,9,2) के लिए एकमात्र संभावित मान 7 था (1, 2, 7 के बजाय) तो यह कोई विरोध नहीं होगा। ये कोशिकाएँ पड़ोसी नहीं हैं।

विवेक जांच सारांश

1. यदि डुप्लिकेट हैं, तो प्रारंभिक समाधान संभव नहीं है।
2. यदि किसी सेल में कोई उम्मीदवार नहीं है, तो इस पहेली का कोई संभावित समाधान नहीं है। प्रत्येक सेल के लिए उम्मीदवार मानों की सूची का उपयोग खोज स्थान को कम करने के लिए किया जा सकता है - बैकट्रैकिंग और अनुकूलन दोनों के लिए।
3. संघर्षों को खोजने की क्षमता यह पहचानती है कि पहेली संभव नहीं है - इसका कोई समाधान नहीं है - खोज प्रक्रिया के बिना। इसके अतिरिक्त, यह "समस्या कोशिकाओं" की पहचान करता है।

एक बैकट्रैकिंग समाधान: खोज प्रक्रिया

मुख्य डेटा संरचनाओं और विवेक जांच के साथ, हम अपना ध्यान खोज प्रक्रिया पर केंद्रित करते हैं। आवर्ती विषय फिर से खोज का समर्थन करने के लिए डेटा संरचनाएं प्राप्त करना है।

खोज पर नज़र रखना

सरणी ट्रैकर किए गए असाइनमेंट का ट्रैक रखता है

1. कॉलम 1 काउंटर है
2. कॉलम 2 इस सेल को असाइन करने के लिए उपलब्ध विकल्पों की संख्या है
   • 1 का अर्थ है 1 विकल्प उपलब्ध है, 2 का अर्थ है दो विकल्प, आदि।
   • 0 का अर्थ है - कोई विकल्प उपलब्ध नहीं है या 0 पर रीसेट करना (कोई निर्दिष्ट मान नहीं) और बैकट्रैकिंग
3. कॉलम 3 वह सेल है जिसे एक मान सूचकांक संख्या (1 से 81) सौंपी गई है
4. कॉलम 4 ट्रैक इतिहास में सेल को निर्दिष्ट मान है
   • 9999 के मान का अर्थ है कि यह सेल उस समय था जब अंतिम छोर पाया गया था
   • 1 और 9 के बीच के पूर्णांक का मान, खोज प्रक्रिया में इस बिंदु पर इस सेल के लिए निर्दिष्ट मान है।
   • 0 के मान का मतलब है कि इस सेल को एक असाइनमेंट की आवश्यकता है

ट्रैकर ऐरे का उपयोग खोज प्रक्रिया का समर्थन करने के लिए किया जाता है। सरणी ट्रैकहिस्ट इसकी संरचना ट्रैकर के समान है लेकिन यह संपूर्ण खोज प्रक्रिया का इतिहास रखता है। तालिका 6 में उदाहरण 1 के लिए ट्रैकहिस्ट का हिस्सा है। इसे बाद के अनुभाग में अधिक विस्तार से समझाया गया है।

इसके अतिरिक्त, सारणी पाव (वेक्टर का एक वेक्टर), इस सेल को पहले से निर्दिष्ट मानों का ट्रैक रखता है। यह सुनिश्चित करता है कि हम किसी असफल समाधान पर दोबारा विचार न करें - जैसा कि TABU में किया जाता है।

एक वैकल्पिक लॉग प्रक्रिया है जहां खोज प्रक्रिया प्रत्येक चरण को लिखती है।

तलाश शुरू

बहीखाता और विवेक जांच के बाद, अब हम खोज प्रक्रिया शुरू कर सकते हैं। चरण हैं:

1. क्या ऐसी कोई कोशिकाएँ बची हैं जिनके लिए मान की आवश्यकता है? - यदि नहीं, तो हमारा काम हो गया।
2. प्रत्येक सेल के लिए जिसे एक मान की आवश्यकता है, प्रत्येक सेल के लिए सभी उम्मीदवार विकल्प ढूंढें। तालिका 4 में समाधान प्रक्रिया की शुरुआत में ये मान हैं। प्रत्येक पुनरावृत्ति पर, इसे कक्षों को निर्दिष्ट मानों को समायोजित करने के लिए अद्यतन किया जाता है।
3. इस क्रम में विकल्पों का मूल्यांकन करें.
   • यदि किसी सेल में शून्य विकल्प हैं, तो बैकट्रैकिंग शुरू करें
   • एक विकल्प से सभी सेल ढूंढें, इनमें से एक सेल चुनें, यह असाइनमेंट बनाएं,
     1. और ट्रैकिंग तालिका, वर्तमान समाधान और PAV को अद्यतन करें।
   • यदि सभी सेल में एक से अधिक विकल्प हैं, तो एक सेल और एक मान का चयन करें और अपडेट करें
     1. और ट्रैकिंग तालिका, वर्तमान समाधान और PAV को अद्यतन करें

हम प्रत्येक चरण को स्पष्ट करने के लिए तालिका 6 का उपयोग करेंगे जो समाधान प्रक्रिया के इतिहास का हिस्सा है (जिसे ट्रैकहिस्ट कहा जाता है)।

पहले पुनरावृत्ति (CTR=1) में, सेल 70 (पंक्ति 8, कॉलम 7, बॉक्स 9) को एक मान निर्दिष्ट करने के लिए चुना गया है। केवल उम्मीदवार (7) है, और यह मान सेल 70 को सौंपा गया है। इसके अतिरिक्त, मान 7 को सेल 70 के लिए पहले से निर्दिष्ट मानों (पीएवी) के वेक्टर में जोड़ा जाता है।

दूसरे पुनरावृत्ति सेल में 30 को मान 1 दिया गया है। इस सेल में दो उम्मीदवार मान थे। सबसे छोटा उम्मीदवार मान सेल को सौंपा गया है (तर्क का पालन करना आसान बनाने के लिए बस एक मनमाना नियम)।

किसी सेल की पहचान करने और मान निर्दिष्ट करने की प्रक्रिया पुनरावृत्ति (सीटीआर) 20 तक ठीक काम करती है। सेल 9 को मूल्य की आवश्यकता है, लेकिन उम्मीदवारों की संख्या शून्य है। दो विकल्प हैं:

• इस पहेली का कोई हल नहीं है.
• हम कुछ असाइनमेंट को पूर्ववत करते हैं (पीछे हटते हैं) और दूसरा रास्ता अपनाते हैं।

हमने इसके निकटतम सेल असाइनमेंट की तलाश की, जहां एक से अधिक विकल्प थे। इस उदाहरण में, यह पुनरावृत्ति 18 पर हुआ, जहां सेल 5 को मान 3 निर्दिष्ट किया गया है, लेकिन सेल 5 के लिए दो उम्मीदवार मान थे - मान 3 और 8।

सेल 5 (सीटीआर = 18) और सेल 9 (सीटीआर = 20) के बीच, सेल 8 को मान 4 (सीटीआर=19) दिया गया है। हमने सेल 8 और 5 को वापस "मूल्य की आवश्यकता" सूची में डाल दिया है। इसे दूसरी और तीसरी CTR=20 प्रविष्टियों में कैप्चर किया जाता है, जहां मान 0 पर सेट किया जाता है। मान 3 को सेल 5 के लिए PAV वेक्टर में रखा जाता है। यानी खोज इंजन सेल 3 को मान 5 निर्दिष्ट नहीं कर सकता है।

खोज इंजन सेल 5 के लिए एक मान की पहचान करने के लिए फिर से शुरू होता है (3 के साथ अब कोई विकल्प नहीं है) और सेल 8 (सीटीआर = 5) के लिए मान 21 निर्दिष्ट करता है। यह तब तक जारी रहता है जब तक कि सभी सेल्स का कोई मान न हो या कोई ऐसा सेल न हो जिसमें कोई विकल्प न हो और कोई बैकट्रैकिंग पथ न हो। समाधान तालिका 7 में पोस्ट किया गया है।

ध्यान दें, जहां एक सेल के लिए एक से अधिक उम्मीदवार हैं, यह समानांतर प्रसंस्करण का मौका है।

MILP अनुकूलन समाधान के साथ तुलना

सतही स्तर पर, सुडोकू पहेली का प्रतिनिधित्व नाटकीय रूप से भिन्न है। एआई दृष्टिकोण पूर्णांकों का उपयोग करता है और किसी भी माप से यह एक सख्त और अधिक सहज प्रतिनिधित्व है। इसके अतिरिक्त, विवेक जांचकर्ता एक मजबूत सूत्रीकरण बनाने के लिए उपयोगी जानकारी प्रदान करते हैं। MILP प्रतिनिधित्व अंतहीन है बाइनरी (0/1). हालाँकि, आधुनिक एमआईएलपी सॉल्वरों की ताकत को देखते हुए बायनेरिज़ शक्तिशाली प्रतिनिधित्व हैं।

हालाँकि, आंतरिक रूप से, MILP सॉल्वर बायनेरिज़ नहीं रखता है बल्कि सभी शून्यों को संग्रहीत करने को समाप्त करने के लिए एक विरल सरणी विधि का उपयोग करता है। इसके अतिरिक्त, बायनेरिज़ को हल करने के लिए एल्गोरिदम 1980 और 1990 के दशक तक सामने नहीं आए थे। 1983 का पेपर क्राउडर, जॉनसन और पैडबर्ग बायनेरिज़ के साथ अनुकूलन के पहले व्यावहारिक समाधानों में से एक पर रिपोर्ट। वे एक सफल समाधान के लिए चतुर प्रीप्रोसेसिंग और शाखा और बाध्य तरीकों के महत्व को महत्वपूर्ण मानते हैं।

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

• एसईओ संचालित सामग्री और पीआर वितरण। आज ही प्रवर्धित हो जाओ।
• प्लेटोडेटा.नेटवर्क वर्टिकल जेनरेटिव एआई। स्वयं को शक्तिवान बनाएं। यहां पहुंचें।
• प्लेटोआईस्ट्रीम। Web3 इंटेलिजेंस। ज्ञान प्रवर्धित। यहां पहुंचें।
• प्लेटोईएसजी. कार्बन, क्लीनटेक, ऊर्जा, पर्यावरण, सौर, कचरा प्रबंधन। यहां पहुंचें।
• प्लेटोहेल्थ। बायोटेक और क्लिनिकल परीक्षण इंटेलिजेंस। यहां पहुंचें।
• स्रोत: https://blog.arkieva.com/an-artificial-intelligence-based-solution-to-sudoku/?utm_source=rss&utm_medium=rss&utm_campaign=an-artificial-intelligence-based-solution-to-sudoku