🔢 mathematics

A Census of New Snake-in-the-Box Records

यह शोध पत्र आयाम 9 से 13 के लिए हाइपरक्यूब ग्राफ में नए, लंबे प्रेरित पथों (स्नेक्स) को प्रस्तुत करता है, जिससे स्नेक-इन-द-बॉक्स समस्या के ज्ञात निचले स्तरों (लोअर बाउंड्स) में सुधार होता है और इन रिकॉर्ड-लंबाई वाले पथों का एक कंप्यूटर-सत्यापन योग्य डेटासेट प्रदान किया जाता है।

मूल लेखक: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

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

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

CC BY 4.0

मूल लेखक: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

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

कल्पना कीजिए कि आप लाइट स्विचों से बने एक विशाल, बहु-आयामी भूलभुलैया में रास्ता खोजने की कोशिश कर रहे हैं। इस दुनिया में, हर कमरा स्विचों के "ऑन" या "ऑफ" होने के एक अनूठे संयोजन (combination) से बना है। एक कमरे से दूसरे कमरे में जाने के लिए, आप केवल ठीक एक स्विच को ही बदल सकते हैं। यह एक "हाइपरक्यूब" (hypercube) है, जो गणित में मौजूद एक आकृति है लेकिन एक डिजिटल भूलभुलैया जैसा महसूस होता है। अब, कल्पना कीजिए कि आप बिना किसी ऐसे कमरे में कदम रखे जिसे आप पहले ही देख चुके हैं, अधिक से अधिक कमरों से गुजरना चाहते हैं, और एक विशेष नियम के साथ: आप कोई शॉर्टकट नहीं ले सकते। यदि आप कमरा A और कमरा B में हैं, और वे दोनों कमरे C से जुड़े हुए हैं, तो आप A से B पर सिर्फ इसलिए नहीं कूद सकते क्योंकि वे पड़ोसी हैं; आपको उसी पथ का अनुसरण करना होगा जिसे आपने शुरू किया था। इस विशिष्ट प्रकार की यात्रा को "स्नेक" (snake) कहा जाता है।

कोई इन डिजिटल सांपों (snakes) की परवाह क्यों करता है? वास्तव में, इन भूलभुलभैयाओं में सबसे लंबे संभव स्नेक को खोजना बेहतर त्रुटि-पहचान कोड (error-detecting codes) बनाने के लिए महत्वपूर्ण है। इन कोडों को सुरक्षा जाल (safety nets) के रूप में सोचें जो आपके टेक्स्ट संदेशों, उपग्रह संकेतों और कंप्यूटर डेटा को शोर भरे ब्रह्मांड में यात्रा करते समय खराब होने से बचाते हैं। जितना लंबा स्नेक होगा, कोड उतना ही मजबूत होगा। दशकों से, गणितज्ञ विभिन्न आकारों की इन भूलभुलैयाओं के लिए सबसे लंबे संभव स्नेक को खोजने की दौड़ में लगे हुए हैं, लेकिन बड़े, अधिक जटिल भूलभुलैया के लिए, रिकॉर्ड लंबे समय से अटका हुआ है।

यह शोध पत्र उस दौड़ में एक बड़ा अपडेट है। लेखकों ने, जो शोधकर्ताओं की एक टीम है, 9 से 13 आयामों (dimensions) वाली भूलभुलैया में नए, लंबे स्नेक खोजने के लिए शक्तिशाली कंप्यूटरों का उपयोग किया है। इस कार्य से पहले, इन आयामों में ज्ञात सबसे अच्छे स्नेक वे थे जो अब तक के सबसे लंबे थे। टीम ने केवल एक या दो नहीं खोजे; उन्होंने महत्वपूर्ण रूप से लंबे पथ खोजे, जिससे उनके द्वारा परीक्षण किए गए प्रत्येक आयाम में पिछले रिकॉर्ड टूट गए। उदाहरण के लिए, 9-आयामी भूलभुलैया में, उन्होंने 191 चरणों वाला एक स्नेक खोजा, जिसने पुराने रिकॉर्ड 190 को पीछे छोड़ दिया। विशाल 13-आयामी भूलभुलैया में, उन्होंने इसकी लंबाई को 2,922 चरणों तक पहुँचा दिया, जो पिछले सर्वश्रेष्ठ 2,900 से अधिक था।

