कंप्यूटिंग और एआईप्रीप्रिंटसिद्धांतपढ़ने में 4 मिनट

विशाल रूबिक क्यूबों के लिए 10⁴⁰ का स्थिरांक घटकर 30.5

रूबिक क्यूब (Rubik’s Cube), जो अभी-अभी 50 साल का हुआ है, शायद दुनिया की सबसे प्रसिद्ध पहेली है, और इसका एक केंद्रीय प्रश्न कहने में सरल है: सबसे बुरी स्थिति में, इसे हल करने में कितनी चालें लगती हैं? क्लासिक 3×3×3 क्यूब के लिए उत्तर सटीक रूप से ज्ञात है: 20 चालें, एक परिणाम जिसे 2014 में एक टीम ने प्रकाशित किया था; उस टीम के सदस्यों में इस नए शोध-पत्र के लेखकों में से एक, टॉमस रोकिकी (Tomas Rokicki), का नाम भी है।

बड़े क्यूबों के लिए, जिनके हर किनारे पर n परतें होती हैं, सटीक उत्तर पहुँच से बाहर है — किसी दिए गए n×n×n क्यूब को इष्टतम ढंग से हल करना तो NP-पूर्ण (NP-complete) भी है। लेकिन 2011 में, एरिक डेमेन (Erik Demaine) और सहयोगियों ने दिखाया कि सबसे बुरी स्थिति कैसे बढ़ती है: n² / lg n के अनुपात में, जहाँ lg आधार-2 वाला लघुगणक है। यह मानक विधियों से एक लघुगणकीय गुणक बेहतर है, जो टुकड़ों को मूलतः एक-एक करके हल करती हैं।

एक बेतुके स्थिरांक वाला प्रमाण

इसमें एक पेंच था। 2011 का परिणाम वृद्धि-दर की गारंटी देता था, उसके आगे लगी संख्या की नहीं। उस एल्गोरिद्म को क़दम-दर-क़दम खंगालने पर, लेखक पाते हैं कि उसका स्थिरांक लगभग 1.01 × 10⁴⁰ है। ज़िम्मेदार है एक कंप्यूटर जाँच, जिसने सिद्ध किया था कि कुछ चालें 24 टुकड़ों के एक समूह की हर व्यवस्था तक पहुँच सकती हैं, पर यह नहीं बताया था कि कितनी जल्दी। उस लंबाई की एकमात्र सुरक्षित सीमा व्यवस्थाओं के उस समूह का आकार थी, लगभग 3.1 × 10²³ क़दम, और सूत्र अंततः विशाल संख्या 24! (1 × 2 × … × 24, लगभग 6.2 × 10²³) का दो जगह उपयोग करता है। इसके विपरीत, निचली सीमा — चालों की वह संख्या जिसकी लगभग हर बिखरे हुए क्यूब को ज़रूरत होती है — का स्थिरांक लगभग 12.88 जितना मामूली है। इसलिए समुदाय में कई लोग मानते थे कि ऐसा एल्गोरिद्म उचित आकारों के लिए कभी व्यावहारिक नहीं हो सकता।

MIT, TU Munich और पालो आल्टो (Palo Alto) से जेरेमी म्रज़िग्लोकी (Jeremy Mrzyglocki), टॉमस रोकिकी (Tomas Rokicki), मैक्सीन पेरोनी-शार्फ़ (Maxine Perroni-Scharf) और एरिक डेमेन (Erik Demaine) ने अब उस स्थिरांक को स्पष्ट और छोटा बना दिया है।

क्यूब के टुकड़ों के लिए छँटाई नेटवर्क

