খেলা − ধরুন বর্গের একটি n × n অ্যারে। এর মধ্যে, কিছু বর্গক্ষেত্র খালি, কিছু কঠিন এবং কিছু অ-সলিড বর্গ পূর্ণসংখ্যা 1, 2, 3, .... দ্বারা সেট করা হয়। প্রতিটি পূর্ণসংখ্যা বোর্ডে ঠিক দুটি ভিন্ন স্কোয়ার বজায় রাখে বা দখল করে। প্লেয়ারের কাজ হল বোর্ডে প্রতিটি পূর্ণসংখ্যার দুটি ঘটনাকে এককভাবে অনুভূমিক এবং উল্লম্ব আন্দোলন বাস্তবায়নের একটি সহজ পথের সাহায্যে সংযুক্ত করা। কোন দুটি ভিন্ন পথ একে অপরকে ছেদ করার অনুমতি নেই। কোন পাথে কোন কঠিন বর্গক্ষেত্র অন্তর্ভুক্ত থাকতে পারে না (কোন পাথে সলিড স্কোয়ার দেখানোর অনুমতি নেই)। সবশেষে, সমস্ত অ-সলিড স্কোয়ার অবশ্যই পাথ দিয়ে পূরণ করতে হবে।
অ্যালগরিদম − একটি প্রদত্ত বোর্ডের আকার n × n সহ একটি বৈধ এলোমেলো ধাঁধা তৈরি করতে, আমরা প্রথমে বোর্ডে র্যান্ডম সহজ পারস্পরিক ছেদহীন পাথ তৈরি করি। যদি কয়েকটি বিচ্ছিন্ন স্কোয়ার সমস্ত উত্পন্ন পথের বাইরে থেকে যায় তবে এই বিচ্ছিন্ন বর্গক্ষেত্রগুলিকে কঠিন (নিষিদ্ধ) হিসাবে চিহ্নিত করুন। এরপর আমরা পাজল হিসেবে পাথের শেষ বিন্দু এবং কঠিন বর্গক্ষেত্রের তালিকা সরবরাহ করি।
এইভাবে আমরা প্রথমে একটি সমাধান তৈরি করি এবং পরবর্তীতে সমাধান থেকে ধাঁধা বের করি। পাথ এবং কঠিন বর্গক্ষেত্র n × n বোর্ডকে বিভক্ত বা বিভাজন করে। এই পার্টিশনটি তৈরি করার জন্য আমরা একটি ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার বাস্তবায়ন করি। ডেটা স্ট্রাকচারটি বোর্ডে n^2 স্কোয়ারের সেটের উপসেটের সাথে কাজ করে।
সিউডোকোড
-
বোর্ডে এলোমেলোভাবে স্কোয়ার (a, b) এবং (c, d) সনাক্ত করুন যাতে −
-
(a, b) এবং (c, d) একে অপরের প্রতিবেশী, এবং
-
(a, b) বা (c, d) কোনটিই এখন পর্যন্ত উত্পাদিত কোন পথের অন্তর্গত নয়। যদি পুরো বোর্ডে এই ধরনের কোনো জোড়া বর্গক্ষেত্র পাওয়া না যায়, তাহলে ব্যর্থতা /* এখানে, (a, b) এবং (c, d) হল নতুন পাথ তৈরির প্রথম দুটি বর্গক্ষেত্র। */
-
-
(a, b) এবং (c, d) সম্বলিত দুটি ইউনিয়ন-খুঁজে গাছের একটি মিলন তৈরি করুন।
-
যতক্ষণ বর্তমান পথ প্রসারিত করা যায় ততক্ষণ পুনরাবৃত্তি করুন −
-
নাম পরিবর্তন করুন (a, b) =(c, d).
-
-
(a, b) এর একটি এলোমেলো প্রতিবেশী বর্গ (c, d) সনাক্ত করুন যাতে −
-
(c, d) এখন পর্যন্ত উত্পাদিত কোনো পথের অন্তর্গত নয় (বর্তমান সহ)
-
আংশিকভাবে নির্মিত বর্তমান পথে একমাত্র প্রতিবেশী (c, d) আছে (a, b)।
-
-
যদি এমন কোন প্রতিবেশী (c, d) খুঁজে না পাওয়া যায়, তবে পথটি আর বাড়ানো যাবে না, তাই লুপটি ভেঙে ফেলুন
-
অন্যথায়, দুটি ইউনিয়নের মিলন তৈরি করুন- (a, b) এবং (c, d) যে গাছের সাথে যুক্ত।
-
নতুন পথের শুরুতে এবং সমাপ্তির সময় দুটি স্কোয়ারের শেষবিন্দুর পতাকা সেট করুন।
-
সফলতা ফেরত
