🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

यह शोध पत्र एक अनुकूलित ऑसिलेटरी न्यूरल नेटवर्क (ONN) सॉल्वर पेश करता है जो सुडोकू को ग्राफ कलरिंग समस्या के रूप में पुनर्गठित करता है, जिससे $4 \times 4$ और $9 \times 9$ पहेलियों पर मौजूदा HNN और ONN दृष्टिकोणों की तुलना में काफी अधिक सटीकता प्राप्त होती है।

मूल लेखक: Filip Sabo, Aida Todri-Sanial

प्रकाशित 2026-07-20

📖 8 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Filip Sabo, Aida Todri-Sanial

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक ऐसी दुनिया की कल्पना करें जहाँ कंप्यूटर केवल एक सुपर-फास्ट कैलकुलेटर की तरह नंबरों को नहीं जोड़ते, बल्कि एक लय पर नाचते हैं। यह ऑसिलेटरी न्यूरल नेटवर्क (ONNs) का क्षेत्र है, जो कि एक प्रकार की "भौतिकी-आधारित" (physics-based) कंप्यूटिंग है। मानक इलेक्ट्रॉनिक स्विचों के बजाय, ये नेटवर्क छोटे, कंपन करने वाले इकाइयों का उपयोग करते हैं जिन्हें ऑसिलेटर (oscillators) कहा जाता है। इन्हें मेट्रोनोमों से भरे एक कमरे या गायकों के एक समूह की तरह समझें। इस प्रणाली में, जानकारी को केवल "ऑन" या "ऑफ" बिट के रूप में संग्रहीत नहीं किया जाता है; इसे कंपनों की टाइमिंग में संग्रहीत किया जाता है, जिसे फेज (phases) कहा जाता है। यदि दो ऑसिलेटर पूरी तरह से तालमेल में कंपन करते हैं, तो वे "इन फेज" (in phase) होते हैं; यदि वे विपरीत समय पर कंपन करते हैं, तो वे "आउट ऑफ फेज" (out of phase) होते हैं।

इन नेटवर्कों का लक्ष्य पूर्ण सामंजस्य या न्यूनतम ऊर्जा की स्थिति खोजना है, जहाँ सभी ऑसिलेटर एक स्थिर पैटर्न में बस जाएँ। यह दृष्टिकोण कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्याओं (combinatorial optimization problems) को हल करने के लिए विशेष रूप से अच्छा है—ऐसे पहेलियाँ जहाँ आपको नियमों के साथ बिना किसी टकराव के टुकड़ों को व्यवस्थित करना होता है। आपने शायद ग्राफ कलरिंग (Graph Coloring) समस्या के बारे में सुना होगा, जो एक मानचित्र को रंगने जैसा है ताकि कोई भी दो पड़ोसी देश एक ही रंग के न हों। यदि आप एक ऑसिलेटर नेटवर्क को स्वाभाविक रूप से ऐसे पैटर्न में बसने के लिए प्राप्त कर सकते हैं जहाँ कोई भी "पड़ोसी" एक ही समय पर कंपन नहीं कर रहा हो, तो आपने केवल ब्रूट-फोर्स गणित के बजाय भौतिकी के नियमों का उपयोग करके एक जटिल पहेली को हल कर लिया है। यह महत्वपूर्ण है क्योंकि पारंपरिक कंप्यूटर इन प्रकार की पहेलियों के साथ संघर्ष करते हैं, अक्सर भारी मात्रा में बिजली और समय खर्च करते हैं, जबकि ये नाचते हुए ऑसिलेटर अधिक तेज़ और ऊर्जा-कुशल तरीके से सोचने का विकल्प दे सकते हैं।

द ग्रेट सुडोकू डांस-ऑफ

