যখন তিনটি ডিস্কের জন্য টাওয়ার্স অফ হ্যানয় সমাধান করা লাগবে, তখন একদম নিচের ডিস্কটি অর্থাৎ ডিস্ক 3 টি সামনে নিয়ে আসা লাগবে, যেন ডিস্ক 3 টি লাঠি A থেকে সরিয়ে লাঠি B তে নিয়ে আসা যায়। ডিস্ক ৩ টি সামনে নিয়ে আসার জন্য আমাদের প্রথমেই 1 এবং 2 ডিস্ক দুইটিকে সরিয়ে অতিরিক্ত যে লাঠিটি রয়েছে অর্থাৎ লাঠি C তে সরিয়ে নিয়ে যেতে হবে:
টাওয়ার্স অফ হ্যানয় ডিস্ক 1, 3 সরিয়ে নেয়াযাক
কিন্তু এখানে—দেখে মনে হচ্ছে প্রথম নিয়মটি অর্থাৎ একসাথে দুইটি ডিস্ক সরানো যাবে না সংক্রান্ত নিয়মটি ভঙ্গ হচ্ছে। কিন্তু ডিস্ক দুইটি একটি ধাপে সরানো হয়নি। এখানে আমরা সবাই একমত হয়েছি যে, ডিস্ক 1 এবং 2 কে যেকোন লাঠি হতে যেকোন লাঠিতে আমরা তিনটি ধাপ ব্যবহার করে সরাতে পারবো। তিনটি ধাপ অতিক্রম করার পরেই আমরা উপরের সমাধানটিতে আসতে পেরেছি। (ডিস্ক 1 কে লাঠি A হতে লাঠি B তে সরানো হল; ডিস্ক 2 কে লাঠি A হতে লাঠি C তে সরানো হল; ডিস্ক 1 কে লাঠি B হতে লাঠি C তে সরানো হল।)
এখানে আরও বলা যায়, ডিস্ক 1 এবং 2 কে লাঠি A থেকে লাঠি C তে সরানোর মাধ্যমে ছোট একটি সমস্যার সমাধানও আমরা করে ফেলেছি: ডিস্ক 1 কে লাঠি A থেকে লাঠি C তে সরিয়ে নেওয়া হল n, minus, 1 ধাপের মাধ্যমে (এখানে মনে রাখা দরকার যে n, equals, 3)। আমরা যদি এই ছোট সমস্যাটি সমাধান করতে পারি তাহলে, আমরা ডিস্ক 3 টি লাঠি A থেকে লাঠি B তে সরিয়ে নিতে পারবো:
টাওয়ার্স অফ হ্যানয় ডিস্ক 2, 3 সরিয়ে নেয়াযাক
এখন সবশেষে আমাদের ডিস্ক 1 কে n, minus, 1 ধাপে লাঠি C থেকে লাঠি B তে নিয়ে আসার ছোট সমস্যাটি সমাধান করতে হবে। আবার আমরা এখানে একমত হচ্ছি যে আমরা এই কাজটি তিনটি ধাপে এই কাজটি সম্পন্ন করতে পারবো। (ডিস্ক 1 কে লাঠি C থেকে সরিয়ে লাঠি A তে নিয়ে আসতে হবে; ডিস্ক 2 কে লাঠি C থেকে সরিয়ে লাঠি B তে নিয়ে আসতে হবে; এরপরে ডিস্ক 1 কে লাঠি A থেকে লাঠি B তে সরিয়ে নিয়ে আসতে হবে।) আর তাহলেই আমাদের কাজ শেষ হয়ে যাবে:
টাওয়ার্স অফ হ্যানয় ডিস্ক 3, 3 সরিয়ে নেয়াযাক
And—you knew this question is coming—is there anything special about which pegs you moved disks 1 through 3 from and to? You could have moved them from any peg to any peg. For example, from peg B to peg C:
  • Recursively solve the subproblem of moving disks 1 and 2 from peg B to the spare peg, peg A. (Move disk 1 from peg B to peg C; move disk 2 from peg B to peg A; move disk 1 from peg C to peg A.)
  • Now that disk 3 is exposed on peg B, move to it peg C.
  • Recursively solve the subproblem of moving disks 1 and 2 from peg A to peg C. (Move disk 1 from peg A to peg B; move disk 2 from peg A to peg C; move disk 1 from peg B to peg C.)
আমরা 1 থেকে 3 পর্যন্ত থাকা ডিস্কগুলো যেকোন লাঠি থেকে যেকোন লাঠিতে সরিয়ে নিতে পারি, ডিস্কগুলো সাতবার সরানোর মাধ্যমে। এখানে লক্ষ্য করলে তুমি দেখবে যে প্রতিটি ডিস্ক তিনবার করে পৌনঃপুনিকতা ব্যবহার করার মাধ্যমে সর্বমোট দুইবার ডিস্কগুলো সরানোর মাধ্যমে ডিস্ক 1 এবং ডিস্ক 2 সরানোর ছোট সমস্যাটি সমাধান করতে পারছ, আর এর সাথে আরও একটি ধাপ যুক্ত হবে ডিস্ক 3 সরানোর জন্য।
How about when n, equals, 4? Because you can recursively solve the subproblem of moving disks 1 through 3 from any peg to any peg, you can solve the problem for n, equals, 4:
  • Recursively solve the subproblem of moving disks 1 through 3 from peg A to peg C, moving disks seven times.
  • Move disk 4 from peg A to peg B.
  • Recursively solve the subproblem of moving disks 1 through 3 from peg C to peg B, moving disks seven times.