बड़े क्यूब पर केंद्र वाले टुकड़े हावी रहते हैं: उनकी संख्या n² की तरह बढ़ती है, जबकि कोने और किनारे वाले टुकड़े केवल n के अनुपाती पद जोड़ते हैं। केंद्र वाले टुकड़े 24-24 के परिवारों में बँटे होते हैं, जो केवल आपस में अदला-बदली कर सकते हैं। बुनियादी औज़ार है कम्यूटेटर (commutator), A B A′ B′ रूप का एक क्रम, जो लगभग सब कुछ अपनी जगह छोड़ देता है और एक परिवार के केवल तीन टुकड़ों का क्रमचय (permutation) करता है। टीम ने सभी 4,000 उपयोगी तीन-टुकड़ा अदला-बदलियों के लिए चालों के क्रम खोजे, जिनमें से हर एक अधिकतम 12 चालों का है।

दो विचार गिनती घटाते हैं। पहला, एक ही कम्यूटेटर को एक साथ कई परिवारों पर, पंक्तियों और स्तंभों के पूरे समूहों में, लगाया जा सकता है। दूसरा, हर परिवार को अलग से हल करने के बजाय, हर परिवार अदला-बदलियों के एक तय सार्वभौमिक क्रम (universal sequence) का पालन करता है, और जिनकी उसे ज़रूरत नहीं होती उन्हें बस छोड़ देता है। एक प्रमेयिका (lemma) सब कुछ एक साथ बाँधती है: L चरणों का सार्वभौमिक क्रम L/2 का अग्रणी स्थिरांक देता है।

उस क्रम को छोटा करने के लिए कंप्यूटर विज्ञान के छँटाई नेटवर्कों (sorting networks) से औज़ार उधार लिए जाते हैं: तुलनाओं के तय पैटर्न, जो किसी भी इनपुट को क्रम में लगा देते हैं। छह इनपुट वाला एक इष्टतम छँटाई नेटवर्क 96 चरण देता है, अतः 48 का स्थिरांक। कंप्यूटर खोज से मिले ऐसे नेटवर्क, जो 24 स्थितियों को पहले 12, फिर 4 के समूहों में बाँटते हैं, इसे 72 चरणों (36) तक ले आते हैं। अंत में, एक साथ तीन से अधिक टुकड़ों को फेरबदल करने वाली चालों की अनुमति देने और स्थितियों को अलग ढंग से बाँटने से यह 61 चरणों तक आ जाता है।

तीस दशमलव पाँच

प्रमेय: किसी भी n×n×n क्यूब को अधिकतम 30.5 n²/lg n चालों में हल किया जा सकता है, साथ में ऐसे पद जो बड़े n के लिए नगण्य हो जाते हैं। स्थिरांक 3.30 × 10³⁸ से अधिक गुना सुधरता है, और निचली सीमा के 2.37 गुने के भीतर है (30.5 / 12.88)। सपाट n×n×1 संस्करण के लिए, जिसे अभ्यास के तौर पर इस्तेमाल किया गया, स्थिरांक 12 या 18 से घटकर 1.5 रह जाता है।

256 परतों वाले एक क्यूब के हल होने के आठ फ़्रेम, खुले हुए फलकों और छोटे क्यूबों के रूप में, बिखरे शोर से लेकर एकसमान रंगों तक।

हर भुजा पर 256 परतों वाले एक क्यूब के हल के आठ समान अंतराल वाले फ़्रेम: बिखरे हुए फलक एकसमान रंगों में बदल जाते हैं। — चित्र 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

एल्गोरिद्म टुकड़ों की संख्या के अनुपात में समय लेता है, और लेखक एक ओपन-सोर्स सॉल्वर उपलब्ध कराते हैं, साथ में ऐसी स्क्रिप्टें जो उन सभी नेटवर्कों की संपूर्ण जाँच करती हैं जिन पर यह निर्भर है। उनकी अपनी तुलना में यह लगभग n = 840 से मौजूदा सॉल्वरों से आगे निकल जाता है; उन्होंने हर भुजा पर 256 और 65,536 परतों वाले क्यूबों के हल रेंडर किए हैं।

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