अब, सुडोकू के बारे में बात करते हैं। आप जानते ही हैं: नंबरों का एक ग्रिड जहाँ आपको खाली स्थानों को इस तरह भरना होता है कि प्रत्येक पंक्ति, कॉलम और छोटे बॉक्स में 1 से 9 (या छोटे संस्करण के लिए 1 से 4) तक के अंक बिना किसी दोहराव के हों। यह एक क्लासिक लॉजिक पज़ल है, लेकिन एक कंप्यूटर के लिए, यह परीक्षण और त्रुटि (trial and error) का एक बड़ा सिरदर्द है।

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

ऑसिलेटर्स की दुनिया में, "एक रंग पहनने" का अर्थ है एक विशिष्ट लय पर कंपन करना। 9x9 सुडोकू के लिए, 9 संभावित लय (फेज) हैं जिन्हें ऑसिलेटर चुन सकते हैं। नेटवर्क का काम यह सुनिश्चित करना है कि सभी डांसर एक ऐसी लय चुनें कि कोई भी दो पड़ोसी एक ही डांस मूव न कर रहे हों।

पुराने डांस मूव्स के साथ समस्या

लेखकों ने देखा कि अन्य वैज्ञानिकों ने पहले इसे कैसे हल करने की कोशिश की थी। एक विधि में एक जटिल गणितीय सूत्र शामिल था जो गणना करने में बहुत महंगा था, जैसे कि हर एक मांसपेशी की गति की पहले से गणना करके एक नृत्य को कोरियोग्राफ करना। एक अन्य विधि अधिक सरल दृष्टिकोण का उपयोग करती थी, लेकिन इसमें एक घातक दोष था: इसने डांसरों को "चीटिंग" करने की अनुमति दी।

कल्प_िए एक ऐसी स्थिति की जहाँ एक ही पंक्ति में दो डांसर दोनों ही "नंबर 1" वाला डांस करने का निर्णय लेते हैं। पुराने, सरल मॉडलों में, नेटवर्क सोच सकता है, "अरे, वे दोनों 'नंबर 1' वाली लय कर रहे हैं, जो कि एक वैध लय है, इसलिए हम ठीक हैं!" लेकिन सुडोकू में, यह एक आपदा है। नियम कहते हैं कि आप एक ही पंक्ति में दो 1 नहीं रख सकते। पुराने मॉडलों के पास डांसरों को उस खराब स्थिति से बाहर निकालने का कोई तरीका नहीं था यदि वे गलती से एक ही नंबर पर सिंक हो जाते।

नया "किक" टर्म (The New "Kick" Term)

इसे ठीक करने के लिए, लेखकों ने ऑसिलेटर्स को नचाने का एक नया, सरल तरीका आविष्कार किया, और उन्होंने एक विशेष "किक" तंत्र जोड़ा।

सरल लय (The Simpler Rhythm): जटिल, महंगी गणितीय सूत्र का उपयोग करने के बजाय, उन्होंने एक स्वच्छ, अधिक प्रत्यक्ष समीकरण का उपयोग किया। इसने कंप्यूटर सिमुलेशन को बहुत तेज़ और सस्ता बना दिया।
"किक" (द सीक्रेट सॉस): यह सबसे महत्वपूर्ण हिस्सा है। उन्होंने समीकरणों में एक विशेष टर्म जोड़ा जो एक रेफरी की तरह काम करता है। यदि एक ही पंक्ति, कॉलम या बॉक्स में दो डांसर गलती से बिल्कुल एक ही फ्रीक्वेंसी पर कंपन करने लगते हैं (मतलब उन्होंने एक ही नंबर चुन लिया है), तो यह रेफरी उन्हें एक ज़ोरदार "किक" देता है। यह उन्हें उस स्थिर, आरामदायक अवस्था से बाहर धकेलता है और उन्हें एक अलग लय आज़माने के लिए मजबूर करता है।

यह "किक" सुनिश्चित करता है कि नेटवर्क केवल तभी शांत होता है जब पहेली वास्तव में सही ढंग से हल हो जाती है। यह एक शिक्षक की तरह है जो कक्षा में घूम रहा है: यदि दो छात्र एक ही गलत उत्तर फुसफुसा रहे हैं, तो शिक्षक उन्हें उनके कंधे पर थपथपाता है ताकि वे रुकें और फिर से सोचें।

