रूबिक के घन को प्रोग्रामेटिक रूप से

Question

हल करना मैं सी में रूबिक के घन को हल करने के लिए एक प्रोग्राम विकसित करने की कोशिश कर रहा हूं। मैंने इसके लिए ट्रैकिंग तकनीक का उपयोग किया। यह एक बहुत लंबी प्रक्रिया है और इसमें बहुत सी चीजें होती हैं, इसलिए मैं इसे हल करने में सक्षम नहीं हूं।

कृपया मुझे यह सुझाव दें कि इसे और अधिक कुशलता से कैसे हल करें - जैसे कि अन्य तकनीकों या बैकट्रैकिंग को अपनाना। Google में मुझे इसे हल करने के लिए बहुत सारे शॉर्टकट मिले लेकिन मैं शॉर्टकट का उपयोग करके इसे हल नहीं करना चाहता हूं।

Answer 1

मानव उन्मुख समाधान का उपयोग क्यों न करें और इसे प्रोग्राम करें।

आपको कुछ पैटर्न मिलान की आवश्यकता है, लेकिन यह कठिन नहीं होगा। (इसके अलावा 1000x1000x1000 को हल करने वाले कार्यक्रम भी हैं)।

• पहले परत
• दूसरा परत
• तीसरा परत

प्रत्येक परत के लिए आप उस पैटर्न एक्स बारी एल्गोरिदम के एक जोड़े को लागू:

मूल विचार चरणों में काम करने के लिए है पैटर्न एक्स 'में। एक चरण में प्रत्येक चरण को घन को हल करने के करीब ले जाना चाहिए। आप प्रत्येक पैटर्न में एक मूल्य जोड़कर ऐसा कर सकते हैं (जहां अधिक मूल्यवान क्यूब्स को उच्च मान दिए जाते हैं)। आप एक कठिनाई भी जोड़ सकते हैं (उदाहरण के लिए मोड़ों की संख्या) ताकि आप प्रति कठिनाई के सर्वोत्तम मूल्य लाभ (या कम से कम मोड़ के साथ सर्वोत्तम परिणाम तक पहुंचने के आधार पर एक एल्गोरिदम का चयन कर सकें)।

इस दृष्टिकोण का मजा यह है कि यदि आप पसंद करते हैं और परीक्षण करते हैं कि उनका कितनी बार उपयोग किया जाता है तो आप नए एल्गोरिदम जोड़ सकते हैं। तो आप प्रत्येक एल्गोरिदम की उपयोगिता का परीक्षण कर सकते हैं।

यदि आप वास्तव में उन geekpoints अर्जित करना चाहते हैं, तो एल्गोरिदम और पैटर्न को हल करने वाले पैटर्न का वर्णन करने के लिए एक अलग भाषा बनाएं।

Answer 2

मुझे यकीन नहीं है कि मैं आपकी समस्या को समझता हूं और शॉर्टकट द्वारा आपका क्या मतलब है। यदि आप रूबिक के घन को हल करने के लिए कुछ गतिशील प्रोग्रामिंग विधि का उपयोग कर रहे हैं तो आपको यह सुनिश्चित करने की आवश्यकता है कि आप समाधान तक पहुंचने के लिए आगे पर्याप्त कदम देख रहे हों। मेरा मानना ​​है कि यदि आप केवल 2 प्रकार की चालों का समर्थन करते हैं (दाएं घुमाएं, घुमाएं) तो समाधान सुनिश्चित करने के लिए आपको प्रत्येक चरण पर निर्णय लेने से पहले 12 चरणों (सुनिश्चित नहीं) को देखने की आवश्यकता है।

यदि आप ऐसा कुछ कर रहे हैं और आपको पता चला है कि आप स्मृति में जगह से बाहर हो गए हैं तो ध्यान रखें कि आपको सही समाधान पर निर्णय लेने के लिए केवल उस मार्ग को बनाए रखने की आवश्यकता है जिसे आप पार कर रहे हैं (पूरे नहीं पेड़)।

मैंने जावा में रुबिक के घन को हल करने के लिए सफलतापूर्वक इस दृष्टिकोण का उपयोग किया है, इसलिए सी को कोई समस्या नहीं होनी चाहिए (जहां तक ​​स्मृति पदचिह्न)।

Answer 3

वहाँ रूबिक समस्या को हल करने के लिए कई एल्गोरिदम, हालांकि, आप इस इष्टतम एक http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

Answer 4

रूबिक क्यूब राज्य 2 के क्रम में अंतरिक्ष आकार की है का उल्लेख कर सकते हैं। एक बैकट्रैकिंग एल्गोरिदम जो राज्य अंतरिक्ष को अंधेरे से खोजता है उसे समाधान खोजने से पहले राज्य के एक बड़े हिस्से की जांच करने की आवश्यकता हो सकती है, इसलिए स्पष्ट रूप से एक सरल बैकट्रैकिंग एल्गोरिदम बहुत अच्छी तरह से काम नहीं करेगा। लेकिन फिर, यह समस्या कई बार हल हो चुकी है। उदाहरण देखेंhttp://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

Answer 5

यदि आपको शामिल चाल की संख्या की परवाह नहीं है, तो यहां राज्य की जगह को विभाजित करने का एक तरीका है ताकि आपकी ब्रूटफोर्स विधि कार्य करे।

नौसिखियों के लिए एक rubix घन समाधान ढूँढना

• पहले bruteforce सभी rubix पहलुओं लेकिन स्थानों में कोनों
• तो चलता रहता है कि चलो अपरिवर्तनीय thoses पहलू को खोजने के (जैसे (FGF-1.g -1)^3)। दो चाल वास्तव में पर्याप्त हैं। उन्हें खोजने के लिए, कोनों और गैर कोनों के उपनुब्बियों के लिए शामिल क्रमपरिवर्तन पर विचार करें, और फिर कोनों पर प्राप्त करने और इनवेरिएंट करने के लिए कोनों के चक्र की लंबाई के पीपीसीएम को दोहराएं)
• स्थानों में कोनों को प्राप्त करने के लिए अपने बैकट्रैकिंग एल्गोरिदम का उपयोग करें (लेकिन वे अभी भी रंगों को संरेखित करने के लिए एक रोटेशन की आवश्यकता होती है)
• जादू चालें जो एक ही खंड पर एक साथ घूमने के लिए घूमती हैं। कोई कदम नहीं है