রিকার্সিভ ব্যাকট্র্যাকার গোলকধাঁধা জেনারেটর

রিকার্সিভ ব্যাকট্র্যাকার অ্যালগরিদম আসলে একটি সাধারণ উদ্দেশ্যের গভীরতা-প্রথম অনুসন্ধান। যখন মেজ জেনারেশনের জন্য ব্যবহার করা হয়, তখন এলোমেলোভাবে পথ বেছে নেওয়ার জন্য এটিকে কিছুটা পরিবর্তন করা হয়, যেখানে প্রকৃত অনুসন্ধানের উদ্দেশ্যে ব্যবহার করা হলে, সাধারণত প্রতিটি স্তরকে রৈখিক ক্রমে অনুসন্ধান করা হয়। এটি দীর্ঘ, ঘূর্ণায়মান করিডোর এবং একটি খুব দীর্ঘ, মোচড়ের সমাধান সহ মেজ তৈরি করে।

একটি নিখুঁত গোলকধাঁধা হল এমন একটি গোলকধাঁধা যেখানে গোলকধাঁধার যেকোনো বিন্দু থেকে অন্য যেকোনো বিন্দুতে ঠিক একটি পথ থাকে। এর মানে হল আপনি বৃত্তাকারে ঘুরে বেড়াতে পারবেন না, তবে আপনি প্রায়শই অচল প্রান্তের মুখোমুখি হবেন, যা আপনাকে ঘুরে ফিরে যেতে বাধ্য করবে।

এখানে তৈরি করা গোলকধাঁধা মানচিত্রগুলিতে কোনও শুরু এবং শেষ অবস্থান ছাড়াই একটি ডিফল্ট সংস্করণ রয়েছে, তাই আপনি নিজেই সেগুলি সিদ্ধান্ত নিতে পারেন: গোলকধাঁধার যেকোনো বিন্দু থেকে অন্য যেকোনো বিন্দুতে একটি সমাধান থাকবে। আপনি যদি অনুপ্রেরণা চান, তাহলে আপনি একটি প্রস্তাবিত শুরু এবং শেষ অবস্থান সক্ষম করতে পারেন - এবং এমনকি উভয়ের মধ্যে সমাধানও দেখতে পারেন।

রিকার্সিভ ব্যাকট্র্যাকার অ্যালগরিদম হল একটি গভীরতা-প্রথম অনুসন্ধান পদ্ধতি যা নিখুঁত গোলকধাঁধা তৈরি করে (কোনও লুপ ছাড়াই এবং যেকোনো দুটি বিন্দুর মধ্যে একটি একক পথ ছাড়াই গোলকধাঁধা)। এটি সহজ, দক্ষ এবং দীর্ঘ, ঘুরানো করিডোর সহ দৃশ্যত আকর্ষণীয় গোলকধাঁধা তৈরি করে।

নাম সত্ত্বেও, এটি রিকার্সন ব্যবহার করে বাস্তবায়িত করার প্রয়োজন হয় না। এটি প্রায়শই LIFO কিউ (অর্থাৎ একটি স্ট্যাক) ব্যবহার করে একটি পুনরাবৃত্ত পদ্ধতিতে বাস্তবায়িত হয়। খুব বড় মেজগুলির জন্য, প্রোগ্রামিং ভাষা এবং উপলব্ধ মেমোরির উপর নির্ভর করে রিকার্সন ব্যবহারের ফলে কল স্ট্যাক ওভারফ্লো হওয়ার সম্ভাবনা বেশি। একটি LIFO কিউকে প্রচুর পরিমাণে ডেটা পরিচালনা করার জন্য আরও সহজেই অভিযোজিত করা যেতে পারে, এমনকি যদি উপলব্ধ মেমোরি অপর্যাপ্ত হয় তবে কিউটি ডিস্কে বা ডাটাবেসে রাখাও সম্ভব।

কিভাবে এটা কাজ করে

অ্যালগরিদমটি স্ট্যাক-ভিত্তিক গভীরতা-প্রথম অনুসন্ধান পদ্ধতি ব্যবহার করে কাজ করে। ধাপে ধাপে ব্রেকডাউন এখানে দেওয়া হল:

1. একটি প্রারম্ভিক ঘর নির্বাচন করুন এবং এটিকে পরিদর্শন করা হয়েছে হিসাবে চিহ্নিত করুন।
2. যখন অযাচিত কোষ থাকে: তখন পাশের কোষগুলি দেখুন যেগুলি এখনও পরিদর্শন করা হয়নি। যদি কমপক্ষে একটি অযাচিত প্রতিবেশী থাকে: এলোমেলোভাবে অযাচিত প্রতিবেশীদের মধ্যে একটি নির্বাচন করুন। বর্তমান কোষ এবং নির্বাচিত প্রতিবেশীর মধ্যে প্রাচীরটি সরিয়ে ফেলুন। নির্বাচিত প্রতিবেশীর কাছে যান এবং এটি পরিদর্শন করা হিসাবে চিহ্নিত করুন। বর্তমান কোষটিকে স্ট্যাকের উপর চাপ দিন। যদি কোনও অযাচিত প্রতিবেশী না থাকে: স্ট্যাক থেকে শেষ কোষটি পপ করে ফিরে যান।
3. স্ট্যাকটি খালি না হওয়া পর্যন্ত এই প্রক্রিয়াটি চালিয়ে যান।

এই অ্যালগরিদম সম্পর্কে একটি আকর্ষণীয় তথ্য হল এটি একটি গোলকধাঁধা জেনারেটর এবং একটি গোলকধাঁধা সমাধানকারী উভয় হিসাবেই কাজ করে। যদি আপনি এটি ইতিমধ্যে তৈরি হওয়া গোলকধাঁধায় চালান এবং নির্ধারিত শেষ বিন্দুতে পৌঁছানোর পরে থামেন, তাহলে স্ট্যাকে গোলকধাঁধার সমাধান থাকবে।

এই সাইটে আমার কাছে এই অ্যালগরিদমের দুটি সংস্করণ আছে: এই পৃষ্ঠায় গোলকধাঁধা তৈরির জন্য LIFO কিউ ভিত্তিক একটি এবং গোলকধাঁধা সমাধানের জন্য একটি পুনরাবৃত্তি ভিত্তিক একটি, অন্যান্য অ্যালগরিদম দ্বারাও গোলকধাঁধা তৈরি করা হয় (সমাধান সহ মানচিত্রগুলি এভাবেই তৈরি করা হয়)। দুটি ভিন্ন সংস্করণ থাকা কেবল খেলাধুলার জন্য কারণ আমি একজন বোকা এবং এটি আকর্ষণীয় বলে মনে করি, যে কোনও একটি উভয়ের জন্যই কাজ করতে পারত ;-)

আরও পড়ুন

যদি আপনি এই পোস্টটি উপভোগ করেন, তাহলে আপনার এই পরামর্শগুলিও পছন্দ হতে পারে:

• বৃক্ষ বৃদ্ধির অ্যালগরিদম গোলকধাঁধা জেনারেটর
• এলারের অ্যালগরিদম গোলকধাঁধা জেনারেটর
• হান্ট অ্যান্ড কিল মেজ জেনারেটর