परिणाम: एक त्रुटिहीन प्रदर्शन

टीम ने अपने नए "किक-अस" (kick-ass) ऑसिलेटर सॉल्वर का हजारों सुडोकू पहेलियों पर परीक्षण किया, जिसमें 4x4 ग्रिड से लेकर मानक 9x9 ग्रिड तक शामिल थे। उन्होंने अपने परिणामों की तुलना दो अन्य प्रसिद्ध सॉल्वर के विरुद्ध की: एक जो हॉपफील्ड न्यूरल नेटवर्क (HNN) पर आधारित है और दूसरा मानक ऑसिलेटरी न्यूरल नेटवर्क।

यहाँ उन्हें क्या मिला:

4x4 पहेलियों के लिए: उनका नया सॉल्वर लगभग पूर्ण था। उन्होंने लगभग 100% पहेलियों को सही ढंग से हल किया, चाहे कितने भी नंबर गायब क्यों न हों। अन्य सॉल्वर संघर्ष कर रहे थे, और जैसे-जैसे पहेलियाँ कठिन हुईं (अधिक गायब नंबर), उनकी सटीकता तेजी से गिरी।
9x9 पहेलियों के लिए: परिणाम अभी भी प्रभावशाली थे, हालांकि पूरी तरह से सटीक नहीं थे। जब पहेलियों में कम संख्या में नंबर गायब थे (लग तक 25% अज्ञात तक), तो उनका सॉल्वर त्रुटिहीन था। यहाँ तक कि जब पहेलियाँ कठिन हुईं (37.5% अज्ञात तक), तब भी इसने 80% से अधिक पहेलियों को हल किया। हालाँकि, जब पहेलियाँ बहुत कठिन हो गईं (50% से अधिक अज्ञात नंबर), तो सॉल्वर लड़खड़ाने लगा, और लगभग 50% सही हल कर पाया। अन्य सॉल्वर बहुत पहले ही विफल हो गए, अक्सर 40-50% से अधिक नंबर गायब होने पर कोई भी पहेली सही ढंग से हल करने में असमर्थ रहे।

शोधकर्ताओं ने एक "ऑर्डर पैरामीटर" (order parameter) पर भी नज़र डाली, जो मूल रूप से एक स्कोर है कि ऑसिलेटर्स ने अपनी अंतिम, सही लय में कितनी अच्छी तरह से बसने का प्रबंधन किया। उन्होंने पाया कि जब भी सॉल्वर ने पहेली को सही हल किया, ऑसिलेटर्स बहुत अच्छी तरह से व्यवस्थित (उच्च ऑर्डर पैरामीटर) थे। जब इसने पहेली को गलत हल किया, तो ऑसिलेटर्स अराजक थे और एक स्थिर पैटर्न पर सहमत नहीं हो सके।

आगे क्या?

लेखक काफी आश्वस्त हैं कि उनका "किक" टर्म उनकी सफलता का कारण है, लेकिन वे स्वीकार करते हैं कि अभी भी काम करना बाकी है। उनके मॉडल में कुछ "नॉब्स" (knobs) थे जिन्हें उन्हें काम करने के लिए मैन्युअल रूप से घुमाना पड़ा (ट्यून करने योग्य पैरामीटर), जिसे समझने में बहुत समय लगा। उन्होंने यह भी देखा कि सबसे कठिन 9x9 पहेलियों के लिए, ऑसिलेटर्स को कभी-कभी "नाचने" और बसने के लिए अधिक समय की आवश्यकता थी, या शायद "किक" पर्याप्त शक्तिशाली नहीं था।

