मेरे पास एक यादृच्छिक अनुक्रम में 35 संख्याओं (1 ~ 35) के साथ 6 * 6 पहेली है। रिक्त स्थान को 'रजिस्टर' के रूप में उपयोग करें और संख्याओं को एक-एक करके क्रमबद्ध करने के लिए स्थानांतरित करें। मैं 3 * 3 पहेली से निपट सकता हूं, लेकिन 6 * 6 एक से निपटने के लिए कैसे? क्या आप मुझे कुछ संकेत दे सकते हैं? 
6 * 6 पहेली एल्गोरिदम
विचार एक ही है, एक राज्यों graph के रूप में समस्या का प्रतिनिधित्व करते हैं, और shortest path एल्गोरिथ्म चलाते हैं।
तो एल्गोरिथम की प्रभाविता महत्वपूर्ण है, आपके पास एक बेहतर एल्गोरिथ्म चाहते हो सकता है -such A* algorithm है, जो सुंदर एक अच्छा admissible heuristic function साथ तेजी से (विकल्प के सापेक्ष) होने की उम्मीद है के रूप में।
एक धीमा हालांकि सरल समाधान BFS चला रहा है।
दोनों एल्गोरिदम (ए *, BFS) कर रहे हैं दोनों पूरा (हमेशा एक solutuion पाता है, यदि कोई है) और इष्टतम (कम से कम पथ पाता है)।
यह भी ध्यान दें, आप मैक्रोज़ का उपयोग की चाल की "अच्छी" श्रृंखला सीखने के लिए कर सकते हैं, ताकि एल्गोरिदम तेजी से प्राप्त हो सके। जब तक आप एक काम (हालांकि धीमी) समाधान लागू नहीं करते हैं, तब तक इस सुधार को अनदेखा करें।
संपादित करें: कोडिंग के दिशा निर्देशों: एक ग्राफ के रूप में समस्या पर
देखो: ग्राफ किया जाएगा G=(V,E) जहां V = { all possible states} और E = { (u,v) | can move from state u to state v within a single step }
अब, यह ग्राफ के साथ - आप एक प्रारंभिक स्थिति है (स्रोत, जो इनपुट के रूप में दिया जाता है) और एक लक्ष्य (एक क्रमबद्ध पहेली)। स्रोत से गंतव्य तक पथ खोजने के लिए, बीएफएस या ए * शुरू करें (संलग्न विकिपीडिया लिंक में इन छद्म कोड पर एक नज़र डालें)। आपको बीएफएस से शुरू करना चाहिए - यह आसान है।
सबसे कम पथ एल्गोरिदम द्वारा लौटा गया पथ प्रारंभिक बोर्ड से लक्ष्य तक पहुंचने के लिए आपको चलने वाली चालों की श्रृंखला के समान है।
नोट: आपको वास्तविक ग्राफ बनाने की आवश्यकता नहीं है! आपको केवल प्रारंभिक नोड (स्रोत) को पकड़ने की आवश्यकता है - और इसकी वर्टेक्स बनाएं, और successors:V->2^V फ़ंक्शन करें, जो आपको प्रत्येक चरम के लिए उत्तराधिकारी देता है (औपचारिक रूप से: successors(v) = { (v,u) | (v,u) is in E })। इस तरह, आप फ्लाई पर ग्राफ के प्रासंगिक भाग का निर्माण कर सकते हैं।
दक्षता शायद इस छोटे से मैट्रिक्स में एक गैर-मुद्दा है, खासकर अगर यह होमवर्क या सीखने की समस्या है। –
ईमानदार होने के लिए, मुझे नहीं पता कि इस समस्या को कैसे हल किया जाए और यह उत्तर मदद नहीं करता है। बहुत ही उच्च स्तर का छद्म कोड यह दिखाने का एक अच्छा तरीका होगा कि यह कैसे किया जाएगा। –
@ टाइयलर: यह उत्तर मानता है कि ओपी पहले से ही इस रणनीति का उपयोग 3x3 के लिए करता है, लेकिन यह 6x6 के लिए काम करने के लिए पर्याप्त तेज़ नहीं है। ओपी से अधिक जानकारी के बिना, हम वास्तव में अब समस्या नहीं कर सकते हैं। –
इस गेम के लिए एक सरल रणनीति शीर्ष पंक्ति पर सही संख्या डाल दी गई है (यह आसान होना चाहिए क्योंकि आपको अन्य नंबरों की परवाह नहीं है, अंतिम दो संख्याएं सही जगह पर रखना मुश्किल है क्योंकि आपको दोनों को एक ही आंदोलन में रखना होगा), फिर आप शीर्ष पंक्ति को फ्रीज करें और बाएं कॉलम के साथ जारी रखें और फिर बाएं कॉलम के साथ ...
यह इष्टतम रणनीति नहीं है लेकिन यह वह है जो काम करता है और कोड के लिए आसान है।
जब मैं कॉलेज में था तब मैंने इसी समस्या/पहेली का अध्ययन किया है और इसकी एक बहुत ही रोचक समस्या है जिसमें एआई और हेरिस्टिक तकनीकों और ग्राफ-सिद्धांत शामिल हैं। जैसा कि अमित द्वारा बताया गया है, आपको ए *, बीएफएस और हेरिस्टिक्स की जांच करने की दृढ़ता से अनुशंसा की जाती है।
यहां मेरा योगदान है: इसे हल करने का प्रयास करते समय, आप रणनीति को जीतने के लिए विभाजित कर सकते हैं।आप सोच सकते हैं कि यह 6x6 ग्रिड सिर्फ चार 3x3 ग्रिड एक दूसरे के करीब है, और किसी दिए गए क्रम में अलग-अलग मामलों के रूप में हल करने का प्रयास करें।
उदाहरण के लिए, आप निम्नलिखित कलन विधि की कोशिश कर सकते हैं:
अंतिम मुद्दा कहने के लिए है कि आप चाहिए वेतन ध्यान जो कोने पर आप अंतरिक्ष काम कर के रूप में आप नहीं कर सकते ऊपरी-दाएँ ग्रिड के ऊपरी-दाएँ कोने अपने काम की जगह "होने के रूप में छोड़ वाला लापता टुकड़े "क्योंकि भविष्य में एक टुकड़ा रखना संभव नहीं होगा;
Ps1: काम करने की जगह वह स्थिति है जिसे आप अस्थायी रूप से टुकड़े करने देते हैं, ताकि टुकड़े टुकड़े करने के लिए एक खाली जगह हो सके;
Ps2: इस संदर्भ में, ग्रिड एनएक्सएन टुकड़ों का संयोजन है, जो सभी सही टुकड़ों को रोकता है, जरूरी नहीं।
आशा है कि मैंने किसी भी तरह से मदद की है। :-)
भी आपको धन्यवाद। आप और अमित दोनों मुझे बहुत मदद देते हैं :-) – tmj
मुझे लगता है कि अगर हम पूरे 6 * 6 मैट्रिक्स को पार करेंगे तो हम केवल एक छोटी संख्या पा सकेंगे और इसे अगले मैट्रिक्स में ले जायेंगे जो प्रासंगिक समाधान नहीं है। इस समस्या को हल करने का बेहतर तरीका दिए गए मैट्रिक्स पर बाइनरी खोज का उपयोग करता है। अगर हम बाइनरी खोज को लागू करेंगे तो उच्च समय की जटिलता होगी। तो इस समस्या को हल करने का बेहतर तरीका क्या है
सभी को आपसे अनुरोध किया गया है कि सभी को नीचे दिए गए कोड में देखें। नीचे कोड उपरोक्त समस्या का समाधान है। मैंने सम्मिलन सॉर्ट का उपयोग करके उपर्युक्त समस्या हल की है। बीएफएस या किसी का उपयोग करने की आवश्यकता नहीं है। सामग्री –
मैंने उपरोक्त हल किया है सॉर्ट एल्गोरिदम डालने का उपयोग करके पहेली। उपर्युक्त पहेली को हल करने में लगभग 2 दिन लग गए। बस नीचे चलाएं। नेट कोड अगर आपको कुछ पूछना है तो बस मुझे एक संदेश छोड़ दें। मैंने उपर्युक्त समस्या को हल करने के लिए किसी भी सी # इनबिल्ट क्लास का उपयोग नहीं किया है। यह कोड
private static void MazePuzzle()
{
/****
* A typical C Problem for Maze puzzle has been solved by prince.It took almost 3 days.
* Problem is about Sorting a 2D Matrix with any number of row and column
* This problem is also known as Rat Maze puzzle
* It is also be a typical Backtracking Problem
* ***/
const int _row = 6;
const int _coloumn = 6;
//int _column1 = _coloumn;
int[,] _doubleArray = new int[_row, _coloumn] { { 19, 2, 4, 34, 23, 41 }, { 11, 63, 3, 93, 65, 98 }, { 12, 80, 15, 76, 71, 90 }, { 119, 32, 94, 84, 23, 41 }, { 129, 232, 124, 341, 253, 411 }, { 197, 289, 47, 343, 293, 401 } };
int [] _StoringArray1D=new int[_row*_coloumn];
int i = 0;
int j = 0;
int _comparingArrayElement = 0;
int _swipeTemp = 0;
for (; i < _row; i++)
{
int _trackrow = 0;
for (;j <_coloumn; j++)
{
_trackrow = 0;
if(i==0 && j==0)
{
_comparingArrayElement= _doubleArray[i, j + 1];
if(_comparingArrayElement<_doubleArray[i,j])
{
_swipeTemp = _doubleArray[i,j+1];
_doubleArray[i, j + 1] = _doubleArray[i, j];
_doubleArray[i, j] = _swipeTemp;
}//innerMost if
}//For First time
else
{
int k = 0;
do
{
if (_trackrow == i || _trackrow < i)
{
for (; k < _coloumn; k++)
{
if(k==j && i==_trackrow)
{
break;
}
else
{
if(_doubleArray[_trackrow,k]>_doubleArray[i,j])
{
int _swipetempPrevious=_doubleArray[_trackrow,k];
_doubleArray[_trackrow,k]=_doubleArray[i,j];
_doubleArray[i, j] = _swipetempPrevious;
}
else
{
//do nothing just traverse
}//swipe else
}//k==j else
}//inner for do while
_trackrow++;
k = 0;
}//trackrow if
else
{
break;
}//trackrow else
} while (true);
}//else
}//innner for
j = 0;
}//outer for
Console.WriteLine("End of Program");
}//Maze Puzzle Method
इस होमवर्क के साथ एक शुद्ध सी लॉजिक कोड समाधान है। –
आप 3x3 मामले से कैसे निपटते हैं? –
* कोई * यादृच्छिक अनुक्रम? यहां तक कि अयोग्य भी? – harold