- What is the Tower of Hanoi?<\/a><\/li>
- Problem Statement: Program for Tower of Hanoi Algorithm<\/a><\/li>
- Recursive Approach
<\/strong><\/a><\/li>- C++ Code for Recursive Approach<\/a><\/li>
- Java Code for Recursive Approach <\/a><\/li>
- Python Code for Recursive Approach <\/a><\/li><\/ul>
- Frequently Asked Questions<\/a><\/li>
- Q.1: What are the minimum moves to solve the Tower of Hanoi problem?<\/a><\/li>
- Q.2: What is the space complexity of the Tower of Hanoi?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
What is the Tower of Hanoi?<\/h2>\n\n\n\n
The Tower of Hanoi <\/strong>is a mathematical puzzle. It consists of three rods<\/strong> and N<\/strong> disks. The task is to move all disks<\/strong> to another rod <\/strong>following certain rules<\/strong>:<\/p>\n\n\n\n
- Only one disk can be moved at a time.<\/li>
- Only the uppermost disk can be moved from one stack to the top of another stack or to an empty rod.<\/li>
- Larger disks cannot be placed on top of smaller disks.<\/li><\/ol>\n\n\n\n
Problem Statement: Program for Tower of Hanoi Algorithm<\/h2>\n\n\n\n
A diagrammatic illustration of the Tower of Hanoi:<\/strong><\/p>\n\n\n\n
<\/figure>\n\n\n\n
Image Source – Google images<\/strong><\/p>\n\n\n\n
The result is :<\/strong><\/p>\n\n\n\n
Image Source – Google Images.<\/strong><\/p>\n\n\n\n
Recursive Approach
<\/strong><\/span><\/h2>\n\n\n\nThe idea is to use a recursive approach to solve this problem.
Let us try to solve the problem for N = 2<\/strong>.<\/p>\n\n\n\nSo, one disk is moved from rod 1<\/strong> to rod 3<\/strong>. Then the second disk is moved from rod 1 <\/strong>to rod 2<\/strong> and finally, the first disk is moved again back to rod 2<\/strong>.<\/p>\n\n\n\n
Similarly, the problem can be solved recursively for N = 3<\/strong>. <\/strong>Observe the below example.<\/p>\n\n\n\n
The minimum number of moves to solve the Tower of Hanoi problem is 2^N – 1<\/strong>, where N is the number of disks.<\/p>\n\n\n\n
Tower Of Hanoi Example<\/figcaption><\/figure>\n\n\n\n Dry Run of the above illustration –<\/strong><\/p>\n\n\n\n
- Move disc 1 from tower A to tower B.<\/li>
- Move disc 2 from tower A to tower C. <\/li>
- Move disc 1 from tower B to tower C.<\/li>
- Move Disc 3 from tower A to tower B.<\/li>
- Move Disc 1 from tower C to tower A.<\/li>
- Move Disc 2 from tower C to tower B.<\/li>
- Move Disc 1 from tower A to tower B.<\/li><\/ul>\n\n\n\n
Algorithm<\/strong><\/p>\n\n\n\n
- Let us consider a recursive function that takes the following argument N,<\/strong> the number of disks<\/strong>, to_Rod<\/strong>, which indicates the rod which is moved to, from_rod<\/strong>, denoting the rod from which rod is removed, and aux_rod<\/strong>, denoting the rod which is used for transferring rods from from_rod<\/strong> to to_rod<\/strong>.<\/li>
- The base case is for N = 1. Move it from source to destination, i.e. from_rod <\/strong>to to_rod.<\/strong><\/li>
- Solve the problem recursively by moving disk 1, 2, 3,…, N – 1 i.e. from_rod <\/strong>to aux_rod <\/strong> by recursively calling the function on (N – 1<\/strong>, from_rod, aux_rod, to_rod)<\/strong>.<\/li>
- Now, since the top N – 1<\/strong> disks have been removed from from_rod<\/strong>, move the last disk from from_rod <\/strong>to to_rod<\/strong>.<\/li>
- Similarly, again remove the top N – 1<\/strong> disk from aux_rod<\/strong> to to_rod<\/strong> and recursively call the function on (N – 1, aux_rod, to_rod, from_rod)<\/strong><\/li>
- Repeat the above steps until it reaches the base case.<\/li><\/ul>\n\n\n\n
C++ Code for Recursive Approach<\/h3>\n\n\n\n
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)\n{\n if (n == 1)\n {\n cout << \"Move disk 1 from rod \" << from_rod <<\n \" to rod \" << to_rod<<endl;\n return;\n }\n towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);\n cout << \"Move disk \" << n << \" from rod \" << from_rod <<\n \" to rod \" << to_rod << endl;\n towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);\n}\nsolve(){\n TowerOfHanoi(n, 'A', 'C', 'B');\n}<\/pre>\n\n\n\nJava Code for Recursive Approach <\/span><\/h3>\n\n\n\n
static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)\n{\n if (n == 1)\n {\n System.out.println(\"Move disk 1 from rod \"+\n from_rod+\" to rod \"+to_rod);\n return;\n }\n towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);\n System.out.println(\"Move disk \"+ n + \" from rod \" +\n from_rod +\" to rod \" + to_rod );\n towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);\n}\n \nsolve(){\n TowerOfHanoi(n, 'A', 'C', 'B')\n \n}<\/pre>\n\n\n\nPython Code for Recursive Approach <\/span><\/h3>\n\n\n\n
def TowerOfHanoi(n , from_rod, to_rod, aux_rod):\n if n == 1:\n print(\"Move disk 1 from rod\",from_rod,\"to rod\",to_rod)\n return\n TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)\n print(\"Move disk\",n,\"from rod\",from_rod,\"to rod\",to_rod)\n TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)\n \ndef solve():\n TowerOfHanoi(n, 'A', 'C', 'B');<\/pre>\n\n\n\n
Time Complexity:<\/strong> O(2^N) where N is the number of disks.
Space Complexity:<\/strong> O(N), as the disks, take up the recursive stack space.<\/p>\n\n\n\n
\n\n\n\nFrequently Asked Questions<\/h2>\n\n\n\n
Q.1: What are the minimum moves to solve the Tower of Hanoi problem?<\/span><\/h3>\n\n\n\n
Ans:<\/strong> The minimum moves required is 2^N – 1 to move all disks from Source rod A to destination rod B while following the rules.<\/p>\n\n\n\n
Q.2: What is the space complexity of the Tower of Hanoi?<\/span><\/h3>\n\n\n\n
Ans: The space complexity is O(N) since, for each recursion, the disks take up N – 1 recursive stack space.<\/p>\n","protected":false},"excerpt":{"rendered":"What is the Tower of Hanoi? The Tower of Hanoi is a mathematical puzzle. It consists of three…\n","protected":false},"author":5,"featured_media":3143,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[480],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2913"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2913"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2913\/revisions"}],"predecessor-version":[{"id":20073,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2913\/revisions\/20073"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3143"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2913"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2913"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2913"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- The base case is for N = 1. Move it from source to destination, i.e. from_rod <\/strong>to to_rod.<\/strong><\/li>
- Let us consider a recursive function that takes the following argument N,<\/strong> the number of disks<\/strong>, to_Rod<\/strong>, which indicates the rod which is moved to, from_rod<\/strong>, denoting the rod from which rod is removed, and aux_rod<\/strong>, denoting the rod which is used for transferring rods from from_rod<\/strong> to to_rod<\/strong>.<\/li>
- Q.2: What is the space complexity of the Tower of Hanoi?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code for Recursive Approach <\/a><\/li>
- Problem Statement: Program for Tower of Hanoi Algorithm<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-5.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-6.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1-1024x344.png\")
<\/figure>\n\n\n\n![\"Tower](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/image-4.gif\")
<\/figure>\n\n\n\n![\"Tower](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/image-3-1.gif\")