वे सुझाव देते हैं कि भविष्य के संस्करणों में वे और भी अधिक जटिल, "नॉन-लीनियर" (nonlinear) ऑसिलेटर्स (अधिक जटिल मूव्स वाले डांसर) का उपयोग कर सकते हैं या "किक" फंक्शन को और भी बेहतर बनाने के लिए ट्यून कर सकते हैं ताकि नियम तोड़ने वालों को और भी बेहतर तरीके से पकड़ा जा सके। लेकिन फिलहाल, उन्होंने दिखाया है कि इन नाचते हुए नेटवर्कों की भौतिकी में एक सरल, चतुर नियम जोड़कर, हम सुडोकू पहेलियों को पहले की तुलना में बहुत बेहतर तरीके से हल कर सकते हैं। यह एक छोटा कदम है, लेकिन यह साबित करता है कि कभी-कभी, एक टूटे हुए सिस्टम को ठीक करने के लिए आपको बस एक सही दिशा में थोड़े से धक्के की आवश्यकता होती है।

तकनीकी सारांश: ऑसिलेटरी न्यूरल नेटवर्क के साथ सुडोकू को हल करने के लिए ग्राफ कलरिंग दृष्टिकोण

समस्या विवरण
यह शोध पत्र भौतिकी-आधारित कंप्यूटिंग प्रतिमान (paradigm) का उपयोग करके बाधित संयोजी अनुकूलन समस्याओं (constrained combinatorial optimization problems - COPs), विशेष रूप से सुडोकू पहेली को हल करने की चुनौती को संबोधित करता है। पारंपरिक कंप्यूटिंग आर्किटेक्चर उन NP-hard समस्याओं को हल करने में मेमोरी-कंप्यूट बाधाओं और उच्च बिजली खपत का सामना करते हैं जहाँ समाधान का समय समस्या के आकार के साथ तेजी से (exponentially) बढ़ता है। लेखक ऑसिलेटरी न्यूरल नेटवर्क (ONNs) का उपयोग करने का प्रस्ताव देते हैं, जो युग्मित ऑसिलेटरों (coupled oscillators) की गतिशीलता के माध्यम से एक अंतर्निहित ऊर्जा फलन (energy function) को न्यूनतम करते हैं, जो पारंपरिक आर्टिफिशियल न्यूरल नेटवर्क और हॉपफील्ड न्यूरल नेटवर्क (HNNs) का एक विकल्प है। विशिष्ट चुनौती सुडोकू के नियमों को मैप करने में निहित है—जहाँ किसी भी पंक्ति, कॉलम या बॉक्स में कोई अंक दोहराया नहीं जा सकता—ऑसिलेटरों के फेज डायनेमिक्स (phase dynamics) में, बिना नियम उल्लंघन की अनुमति दिए (जैसे, एक ही पंक्ति में दो ऑसिलेटर एक ही "अंक" फेज पर स्थिर न हो जाएं)।

कार्यप्रणाली
लेखक सुडोकू को एक ग्राफ कलरिंग समस्या के रूप में तैयार करते हैं, जहाँ प्रत्येक सेल एक नोड है और किनारे (edges) उन सेल्स को जोड़ते हैं जो एक ही पंक्ति, कॉलम या बॉक्स साझा करते हैं। लक्ष्य प्रत्येक नोड को एक अद्वितीय "रंग" (फेज) आवंटित करना है।

