संगणन आणि एआयप्रीप्रिंटसिद्धांतवाचनासाठी ३ मिनिटे

महाकाय रुबिक क्यूबसाठी 10⁴⁰ चा स्थिरांक घटून 30.5 वर

नुकताच 50 वर्षांचा झालेला रुबिक क्यूब (Rubik’s Cube) हे कदाचित जगातील सर्वात सुप्रसिद्ध कोडे आहे, आणि त्याचा एक मध्यवर्ती प्रश्न मांडायला सोपा आहे: सर्वात वाईट परिस्थितीत, तो सोडवायला किती चाली लागतात? पारंपरिक 3×3×3 क्यूबसाठी उत्तर अचूक ज्ञात आहे: 20 चाली, हा निकाल 2014 मध्ये एका पथकाने प्रकाशित केला, ज्यात या नव्या शोधनिबंधाचे एक लेखक टॉमस रोकिकी (Tomas Rokicki) यांचा समावेश होता.

मोठ्या क्यूबसाठी, ज्यांच्या प्रत्येक कडेवर n थर असतात, अचूक उत्तर आवाक्याबाहेर आहे — दिलेला n×n×n क्यूब इष्टतम (optimal) पद्धतीने सोडवणे तर 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²³) ही प्रचंड संख्या दोन ठिकाणी वापरते. याउलट, निम्न सीमेचा (lower bound) — जवळजवळ प्रत्येक विस्कटलेल्या क्यूबला लागणाऱ्या चालींच्या संख्येचा — स्थिरांक सुमारे 12.88 इतका माफक आहे. त्यामुळे समुदायातील अनेकांचा असा विश्वास होता की असा अल्गोरिदम वाजवी आकारांसाठी कधीच व्यावहारिक ठरू शकणार नाही.

MIT, TU म्युनिक आणि पालो आल्टो येथील जेरेमी म्र्झिग्लॉकी (Jeremy Mrzyglocki), टॉमस रोकिकी, मॅक्सिन पेरोनी-शार्फ (Maxine Perroni-Scharf) आणि एरिक डेमेन यांनी आता तो स्थिरांक स्पष्ट आणि लहान केला आहे.

क्यूबच्या तुकड्यांसाठी वर्गीकरण जाळी

मोठ्या क्यूबवर मध्यभागीचे तुकडे (centre pieces) वर्चस्व गाजवतात: त्यांची संख्या n² प्रमाणे वाढते, तर कोपरे आणि कडा फक्त n च्या प्रमाणातील पदे जोडतात. मध्यभागीचे तुकडे 24 च्या कुटुंबांमध्ये विभागलेले असतात, जे केवळ आपापसांतच अदलाबदल करू शकतात. मूलभूत साधन आहे कम्युटेटर (commutator), A B A′ B′ या स्वरूपाचा एक क्रम जो जवळजवळ सर्वकाही जागेवर ठेवतो आणि एका कुटुंबातील फक्त तीन तुकड्यांची जागा बदलतो. पथकाला सर्व 4,000 वापरण्याजोग्या तीन-तुकड्यांच्या अदलाबदलींसाठी चालींचे क्रम सापडले, प्रत्येक जास्तीत जास्त 12 चालींचा.

दोन कल्पनांमुळे ही संख्या घटते. पहिली, तोच कम्युटेटर अनेक कुटुंबांवर एकाच वेळी, ओळी आणि स्तंभांच्या संपूर्ण गटांवर लागू करता येतो. दुसरी, प्रत्येक कुटुंब स्वतंत्रपणे सोडवण्याऐवजी, प्रत्येक कुटुंब अदलाबदलींच्या एकाच निश्चित सार्वत्रिक क्रमाचे (universal sequence) अनुसरण करते, आणि त्याला नको असलेल्या अदलाबदली फक्त वगळते. एक प्रमेयिका (lemma) सर्वकाही एकत्र बांधते: L टप्प्यांचा सार्वत्रिक क्रम L/2 इतका अग्र स्थिरांक (leading constant) देतो.

तो क्रम लहान करण्यासाठी संगणकशास्त्रातील वर्गीकरण जाळ्यांची (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 थर असलेल्या क्यूबच्या सोडवणुकीतील समान अंतराने घेतलेल्या आठ चौकटी: विस्कटलेली पृष्ठे एकसंध रंगांमध्ये बदलतात. — Figure 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

अल्गोरिदमला लागणारा वेळ तुकड्यांच्या संख्येच्या प्रमाणात असतो, आणि लेखकांनी एक मुक्त-स्रोत (open-source) सोडवणारा प्रोग्राम (solver) उपलब्ध करून दिला आहे, ज्यासोबत तो ज्या प्रत्येक जाळ्यावर अवलंबून आहे त्याची संपूर्ण तपासणी करणाऱ्या स्क्रिप्ट्स आहेत. त्यांच्या स्वतःच्या तुलनेत तो सुमारे n = 840 पासून विद्यमान सोडवणाऱ्या प्रोग्रामच्या पुढे जातो; त्यांनी प्रत्येक बाजूला 256 आणि 65,536 थर असलेल्या क्यूबच्या सोडवणुकीचे दृश्यरूपण (render) केले आहे.

2.37 हे एक अनंतस्पर्शी (asymptotic) विधान आहे: सूत्रातील लहान पदे निश्चित केलेली नाहीत, त्यामुळे ते एखाद्या विशिष्ट क्यूबसाठी चालींची अचूक संख्या देत नाही. लेखक सुचवतात की पुढील सुधारणा तुकड्यांना वर्गीकरण जाळ्यांमध्ये गटबद्ध करण्याच्या इतर मार्गांमधून आणि अधिक चांगल्या तीन-तुकड्यांच्या अदलाबदलींमधून येऊ शकतात — आणि हीच यंत्रणा इतर महाकाय कोडी, किंवा चार- आणि पाच-मितीय अतिघन (hypercubes) यांनाही हाताळू शकेल.