20 चरणों में रूबिक्स क्यूब

रूबिक क्यूब की किसी भी स्थिति को 20 से अधिक चरणों में हल नहीं किया जा सकता है।



कुछ साल पहले यह साबित हो गया था कि रुबिक के क्यूब के लिए 23 चालों का हल था। अब यह संख्या घटकर 20 हो गई है। ऐसा करने के लिए, Google द्वारा दान किए गए कंप्यूटर समय के 35 (पैंतीस) वर्ष लग गए।





प्रत्येक समाधान ब्लॉक ने अपने एल्गोरिथ्म का उपयोग किया - वांछित कॉन्फ़िगरेशन को प्राप्त करने के लिए चरणों का एक क्रम। उदाहरण के लिए, एक एल्गोरिथ्म ऊपरी चेहरे को हल करने के लिए डिज़ाइन किया गया था, और दूसरा मध्य किनारों को स्थिति में लाने के लिए। कई अलग-अलग एल्गोरिदम हैं जो कठिनाई की डिग्री और आवश्यक चरणों की संख्या में भिन्न होते हैं, लेकिन उन लोगों को याद कर सकते हैं जिन्हें आमतौर पर 40 से अधिक चरणों की आवश्यकता होती है।



यह मानना ​​उचित है कि भगवान अधिक कुशल एल्गोरिथ्म का उपयोग कर सकते हैं जो समस्या को कम से कम चरणों में हल करता है। इस एल्गोरिथ्म को "भगवान एल्गोरिथ्म" के रूप में जाना जाता है। सबसे खराब स्थिति संख्या को भगवान की संख्या कहा जाता है। अंत में, यह दिखाया गया कि यह संख्या 20 है।



रूबिक के क्यूब के आविष्कार के बाद, एक स्थिति खोजने में पंद्रह साल लग गए, जो 20 चरणों में हल होने की संभावना है। उसके 15 साल बाद, हम साबित करेंगे कि किसी भी स्थिति के लिए 20 कदम पर्याप्त हैं।

भगवान की संख्या की कहानी

1980 तक, यह स्थापित किया गया था कि निचली सीमा 18 है, और ऊपरी एक शायद लगभग 80 है। नीचे दी गई तालिका में सभी परिणाम शामिल हैं:

हमने यह कैसे किया

हमने रुबिक के क्यूब के 43 252 003 274 489 856 000 पदों के साथ कैसे व्यवहार किया?

• हमने सभी पदों को 2,217,093,120 सेटों में विभाजित किया है - प्रत्येक में 19,508,428,800 पद।
• हमने सेट की समरूपता और कवरेज के आधार पर समाधान के लिए सेट की संख्या को 55,888,296 तक कम कर दिया।
• हमने इष्टतम समाधान की तलाश नहीं की, लेकिन केवल 20 या उससे कम चरणों की लंबाई के साथ समाधान।
• हमने एक कार्यक्रम लिखा था जो 20 सेकंड में एक सेट के लिए समाधान ढूंढता है।
• 55,888,296 सेट में से प्रत्येक में सभी कॉन्फ़िगरेशन के समाधान खोजने के लिए कंप्यूटर के 35 वर्षों का समय लगा।

स्थिति स्थान विभाजन

हमने बड़े कार्य को 2,217,093,120 छोटे उपखंडों में विभाजित किया है: प्रत्येक में 19,508,428,800 विभिन्न पद शामिल हैं। इस तरह के एक उप योग को आसानी से एक आधुनिक कंप्यूटर की स्मृति में रखा जाता है, और इस पद्धति ने एक समाधान प्राप्त करना संभव बना दिया है।

समरूपता

यदि आप रूबिक के क्यूब को बाएं-दाएं या ऊपर-नीचे घुमाते हैं, तो, वास्तव में, कुछ भी नहीं बदलेगा: समाधान में चरणों की संख्या समान रहेगी। इन सभी पदों को हल करने के बजाय, आप एक के लिए एक समाधान प्राप्त कर सकते हैं और इसे घुमाए गए पदों तक बढ़ा सकते हैं। अंतरिक्ष में 24 अलग-अलग झुकाव हैं और प्रत्येक स्थिति के लिए क्यूब के 2 दर्पण स्थान हैं, जो हल किए गए पदों की संख्या को 48 गुना कम कर देता है। यदि हम समान तर्क का उपयोग करते हैं और "सेट को कवर करने" की समस्या के लिए खोज का उपयोग करते हैं, तो उप-संख्या की संख्या 2,217,093,120 से घटकर 55,882,296 हो जाती है।

अच्छा और इष्टतम समाधान

इष्टतम समाधान में पर्याप्त संख्या में चरण होते हैं, लेकिन आवश्यकता से अधिक नहीं। चूंकि एक स्थिति पहले से ही ज्ञात है जिसके लिए 20 चरणों की आवश्यकता होती है, हम प्रत्येक स्थिति के लिए इष्टतम समाधान नहीं खोज सकते, लेकिन केवल 20 या उससे कम चरणों में समाधान। यह कई बार कार्य को गति देता है।

उपकरण

हमारे पास Google की सुविधाओं में 55,882,296 उप-मुखौटे हल करने और कुछ हफ्तों में सभी गणनाओं को पूरा करने का अवसर था। Google कंप्यूटर की विशेषताओं का खुलासा नहीं करता है, लेकिन गणना पर 1.1 बिलियन सेकंड का कंप्यूटर समय (Intel Nehalem, फोर-कोर, 2.8GHz) खर्च किया गया।

सबसे कठिन मुद्रा

हम 15 वर्षों से जानते हैं कि ऐसी स्थितियाँ हैं जिनमें 20 चरणों की आवश्यकता होती है, लेकिन हमने यह साबित कर दिया है कि किसी एक पद की अधिक आवश्यकता नहीं है।



20 चरणों में समाधान वाले पद दुर्लभ हैं, लेकिन वास्तविकता में उनसे मिलना काफी संभव है। ऐसी स्थिति के मिलने की संभावना 10 ^ (- 9) से 10 ^ (- 8) तक भिन्न होती है। हम इस तरह के पदों की सही संख्या नहीं जानते हैं। तालिका प्रत्येक समाधान लंबाई के लिए पदों की संख्या का अनुमान देती है।





16 की लंबाई और अधिक के लिए, संख्या अनुमानित है। हमारे अध्ययनों ने लाइन 14 और सहित सभी प्रारंभिक डेटा की पुष्टि की, और लाइन 15 एक नया परिणाम है। 11 अगस्त को, हमने समाधान की लंबाई 20 के साथ 12 मिलियन स्थान पाया। यह स्थिति हमारे कार्यक्रमों के लिए सबसे कठिन थी: