रिकर्सिव बैकट्रैकर भूलभुलैया जनरेटर

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

एक आदर्श भूलभुलैया वह भूलभुलैया होती है जिसमें भूलभुलैया के किसी भी बिंदु से किसी अन्य बिंदु तक जाने के लिए बिल्कुल एक ही रास्ता होता है। इसका मतलब है कि आप चक्कर लगाते हुए नहीं रह सकते, लेकिन आप अक्सर ऐसे रास्ते पर आएँगे जहाँ आपको पीछे मुड़ना होगा और वापस लौटना होगा।

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

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

इसके नाम के बावजूद, इसे जरूरी नहीं कि रिकर्सन का उपयोग करके लागू किया जाए। इसे अक्सर LIFO कतार (यानी स्टैक) का उपयोग करके पुनरावृत्त दृष्टिकोण में लागू किया जाता है। बहुत बड़ी भूलभुलैया के लिए, रिकर्सन का उपयोग करने से कॉल स्टैक ओवरफ़्लो होने की अधिक संभावना होती है, जो प्रोग्रामिंग भाषा और उपलब्ध मेमोरी पर निर्भर करता है। LIFO कतार को बड़ी मात्रा में डेटा को संभालने के लिए अधिक आसानी से अनुकूलित किया जा सकता है, यहां तक ​​कि अगर उपलब्ध मेमोरी अपर्याप्त है तो कतार को डिस्क या डेटाबेस में भी रखा जा सकता है।

यह काम किस प्रकार करता है

यह एल्गोरिथ्म स्टैक-आधारित डेप्थ-फर्स्ट सर्च दृष्टिकोण का उपयोग करके संचालित होता है। यहाँ चरण-दर-चरण विवरण दिया गया है:

1. एक प्रारंभिक सेल चुनें और उसे विज़िट किया गया के रूप में चिह्नित करें.
2. जबकि कुछ कक्ष ऐसे हैं जहां कोई नहीं आया है:
   • उन पड़ोसी कोशिकाओं को देखें जिन पर अभी तक कोई नहीं गया है।
   • यदि कम से कम एक ऐसा पड़ोसी मौजूद है जिसका दौरा नहीं हुआ है:
     • यादृच्छिक रूप से किसी एक अप्रयुक्त पड़ोसी को चुनें।
     • वर्तमान सेल और चुने गए पड़ोसी सेल के बीच की दीवार को हटाएँ।
     • चुने हुए पड़ोसी के पास जाएँ और उसे विज़िट किए गए के रूप में चिह्नित करें।
     • वर्तमान सेल को स्टैक पर धकेलें.
   • यदि कोई भी अनजान पड़ोसी मौजूद न हो तो:
     • स्टैक से अंतिम सेल को हटाकर बैकट्रैक करें।
3. इस प्रक्रिया को तब तक जारी रखें जब तक स्टैक खाली न हो जाए।

इस एल्गोरिथ्म के बारे में एक दिलचस्प तथ्य यह है कि यह भूलभुलैया जनरेटर और भूलभुलैया सॉल्वर दोनों के रूप में काम करता है। यदि आप इसे पहले से ही जेनरेट की गई भूलभुलैया पर चलाते हैं और तय किए गए अंतिम बिंदु पर पहुँचने पर रुक जाते हैं, तो स्टैक में भूलभुलैया का समाधान शामिल होगा।

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