টাওয়ার অব হানয়

টাওয়ার অব হানয় (এছাড়াও বলা হয় টাওয়ার অফ ব্রাহ্ম বা লুকাস টাওয়ার ) হল এক ধরনের বুদ্ধির খেলা । এ খেলায় তিনটি দন্ড খাড়াভাবে পাশাপাশি রাখা থাকে । এবং ছোট বড় কিছু ডিস্ক বা চাকতি দন্ড এর ভিতর প্রবেশ করান থাকে । এ খেলায় প্রথম দন্ড থেকে তৃতীয় দন্ডে সবগুলো চাকতি আনতে হয় । তবে কিছু নিয়ম পালন করতে হয় । নিয়মগুলো হলো:

একটি চার চাকতি বিশিষ্ট টাওয়ার অব হানয় গেমের অ্যানিমেশন

  ১. একসাথে একাধিক চাকতি সরানো যাবে না।
  ২. কখনই ছোট চাকতির উপর বড় চাকতি রাখা যাবে না।
  ৩. সবসময় উপরের চাকতি ওঠানো যাবে।

হ্যানয় ধাঁধার টাওয়ার সমাধানের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যা চাল হলো $2^{n}-1$ , যেখানে n হল ডিস্কের সংখ্যা।

সমাধান

টাওয়ার অব হানয় সমাধান করা আগে খুব কঠিন ছিল । এখন এটি সমাধান করার জন্য নানা ধরনের এলগরিদম বের হয়েছে । নিচে এর এলগরিদম গুলো নিয়ে আলোচনা করা হলোঃ মনে কর ,১ নং দন্ড টি হলো ১ , ২ নং ২ এবং ৩ নং ৩ জোড় সংখ্যার ক্ষেত্রেঃ

    ১. ১ ও ২ এর মধ্যে একটি সঠিক মুভ কর 
    ২. ১ ও ৩ এর মধ্যে একটি সঠিক মুভ কর
    ৩. ২ ও ৩ এর মধ্যে একটি সঠিক মুভ কর  
    ৪. সম্পূর্ণ না হওয়া পর্যন্ত চালিয়ে যাও 

বিজোড় সংখ্যার ক্ষেত্রেঃ

    ১. ১ ও ৩ এর মধ্যে একটি সঠিক মুভ কর 
    ২. ১ ও ২ এর মধ্যে একটি সঠিক মুভ কর
    ৩. ২ ও ৩ এর মধ্যে একটি সঠিক মুভ কর  
    ৪. সম্পূর্ণ না হওয়া পর্যন্ত চালিয়ে যাও

সুডোকোডে আলগরিদম

 A = [5,4,3,2,1]
 B = []
 C = []
 
 def move(n, source, target, auxiliary):
 <nowiki> </nowiki>   if n > 0:
 <nowiki> </nowiki>       # move n-1 disks from source to auxiliary, so they are out of the way  
 <nowiki> </nowiki>       move(n-1, source, auxiliary, target)
 
 <nowiki> </nowiki>       # move the nth disk from source to target
 <nowiki> </nowiki>       target.append(source.pop())
 
 <nowiki> </nowiki>       # Display our progress
 <nowiki> </nowiki>       print(A, B, C, '##############', sep='\n')  
 <nowiki> </nowiki>       
 <nowiki> </nowiki>       # move the n-1 disks that we left on auxiliary onto target
 <nowiki> </nowiki>       move(n-1, auxiliary, target, source)
 
 <nowiki>#</nowiki> initiate call from source A to target C with auxiliary B 
 move(5, A, C, B)

সি++ কোড

#include <iostream>
using namespace std;

void tower_hannoi (int disk, char tower1, char tower2, char tower3)
{
    if (disk == 1)
    {
        cout << "Move disk " << disk << " from " << tower1 << " to " << tower3 << endl;

    }
    else
    {
        tower_hannoi (disk-1, tower1, tower3, tower2);
        cout << "Move disk " << disk << " from " << tower1 << " to " << tower3 << endl;
        tower_hannoi (disk-1, tower2, tower1, tower3);
    }
}

int main()
{
    int disk;
    char tower1 = 'A';
    char tower2 = 'B';
    char tower3 = 'C';
    cin >> disk;
    tower_hannoi (disk, tower1, tower2, tower3);
    return 0;
}

পাইথন কোড

def hanoi(n, a='A', b='B', c='C'): 
    if n == 1:
        print('move', a, '-->', c)
        return
    hanoi(n-1, a, c, b)
    print('move', a, '-->', c)
    hanoi(n-1, b, a, c)

print(hanoi(5))

গ্যালারি

• 
• 
• 

বহিঃসংযোগ

http://orbisbux.com/?ref=softimine