টাওয়ার্স অফ হ্যানয় (Towers of Hanoi)

আমরা যদি recursion বা পৌনঃপুনিকতার অনুশীলনীটি অনুশীলন করে থাকি, তাহলে আমরা আরও একটি অনুশীলনী অনুশীলন করবার জন্য তৈরি, যেখানে পুনরাবৃত্তি (recursion) খুবই কাজে দিতে পারে। এটাকে টাওয়ার্স অফ হ্যানয় (Towers of Hanoi) বলা হয়। তোমাকে তিনটি লাঠির একটি সেট এবং $n$‍ সংখ্যক ডিস্ক দেওয়া হল যার প্রতিটি ডিস্ক আবার ভিন্ন ভিন্ন আকারের। লাঠিগুলোর নাম দেওয়া যাক A, B এবং C আর ডিস্কগুলোকে সংখ্যা দিয়ে প্রকাশ করা যাক- সবচেয়ে ছোট ডিস্ককে 1 সংখ্যাটি দিয়ে এবং $n$‍ দিয়ে সবচেয়ে বড় ডিস্ককে প্রকাশ করা যাক। একদম শুরুতে, সবগুলো $n$‍ ডিস্ক লাঠি A তে আছে, এখন লাঠিটিতে থাকা ডিস্কগুলোকে এমনভাবে সাজাতে হবে যেন, লাঠিটির নিচে থেকে উপরে ডিস্কগুলো তাদের আকার অনুযায়ী বড় থেকে ছোট ক্রম অনুসারে সাজান থাকে অর্থাৎ ডিস্ক $n$‍ থাকবে সবচেয়ে নিচে এবং ডিস্ক 1 থাকবে সবচেয়ে উপরে। এখান টাওয়ার্স অফ হ্যানয় দেখতে কেমন হবে, যেখানে ডিস্কের সংখ্যা হল $n=5$‍টি তার একটি চিত্র দেওয়া হল:

এখানে আমাদের লক্ষ্য হল এই সবগুলো $n$‍ সংখ্যক ডিস্ককে লাঠি A থেকে সরিয়ে লাঠি B তে নিয়ে আসা:

শুনে বেশ সহজ বলে মনে হচ্ছে, তাই না? কিন্তু এটা এতো সহজও নয়, কারণ এখানে তোমাকে দুইটি নিয়ম মেনে কাজটি সম্পন্ন করতে হবে:

তুমি হয়তো চিন্তা করতে পার যে, এই সমস্যাটি এতো বেশি গুরুত্বপূর্ণ নয়। Au contraire! এশিয়া মহাদেশের কোন অঞ্চলে লোককাহিনী আছে (তিব্বত, ভিয়েতনাম, ভারত—ইন্টারনেট থেকে যে লোককাহিনীই তুমি খুঁজে বের কর না কেন), সন্ন্যাসীরা এই সমস্যাটি সমাধান করার চেষ্টা করে 64 টি ডিস্ক ব্যবহার করার মাধ্যমে, আর—গল্প চালু আছে,—সন্ন্যাসীরা বিশ্বাস করে যে যদি তারা নিয়ম অনুসরণ করে এই 64 টি ডিস্ক লাঠি A থেকে সরিয়ে লাঠি B তে নেওয়া শেষ করে ফেলে তাহলে এই পৃথিবী ধ্বংস হয়ে যাবে। সন্ন্যাসীদের কথা যদি সত্যি হয়, আমাদের কি তাহলে ভয় পাওয়া উচিৎ নয়?

প্রথমেই দেখা যাক আমরা কীভাবে পৌনঃপুনিকতা (recursively) ব্যবহার করে এই সমস্যাটি সমাধান করতে পারি। আমরা একদম সহজ অবস্থা থেকে কাজটি শুরু করব: একটি ডিস্ক দিয়ে, সেটা হল, $n=1$‍। $n=1$‍ হবে আমাদের সমস্যাটি সমাধান করার একদম ভিত্তি। তুমি সব সময়ই ডিস্ক 1 কে লাঠি A থেকে লাঠি B তে নিয়ে যেতে পারবে, কারণ তুমি জানো যে এই ডিস্কের নিচে থাকা যেকোন ডিস্ক এর থেকে বড় হতে হবে। এবং লাঠি A এবং B এর ক্ষেত্রে বিশেষ কোন কিছু নেই। তুমি যদি চাও তাহলে তুমি ডিস্ক 1 কে লাঠি B থেকে লাঠি C তে সরিয়ে নিতে পার অথবা লাঠি C থেকে লাঠি A তে অথবা যে কোন লাঠি থেকে যে কোন লাঠিতে ডিস্কগুলো সরিয়ে নিতে পার। একটি ডিস্ক দিয়ে টাওয়ার্স অফ হ্যানয় সমাধান করা খুবই সহজ একটি ব্যাপার এবং এই ক্ষেত্রে আমাদের এক সময়ে শুধুমাত্র একটি ডিস্কই সরানোর প্রয়োজন পড়বে।

দুইটি ডিস্কের সময় তাহলে কি হবে? আমরা কীভাবে একটি সমস্যা সমাধান করতে পারি যখন $n=2$‍ হবে? আমরা এই সমস্যাটি তিনটি ধাপে সমাধান করতে পারি। এটি শুরুতে দেখতে কেমন হবে তার একটি চিত্র এখানে দেওয়া হল:

শুরুতে, ডিস্ক 1 কে লাঠি A থেকে সরিয়ে লাঠি C তে নিতে হবে:

এখানে লক্ষ্য করা যাচ্ছে যে আমরা লাঠি C কে অতিরিক্ত একটি লাঠি হিসেবে ব্যবহার করব যেখানে আমরা ডিস্ক 1 কে রাখতে পারব যাতে আমরা ডিস্ক 2 টি নিয়ে কাজ করতে পারি। এখন ডিস্ক 2 টি—যেটা হল সবচেয়ে নিচের ডিস্ক—আমাদের সামনে চলে এল আর এই ডিস্কটি এখন আমরা লাঠি B তে সরিয়ে নিতে পারি:

সবশেষে, ডিস্ক 1 টি লাঠি C থেকে লাঠি B সরিয়ে নিয়ে আসা যাক:

এই সমাধানটি পেতে আমাদের তিনটি ধাপ অতিক্রম করতে হয়েছে আর দুইটি ডিস্ককে লাঠি A থেকে সরিয়ে, লাঠি B তে নেওয়ার মধ্যে বিশেষ কিছু নেই। তুমি ডিস্কগুলোকে লাঠি B থেকে লাঠি C তে নিয়ে যেতে পার লাঠি A কে অতিরিক্ত একটি লাঠি হিসেবে ব্যবহার করার মাধ্যমে: ডিস্ক 1 কে লাঠি B থেকে নিয়ে লাঠি A তে নিয়ে যাওয়া যাক, তারপরে ডিস্ক 2 কে লাঠি B থেকে নিয়ে লাঠি C তে নিয়ে আসা যাক আর সর্বশেষে ডিস্ক 1 কে লাঠি A থেকে সরিয়ে লাঠি C তে নিয়ে আসা যাক। ডিস্ক 1 এবং 2 এই ডিস্ক দুইটি, যে যেকোন লাঠি থেকে যে কোন লাঠিতে তিনটি ধাপে নিয়ে যাওয়া সম্ভব সে সম্পর্কে কি তুমি একমত? ("হ্যাঁ" বল।)

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।