रुबिक के घन के लिए भगवान की संख्या 20 है

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

थोड़ा इतिहास

क्यूब का आविष्कार 1974 में हुआ था। क्यूब के सैद्धांतिक अध्ययन ने क्यूब को हल करने के लिए अधिकतम संख्या में चाल की निचली और ऊपरी सीमाओं का आकलन करने पर ध्यान केंद्रित किया।



1980 तक, निचले बाउंड का अनुमान 18 के रूप में लगाया गया था: लंबाई 17 या उससे कम के चाल के अलग-अलग अनुक्रम क्यूब के कॉन्फ़िगरेशन से कम थे। यह मूल्यांकन 15 साल तक चला - 1995 तक, जब माइकल रीड ने साबित किया कि "सुपरफ्लिप" कॉन्फ़िगरेशन के लिए (दाएं कोनों और पक्षों के भ्रमित मध्य बिंदु) बिल्कुल 20 चालों की आवश्यकता है।



इस बीच, ऊपरी बाध्य अनुमान अधिक बार कम हो गया, लेकिन अधिक धीरे-धीरे: 1981 में यह 52 था, 1995 में उसी माइकल रीड को मूल्य 29 मिला, 2008 में टॉमस रोकिकी ने इसे 25-23-22 तक घटा दिया (23 चाल का अनुमान Habré :-)) पर एक लेख जीता, और अंत में जुलाई 2010 में उसी टोमाज़ रोकिकी ने, मॉर्ले डेविडसन, जॉन डेथ्रिज और हर्बर्ट सोशिएम्बा के साथ, अंतिम परिणाम प्राप्त किया - 20 चाल।

कैसे?

कुल 8 हैं! * ३ ¹² * १२! * 2 ¹⁰ = 43,252,003,274,489,856,000 ~ 4.3 * 10 ¹⁹ घन विन्यास। समरूपता और कवरिंग सेट का उपयोग करते हुए, उन्हें अनिवार्य रूप से अलग-अलग विन्यासों में घटाकर 55,882,296 कर दिया गया, जिसे ईमानदारी से हल किया जाना था। प्रत्येक कॉन्फ़िगरेशन के लिए कार्य को सरल बनाने के लिए, उन्होंने इष्टतम समाधान (यह भगवान का समाधान है) की तलाश नहीं की, लेकिन 20 या उससे कम चाल में समाधान।



अंत में, कॉन्फ़िगरेशन कई Google कंप्यूटरों के बीच वितरित किए गए, और गणना कुछ ही हफ्तों में पूरी हुई। एक अच्छे कंप्यूटर (Intel Nehalem, फोर-कोर, 2.8GHz) पर इन गणनाओं में 1.1 बिलियन सेकंड या 35 साल लगेंगे।

प्रतिक्रिया

हालांकि कई लोग व्यावहारिक मूल्य की कमी के लिए रूबिक क्यूब की आलोचना करते हैं, परिणाम अभी भी दिलचस्प है - कम से कम इसकी अंतिमता के लिए, क्योंकि न तो ऊपरी और न ही निचली सीमा को और आगे ले जाया जा सकता है। प्रसिद्ध (और आप स्वयं घन के शौकीन थे?) खुली समस्या हल हो गई है, आप शोधकर्ताओं को बधाई दे सकते हैं और कुछ और पर स्विच कर सकते हैं।



यह हास्यास्पद है कि इस परिणाम के बारे में जानने वाले बहुत से लोग यह कहते हैं कि Google के पास कंप्यूटिंग शक्ति डालने के लिए कहीं नहीं है जो कैंसर की समस्या को हल कर सकता है। ठीक है, अगर कोई वास्तव में सिर्फ 35 सीपीयू-वर्षों (और उनके काम के कई वर्षों) में कैंसर का इलाज पा सकता है, तो मुझे लगता है कि Google उन्हें उन्हें देने में प्रसन्न होगा।

सूत्रों का कहना है

1. भगवान की संख्या 20 है

2. रुबिक का क्यूब विकिपीडिया पर

3. रेडिट पर समाचार की चर्चा