বিষয়বস্তুতে চলুন

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

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে
একটি চার চাকতি বিশিষ্ট টাওয়ার অব হানয় গেমের অ্যানিমেশন

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

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

হ্যানয় ধাঁধার টাওয়ার সমাধানের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যা চাল হলো , যেখানে 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))

গ্যালারি

[সম্পাদনা]

তথ্যসূত্র

[সম্পাদনা]
  1. Hofstadter, Douglas R. (১৯৮৫)। Metamagical themas : questing for the essence of mind and pattern। Internet Archive। New York : Basic Books। আইএসবিএন 978-0-465-04540-2 

বহিঃসংযোগ

[সম্পাদনা]

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