এই সমাধানে ডিস্কগুলো আমরা 15 বার (7 + 1 + 7) সরিয়েছি এবং আমরা 1 থেকে 4 পর্যন্ত থাকা ডিস্কগুলো যেকোন লাঠি থেকে যেকোন লাঠিতে সরিয়ে নিতে পারি।
At this point, you might have picked up two patterns. First, you can solve the Towers of Hanoi problem recursively. If n, equals, 1, just move disk 1. Otherwise, when n, is greater than or equal to, 2, solve the problem in three steps:
  • Recursively solve the subproblem of moving disks 1 through n, minus, 1 from whichever peg they start on to the spare peg.
  • Move disk n from the peg it starts on to the peg it's supposed to end up on.
  • Recursively solve the subproblem of moving disks 1 through n, minus, 1 from the spare peg to the peg they're supposed to end up on.
দ্বিতীয়ত, n সংখ্যক ডিস্কের একটি সমস্যার সমাধান করার জন্য, 2, start superscript, n, end superscript, minus, 1 সংখ্যকবার ডিস্কগুলো সরানোর প্রয়োজন হবে। আমরা এখানে দেখছি যে, n, equals, 1 সত্য হলে (2, start superscript, 1, end superscript, minus, 1, equals, 1 হবে এবং আমাদের শুধুমাত্র একবার ডিস্ক সরানোর প্রয়োজন হবে), n, equals, 2 হলে (2, start superscript, 2, end superscript, minus, 1, equals, 3 হবে এবং আমাদের তিনবার ডিস্কগুলো সরানোর প্রয়োজন হবে), n, equals, 3 হলে (2, start superscript, 3, end superscript, minus, 1, equals, 7 হবে এবং আমাদের সাতবার ডিস্কগুলো সরানোর প্রয়োজন হবে), এবং n, equals, 4 হলে (2, start superscript, 4, end superscript, minus, 1, equals, 15 হবে এবং আমাদের 15 বার ডিস্কগুলো সরানোর প্রয়োজন হবে)। যদি তুমি n, minus, 1 সংখ্যক ডিস্কের সমস্যাটি 2, start superscript, n, minus, 1, end superscript, minus, 1 সংখ্যকবার ডিস্ক সরানোর মাধ্যমে সমাধান করতে পার, তাহলে তুমি n সংখ্যক ডিস্কের সমস্যাটির সমাধান 2, start superscript, n, end superscript, minus, 1 সংখ্যকবার ডিস্ক সরানোর মাধ্যমে সমাধান করতে পারবে: প্রথম ছোট সমস্যাটি সমাধান করার জন্য তোমার 2, start superscript, n, minus, 1, end superscript, minus, 1 সংখ্যকবার পৌনঃপুনিকভাবে ডিস্ক 1 কে n, minus, 1 সংখ্যকবার সরাতে হবে, ডিস্ক n কে সরানোর জন্য একবার এবং তারপরে আরও 2, start superscript, n, minus, 1, end superscript, minus, 1 একবার এরপরে দ্বিতীয় ছোট সমস্যাটি সমাধান করার জন্য ডিস্ক 1 কে n, minus, 1 সংখ্যকবার সরাতে হবে। ডিস্কগুলো কতবার সরিয়েছ যদি তার সংখ্যাটি তুমি একসাথে কর তাহলে তুমি পাবে 2, start superscript, n, end superscript, minus, 1
সন্ন্যাসীর কাছে ফিরে যাওয়া যাক। তারা ব্যবহার করছে n, equals, 64 সংখ্যক ডিস্ক এবং তাহলে একটি ডিস্ক তাদের 2, start superscript, 64, end superscript, minus, 1 সংখ্যকবার সরানোর প্রয়োজন হবে। এই সন্ন্যাসীরা খুবই চটপটে এবং শক্তিশালী। রাত এবং দিনে প্রতি সেকেন্ডে তারা একটি করে ডিস্ক সরাতে পারে। 2, start superscript, 64, end superscript, minus, 1 কত সেকেন্ড দীর্ঘ? মোটামুটি অনুমানের উপরে ভিত্তি করে প্রতি বছর 365.25 দিনের হিসাব ব্যবহার করলে (প্রতি 400 বছরে থাকা অধিবর্ষের হিসাব আমরা এখানে আনছি না), আমরা পাচ্ছি 584,542,046,090.6263 বছর। তাহলে এটা হবে 584+ বিলিয়ন বছর। সূর্যের সুপারনোভাতে পরিনত হবার জন্য আর পাঁচ থেকে সাত বিলিয়ন বছর সময় লাগতে পারে। তাহলে, হ্যাঁ, সন্ন্যাসীরা যতই নাছোড়বান্দা হোক না কেন এক সময় এই বিশ্বের সমাপ্তি ঘটবে, এবং এটা ঘটবে সম্পূর্ণ 64 টি ডিস্ক লাঠি B তে সরিয়ে নিয়ে যাবার আগেই।
বিশ্বের সমাপ্তির সময় অনুমান করা ছাড়া এই অ্যাপ্লিকেশনটি আমরা আর কি কি কাজে ব্যবহার করতে পারি? উইকিপিডিয়ার তালিকা কয়েকটি মজাদার অ্যাপ্লিকেশন

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