पुनरावर्ती ब्याकट्रैकर भूलभुलैया जेनरेटर

पुनरावर्ती ब्याकट्रैकर एल्गोरिदम वास्तवमा एक सामान्य उद्देश्य गहिराइ-पहिलो खोजी हो। जब भूलभुलैया उत्पादनको लागि प्रयोग गरिन्छ, यो अनियमित रूपमा बाटो छनौट गर्न थोरै परिमार्जन गरिएको छ, जबकि यदि वास्तविक खोजी उद्देश्यहरूको लागि प्रयोग गरिएको छ भने, एक सामान्यतया प्रत्येक स्तरलाई रैखिक क्रममा खोजी गर्दछ। यसले लामो, घुमाउरो कोरिडोरहरू र धेरै लामो, घुमाउरो समाधानको साथ भूलभुलैयाहरू उत्पादन गर्दछ।

उत्तम भूलभुलैया भनेको त्यस्तो भूलभुलैया हो जहाँ भूलभुलैयाको कुनै पनि बिन्दुबाट अर्को कुनै पनि बिन्दुमा ठ्याक्कै एउटा बाटो हुन्छ। यसको मतलब तपाईं सर्कलमा घुम्न सक्नुहुन्न, तर तपाईंले प्रायः मृत छेउहरू भेट्नुहुनेछ, जसले गर्दा तपाईंलाई फर्केर फर्कन बाध्य पार्छ।

यहाँ उत्पन्न गरिएको भूलभुलैया नक्सामा कुनै पनि सुरुवात र अन्त्य स्थिति बिना पूर्वनिर्धारित संस्करण समावेश छ, त्यसैले तपाईं आफैंले ती निर्णय गर्न सक्नुहुन्छ: भूलभुलैयाको कुनै पनि बिन्दुबाट अन्य कुनै पनि बिन्दुमा समाधान हुनेछ। यदि तपाईं प्रेरणा चाहनुहुन्छ भने, तपाईंले सुझाव गरिएको सुरुवात र अन्त्य स्थिति सक्षम गर्न सक्नुहुन्छ - र दुई बीचको समाधान पनि हेर्न सक्नुहुन्छ।

पुनरावर्ती ब्याकट्र्याकर एल्गोरिथ्म सही भूलभुलैया उत्पन्न गर्नका लागि एक गहिराइ-पहिलो खोजी विधि हो (कुनै लूपहरू र कुनै पनि दुई बिन्दुहरू बीच एकल मार्गको साथ भूलभुलैया)। यो सरल, कुशल छ, र लामो, घुमावदार कोरिडोरको साथ नेत्रहीन आकर्षक भूलभुलैया उत्पादन गर्दछ।

यसको नामको बावजुद, यो पुनरावृत्ति प्रयोग गरेर लागू गर्न आवश्यक छैन। यो प्राय: एलआईएफओ कतार (अर्थात् स्ट्याक) प्रयोग गरेर पुनरावृत्ति दृष्टिकोणमा लागू गरिन्छ। धेरै ठूलो भूलभुलैयाको लागि, पुनरावृत्ति प्रयोग गर्दा प्रोग्रामिंग भाषा र उपलब्ध मेमोरीमा निर्भर गर्दै कल स्ट्याक ओभरफ्लोमा परिणाम हुने सम्भावना बढी हुन्छ। उपलब्ध मेमोरी अपर्याप्त भएमा एलआईएफओ लाइनलाई ठूलो मात्रामा डेटा ह्यान्डल गर्न अझ सजिलै अनुकूलन गर्न सकिन्छ, यदि उपलब्ध मेमोरी अपर्याप्त छ भने डिस्कमा वा डाटाबेसमा लाइन राख्न पनि।

यो कसरी काम गर्दछ

एल्गोरिथ्म स्ट्याक-आधारित गहिराइ-पहिलो खोजी दृष्टिकोण प्रयोग गरेर सञ्चालन गर्दछ। यहाँ चरण-दर-चरण ब्रेकडाउन छ:

1. सुरुआत कक्ष रोज्नुहोस् र यसलाई भ्रमण गरिएको रूपमा चिनो लगाउनुहोस् ।
2. जबकि त्यहाँ नहेरिएका कक्षहरू छन्:
   • छिमेकी कक्षहरू हेर्नुहोस् जुन अहिलेसम्म भ्रमण गरिएको छैन।
   • यदि कम्तिमा एक नहेरिएको छिमेकी अवस्थित छ भने:
     • अनियमित रूपमा नदेखेका छिमेकीहरू मध्ये एक रोज्नुहोस्।
     • हालको कक्ष र रोजेको छिमेकीबीचको भित्ता हटाउनुहोस् ।
     • छानिएको छिमेकीमा सार्नुहोस् र यसलाई भ्रमण गरिएको रूपमा चिनो लगाउनुहोस्।
     • हालको कक्षलाई स्ट्याकमा धकेल्नुहोस् ।
   • यदि नदेखेका छिमेकीहरू अवस्थित छैनन् भने:
     • स्ट्याकबाट अन्तिम सेल पप गरेर ब्याकट्रयाक गर्नुहोस्।
3. स्ट्याक खाली नभएसम्म यो प्रक्रिया जारी राख्नुहोस् ।

यस एल्गोरिदमको बारेमा एक रोचक तथ्य यो हो कि यसले भूलभुलैया जनरेटरको रूपमा र भूलभुलैया समाधानकर्ताको रूपमा दुवै काम गर्दछ। यदि तपाईं यसलाई पहिले नै उत्पन्न भूलभुलैयामा चलाउनुहुन्छ र निर्णय गरिएको अन्त्य बिन्दुमा हिट गर्दा रोक्नुहोस्, स्ट्याकले भूलभुलैयाको समाधान समावेश गर्दछ।

म वास्तवमा यस साइटमा प्लेमा यस एल्गोरिदमको दुई संस्करणहरू छन्: यस पृष्ठमा भूलभुलैया उत्पन्न गर्न को लागी एक लिफो कतार आधारित छ र भूलभुलैया को समाधान को लागि एक पुनरावृत्ति आधारित छ, अन्य एल्गोरिदम द्वारा उत्पन्न भूलभुलैया पनि (समाधान संग नक्शा कसरी बनाइन्छ)। दुई फरक संस्करणहरू हुनु खेलको लागि मात्र हो किनकि म एक बेवकूफ हुँ जसले यसलाई रोचक भेट्टाउँछ, या त दुबैको लागि काम गर्न सक्थ्यो ;-)