शोधकर्ताओं ने केवल एक पथ खोजने पर ही नहीं रोका; उन्होंने डिजिटल पुरातत्वविदों (archaeologists) की तरह काम किया, इन रिकॉर्ड-तोड़ने वाले स्नेक्स के पूरे परिवारों को खोद निकाला। 9-आयामी मामले में, उन्होंने उस नए रिकॉर्ड लंबाई के स्नेक को बनाने के 1,311 अलग-अलग तरीके खोजे। उन्होंने लंबे "कॉइल्स" (coils) (जो स्नेक की तरह ही हैं लेकिन वापस शुरुआत पर लौट आते हैं) और "सिमेट्रिक कॉइल्स" (symmetric coils) (जहाँ लूप का दूसरा आधा हिस्सा पहले आधे हिस्से का दर्पण होता है) खोजने के लिए भी अपनी विधियों को लागू किया। उनके परिणाम दर्शाते हैं कि पिछले सीमाएँ वास्तविक छत नहीं थीं; अभी भी बढ़ने की गुंजाइश बाकी है। इन सभी नए, लंबे पथों को एक सार्वजनिक डेटासेट में सहेजा गया है, जिससे कोई भी गणित को सत्यापित कर सकता है या इन नए, लंबे पथों का उपयोग और भी बेहतर त्रुटि-पहचान कोड बनाने के लिए कर सकता है। हालांकि उन्होंने प्रत्येक संभावित आयाम के लिए पहेली को हल नहीं किया है, लेकिन उन्होंने सफलतापूर्वक डिजिटल भूलभुलैया में क्या संभव है, उसकी ज्ञात सीमाओं का विस्तार किया है, यह सिद्ध करते हुए कि पर्याप्त कम्प्यूटेशनल शक्ति के साथ, हम अभी भी अंधेरे में चलने के नए, लंबे तरीके खोज सकते हैं।

तकनीकी सारांश: नए स्नेक-इन-द-बॉक्स (Snake-in-the-Box) रिकॉर्ड्स का एक जनगणना

समस्या की परिभाषा
यह शोध पत्र "स्नेक-इन-द-बॉक्स" समस्या को संबोधित करता है, जिसे मूल रूप से 1958 में कौट्ज़ (Kautz) द्वारा त्रुटि-पता लगाने वाले कोड (error-detecting codes) के संदर्भ में प्रतिपादित किया गया था। यह समस्या हाइपरक्यूब ग्राफ $Q_n$ के भीतर सबसे लंबे प्रेरित (induced/chordless) पथ, जिसे "स्नेक" (snake) कहा जाता है, की खोज करती है। $Q_n$ में, वर्टिक्स (vertices) लंबाई $n$ के बाइनरी स्ट्रिंग्स का प्रतिनिधित्व करते हैं, और एड्ज (edges) उन स्ट्रिंग्स को जोड़ते हैं जो ठीक एक कोऑर्डिनेट (coordinate) में भिन्न होते हैं। एक स्नेक को विशिष्ट वर्टिक्स के एक अनुक्रम के रूप में परिभाषित किया गया है जहाँ क्रमिक वर्टिक्स आसन्न (adjacent) होते हैं, और कोई भी दो गैर-क्रमिक वर्टिक्स आसन्न नहीं होते हैं। ऐसे पथ की अधिकतम लंबाई को $a(n)$ द्वारा दर्शाया जाता है।

शोध पत्र संबंधित संरचनाओं पर भी विचार करता है: "कॉइल्स" (coils - $Q_n$ में प्रेरित चक्र) जिनकी अधिकतम लंबाई $b(n)$ है, और "सिमेट्रिक कॉइल्स" (symmetric coils - वे कॉइल्स जहाँ चक्र का दूसरा आधा हिस्सा एक निश्चित XOR ऑपरेशन के माध्यम से पहले आधे हिस्से को प्रतिबिंबित करता है), जिनकी अधिकतम लंबाई $c(n)$ है। जबकि आयाम $n \le 8$ के लिए $a(n)$ और $b(n)$ के सटीक मान ज्ञात हैं, और $n \le 7$ के लिए $c(n)$ ज्ञात है, $n \ge 9$ (और सिमेट्रिक कॉइल्स के लिए $n \ge 8$ ) के लिए यह समस्या अनसुलझी बनी हुई है, जहाँ विभिन्न कम्प्यूटेशनल खोजों के माध्यम से केवल निचली सीमाएँ (lower bounds) स्थापित की गई हैं।

कार्यप्रणाली और दृष्टिकोण
लेखक आयाम 9 से 13 तक के लंबे स्नेक्स, कॉइल्स और सिमेट्रिक कॉइल्स खोजने के लिए निरंतर कम्प्यूटेशनल प्रयासों का उपयोग करते हैं। प्रदान किए गए टेक्स्ट में कोई विशिष्ट नवीन एल्गोरिथम आर्किटेक्चर का विवरण नहीं दिया गया है, बल्कि यह अपने कार्य को पिछले तरीकों (जिनमें जेनेटिक एल्गोरिदम, जनसंख्या-आधारित विकासवादी खोज, परम्यूटेशन-आधारित निर्माण और मोंटे-कार्लो ट्री सर्च शामिल थे) के ऊपर एक प्रगति के रूप में प्रस्तुत करता है।