फेज मैपिंग (Phase Mapping): $N \times N$ आकार के सुडोकू के लिए (जहाँ $K=N$ ), आदर्श फेजों को असतत मानों में मैप किया जाता है: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ जहाँ $k \in \{1, ..., K\}$ ।
संशोधित ODE: लेखक मौजूदा ONN ग्राफ कलरिंग मॉडलों (विशेष रूप से Max-K-Cut फॉर्मूलेशन) की आलोचना करते हैं क्योंकि वे ट्यूनेबल मापदंडों के कारण गणनात्मक रूप से महंगे होते हैं और संभावित रूप से अमान्य मूल (invalid roots) की अनुमति दे सकते हैं जहाँ जुड़े होने के बावजूद ऑसिलेटर एक ही फेज पर स्थिर हो जाते हैं। वे ऑसिलेटर डायनेमिक्स के लिए एक सरल, गणनात्मक रूप से सस्ते साधारण अवकल समीकरण (ODE) का प्रस्ताव करते हैं:
$\dot{\phi}_i = -f_{unknown}(\phi_i) \left[ \frac{1}{N} \sum_{j} W_{ij} \sin\left(\frac{K}{2}(\phi_i - \phi_j)\right) + K_S \sin(K\phi_i) \right] + f_{unknown}(\phi_i) K_G \sum_{j} W'_{ij} g(\phi_i, \phi_j)$
- पहला पद (First Term): ऑसिलेटरों को $\frac{2\pi}{K}$ द्वारा अलग करने के लिए प्रेरित करता है (Max-K-Cut तर्क)।
- दूसरा पद ( $K_S$ ): ऑसिलेटरों को विशिष्ट आदर्श फेज मानों पर स्थिर होने के लिए मजबूर करता है।
- तीसरा पद (Novel Contribution): एक अतिरिक्त पद जिसमें एक फलन $g(\phi_i, \phi_j)$ शामिल है जो यह पता लगाता है कि क्या दो जुड़े हुए ऑसिलेटर एक ही फेज पर स्थिर हो गए हैं (एक नियम उल्लंघन)। यदि उल्लंघन का पता चलता है, तो यह पद एक ग्रेडिएंट इंजेक्ट करता है जो ऑसिलेटरों को उस स्थिर अवस्था से बाहर "धकेलने" (kick) का काम करता है।
वेट मैट्रिक्स ( $W_{ij}$ ): वेट्स को इस तरह डिज़ाइन किया गया है कि ज्ञात अंक अज्ञात अंकों की तुलना में अधिक प्रभाव डालते हैं। ज्ञात अंक स्थिर (शून्य ग्रेडिएंट) होते हैं, जबकि अज्ञात अंक अपने पड़ोसियों के साथ परस्पर क्रिया करते हैं। एक ही पंक्ति/कॉलम/बॉक्स में दो अज्ञात अंकों के बीच का वेट नकारात्मक होता है लेकिन ज्ञात अंक वाले वेट की तुलना में कम परिमाण का होता है।
ऑर्डर पैरामीटर ( $\kappa$ ): अभिसरण (convergence) को ट्रैक करने के लिए एक मीट्रिक परिभाषित किया गया है, जहाँ 1 के करीब मान सफल अभिसरण को दर्शाते हैं।

मुख्य योगदान

नवीन ONN फॉर्मूलेशन: शोध पत्र एक संशोधित ONN सॉल्वर पेश करता है जो सुडोकू को ग्राफ कलरिंग समस्या के रूप में पुनर्गठित करता है लेकिन ODE में एक विशिष्ट बाधा-प्रवर्तन (constraint-enforcement) पद जोड़ता है। यह पद सुनिश्चित करता है कि सिस्टम केवल तभी लुप्त ग्रेडिएंट (vanishing gradient) तक पहुँचता है जब सभी सुडोकू बाधाएं संतुष्ट होती हैं, जिससे "फॉल्स पॉजिटिव" (गलत सकारात्मक) को रोका जा जाता है जहाँ जुड़े हुए नोड्स के लिए ऑसिलेटर समान फेज पर स्थिर हो जाते हैं।
गणना दक्षता: लेखक जटिल, पैरामीटर-भारी Max-K-Cut ODE के स्थान पर एक सरल, गणनात्मक रूप से सस्ता मॉडल प्रदान करते हैं जिसे इंटरेक्शन फंक्शन के लिए ट्यूनेबल पीक-विड्थ मापदंडों की आवश्यकता नहीं होती है।
बेंचमार्किंग: अध्ययन $4 \times 4$ और $9 \times 9$ पहेलियों और अज्ञात अंकों के विभिन्न अनुपातों के साथ एक स्थापित HNN सॉल्वर और एक पारंपरिक ONN सुडोकू सॉल्वर के विरुद्ध एक व्यापक सटीकता तुलना प्रदान करता है।

परिणाम

