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

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

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

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

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

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

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

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

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

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

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