लेखकों का दृष्टिकोण रिकॉर्ड-लंबाई वाले पथों को उत्पन्न करने और सत्यापित करने पर केंद्रित है। वे एक मानक नोटेशन का उपयोग करते हैं जहाँ एक स्नेक को एक 'ट्रांजिशन सीक्वेंस' (transition sequence) द्वारा दर्शाया जाता है—पथ के साथ बदले गए 0-इंडेक्स्ड कोऑर्डिनेट इंडेक्स की क्रमबद्ध सूची। अपने निष्कर्षों की वैधता सुनिश्चित करने के लिए, लेखक एक कंप्यूटर-सत्यापन योग्य डेटासेट प्रदान करते हैं। वे रिकॉर्ड लंबाई पर मिलने वाले असमान (inequivalent) स्नेक्स की गणना करने के लिए समाधान स्थान (solution space) का एक जनगणना (census) भी करते हैं। तुल्यता (Equivalence) का निर्धारण $Q_n$ की समरूपताओं (symmetries) द्वारा किया जाता है, जिसमें $n!$ कोऑर्डिनेट परम्यूटेशन, $2^n$ ट्रांसलेशन (XORिंग), और पथ रिवर्सल शामिल हैं।

मुख्य योगदान और परिणाम
शोध पत्र का प्राथमिक योगदान आयाम 9 से 13 तक $a(n)$ , $b(n)$ , और $c(n)$ के लिए नए निचले स्तर (lower bounds) स्थापित करना है, जो सभी पिछले ज्ञात रिकॉर्ड्स से बेहतर हैं।

स्नेक की लंबाई ( $a(n)$ ): लेखक आयाम 9 से 13 के प्रत्येक आयाम में पिछले सर्वश्रेष्ठ ज्ञात से लंबे स्नेक्स प्रस्तुत करते हैं।
- $n=9$ : 191 की एक नई लंबाई (पिछले 190 से सुधार)। लेखकों ने इस लंबाई के लिए 1,311 असमान स्नेक्स की पहचान की।
- $n=10$ : 379 की एक नई लंबाई (पिछले 376 से सुधार)।
- $n=11$ : 746 की एक नई लंबाई (पिछले 737 से सुधार)।
- $n=12$ : 1,476 की एक नई लंबाई (पिछले 1,465 से सुधार)।
- $n=13$ : 2,922 की एक नई लंबाई (पिछले 2,900 से सुधार)।
- सुधार की सीमा पिछले रिकॉर्ड्स से +1 से लेकर +22 तक है।
कॉइल की लंबाई ( $b(n)$ ): शोध पत्र आयाम 9, 10 और 11 में सबसे लंबे कॉइल्स के लिए बेहतर निचली सीमाएं रिपोर्ट करता है, जिसमें क्रमशः 192, 374 और 732 की नई लंबाई शामिल है।
सिमेट्रिक कॉइल की लंबाई ( $c(n)$ ): आयाम 10 और 11 के लिए बेहतर निचली सीमाएं प्रदान की गई हैं, जिनमें 370 और 726 की नई लंबाई है।

लेखक $Q_9$ में लंबाई-191 के एक स्नेक का एक ठोस उदाहरण प्रदान करते हैं, जिसमें उसका पूर्ण ट्रांजिशन सीक्वेंस सूचीबद्ध है। वे उल्लेख करते हैं कि लाखों नमूना लिए गए लंबाई-191 के स्नेक्स में से, $n=9$ के लिए ठीक 131 सिमेट्री क्लासेस पाई गईं, जिससे यह अनुमान लगाया गया कि इस लंबाई के लिए कोई अन्य क्लास मौजूद नहीं है, हालांकि वे $n \ge 10$ के लिए ऐसा कोई पूर्णता का दावा नहीं करते हैं।

महत्व और दावे
शोध पत्र मुख्य रूप से स्नेक-इन-द-बॉक्स समस्या के ज्ञात सीमाओं के अनुभवजन्य (empirical) विस्तार के माध्यम से अपना महत्व दावा करता है। आयाम 9 से 13 तक के ऐसे स्नेक्स प्रदान करके जो पहले से ज्ञात किसी भी स्नेक से अधिक लंबे हैं, लेखकों ने हाइपरक्यूब में अधिकतम संभव लंबाई के निचली स्तरों को और अधिक सटीक बनाया है।

यह कार्य इन नए रिकॉर्ड्स के एक "जनगणना" (census) के रूप में कार्य करता है, जो एक व्यापक डेटासेट प्रदान करता है जिसमें सभी अलग-अलग रिकॉर्ड-लंबाई वाले स्नेक्स के विशिष्ट ट्रांजिशन सीक्वेंस शामिल हैं। यह डेटासेट कंप्यूटर-सत्यापन योग्य प्रारूप में सार्वजनिक रूप से उपलब्ध कराया गया है, जिससे परिणामों का स्वतंत्र सत्यापन संभव है। लेखक अपने कार्य को पिछले शोधकर्ताओं (जैसे ऐस, इकोल्स, मेयर्सन और अन्य) द्वारा स्थापित कम्प्यूटेशनल वंशावली के विस्तार के रूप में देखते हैं, जो इस कॉम्बिनेटोरियल ऑप्टिमाइजेशन समस्या में कम्प्यूटेशनल रूप से प्राप्त करने योग्य सीमा को आगे बढ़ाता है, बिना यह दावा किए कि उन्होंने इन आयामों के लिए समस्या को हल कर लिया है या अपने नए बॉउंड्स की इष्टतमता (optimality) को सिद्ध कर दिया है।

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