$4 \times 4$ पहेलियाँ: प्रस्तावित सॉल्वर ने सभी परीक्षण किए गए अज्ञात अनुपातों (87.5% तक) के लिए लगभग त्रुटिहीन सटीकता प्राप्त की, जो HNN और पारंपरिक ONN सॉल्वर दोनों से काफी बेहतर प्रदर्शन करती है। HNN सॉल्वर 60% से अधिक अज्ञात अनुपात के लिए पूरी तरह विफल रहा, जबकि पारंपरिक ONN सॉल्वर 50% अज्ञात होने पर ~80% सटीकता तक गिर गया।
$9 \times 9$ पहेलियाँ: प्रस्तावित सॉल्वर ने अन्य विधियों की तुलना में बेहतर प्रदर्शन किया। इसने 25% तक के अज्ञात अनुपातों के लिए पूर्ण सटीकता प्राप्त की और 37.5% अज्ञात होने पर 80% से अधिक सटीकता बनाए रखी। हालाँकि, जैसे-जैसे अज्ञात अंकों की संख्या बढ़ी, प्रदर्शन घटता गया, जो 50% अज्ञात होने पर ~50% तक गिर गया और 70% से अधिक अज्ञात अनुपातों के लिए पहेलियों को सही ढंग से हल करने में विफल रहा।
ऑर्डर पैरामीटर्स: सटीकता और ऑर्डर पैरामीटर के बीच एक मजबूत सहसंबंध था। उच्च सटीकता 1 के करीब ऑर्डर पैरामीटर्स (आदर्श फेजों की ओर अभिसरण) के अनुरूप थी, जबकि कम सटीकता कम ऑर्डर पैरामीटर्स के साथ जुड़ी थी, जो बताता है कि सिस्टम एक वैध स्थिर अवस्था में स्थिर होने में विफल रहा।

महत्व और दावे
शोध पत्र का दावा है कि प्रस्तावित दृष्टिकोण मौजूदा HNN और ONN सुडोकू सॉल्वर की तुलना में सटीकता में काफी बेहतर है, विशेष रूप से छोटी ग्रिड ( $4 \times 4$ ) और मध्यम रूप से बाधित $9 \times 9$ ग्रिड के लिए। लेखक इस सफलता का श्रेय ODE में अतिरिक्त पद को देते हैं, जो प्रभावी रूप से उन अमान्य स्थिर अवस्थाओं को समाप्त करता है जो ऊर्जा न्यूनीकरण (energy minimization) को तो संतुष्ट करती हैं लेकिन सुडोकू नियमों का उल्लंघन करती हैं।

लेखक अपनी सीमाओं को विनम्रतापूर्वक स्वीकार करते हैं, यह नोट करते हुए कि मॉडल चार ट्यूनेबल मापदंडों पर निर्भर करता है, जिससे पैरामीटर स्वीप (parameter sweep) महंगा हो जाता है। वे सुझाव देते हैं कि $9 \times 9$ पहेलियों में बड़े अज्ञात अनुपातों के लिए, अतिरिक्त पद को पर्याप्त रूप से स्केल नहीं किया गया होगा, या सिस्टम को स्थिर होने के लिए अधिक ऑसिलेटरी चक्रों की आवश्यकता हो सकती है। शोध पत्र निष्कर्ष निकालता है कि बाधा-प्रवर्तन पदों के साथ विस्तारित ODEs, ONNs के साथ COPs को हल करने के लिए एक प्रासंगिक रणनीति है और सुझाव देता है कि भविष्य के कार्य को अत्यधिक गैर-रेखीय (nonlinear) ऑसिलेटर और बाधा-प्रवर्तन फलन के वैकल्पिक फॉर्मूलेशनों का पता लगाना चाहिए।

द ग्रेट सुडोकू डांस-ऑफ

पुराने डांस मूव्स के साथ समस्या

नया "किक" टर्म (The New "Kick" Term)

परिणाम: एक त्रुटिहीन प्रदर्शन

आगे क्या?

इसी तरह के और पेपर