{"id":83576,"date":"2021-08-21T09:00:28","date_gmt":"2021-08-21T03:30:28","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=83576"},"modified":"2021-08-21T09:00:28","modified_gmt":"2021-08-21T03:30:28","slug":"tower-of-hanoi","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/","title":{"rendered":"Tower of Hanoi in Data Structure"},"content":{"rendered":"

The Tower of Hanoi is a mathematical puzzle containing 3 pillars\/towers<\/strong> with n<\/strong> disks<\/strong> each of a different size\/diameter. These disks can slide onto any pillar. The following diagram shows the initial state of the problem.<\/p>\n

\"Tower<\/a><\/p>\n

Here, we have stacked the disks over each other in the ascending order of their sizes. Note that we can have any number of disks but only 3 towers.<\/p>\n

Rules to be followed:<\/h3>\n

Our objective in this puzzle is to move all these disks to another pillar without changing the order in which the disks are placed in the initial state. The rules for this puzzle are:<\/p>\n

1. We can move only one disk at a time.<\/p>\n

2. We can remove only the top disk.<\/p>\n

3. We can only place a disk above a disk of a larger size.<\/p>\n

Approach:<\/h3>\n

Tower of Hanoi is a recursion based puzzle and thus, we will follow a recursive approach to solve it. Consider a puzzle with 3 pillars and 3 disks as shown:<\/p>\n

\"Tower<\/a><\/p>\n

Step 1: toh(2, source, aux, dest)<\/p>\n

\"Working<\/a><\/p>\n

Step 2: Move the disk from source to destination<\/p>\n

\"Tower<\/a><\/p>\n

Step 3: toh(2, aux, dest, source)<\/p>\n

\"Working<\/a><\/p>\n

Thus, in general, for n disks, the steps are:<\/p>\n

1:<\/strong> Move n-1 disks from source to auxiliary i.e. toh(n-1, source, aux, dest)
\n2:<\/strong> Move the nth disk from source to destination
\n3:<\/strong> Move n-1 disks from aux to dest i.e. toh(n-1, aux, dest, source)<\/p>\n

Algorithm:<\/h3>\n

We can write the solution for this puzzle in both iterative and recursive approaches. Let us here see the steps to write a recursive algorithm for the Tower of Hanoi.<\/p>\n

procedure TOH(disk, Source, Dest, Aux):\n   if disk == 1:\n        move disk from Source to Dest             \n   else:\n        TOH(disk - 1, Source, Aux, Dest)     \n        move disk from Source to Dest          \n        TOH(disk - 1, Aux, Dest, Source)     \n   END if\nEND TOH\n<\/pre>\n
Implementation of Tower of Hanoi in C:<\/h3>\n
#include<stdio.h>\nvoid toh(int, char, char, char);\n\nint main(){\n  char source = 'A', destination='B', Auxiliary='C';\n  int n;\n  printf(\"Enter value of n\\t\");\n  scanf(\"%d\", &n);\n  toh(n, source, destination, Auxiliary);\n  return 0;\n}\n\nvoid toh(int n, char source, char dest, char aux){\n  if(n==1){\n    printf(\"%c -> %c \\n\", source, dest);\n    return;\n  }\n  toh(n-1, source, aux, dest);\n  printf(\"%c -> %c \\n\", source, dest);\n  toh(n-1, aux, dest, source);\n}\n<\/pre>\n
Tower of Hanoi Implementation in C++:<\/h3>\n
#include<bits\/stdc++.h>\nvoid toh(int, char, char, char);\n\nint main(){\n  char source = 'A', destination='B', Auxiliary='C';\n  int n;\n  cout<< \"Enter value of n\\t\";\n  cin>> n;\n  toh(n, source, destination, Auxiliary);\n  return 0;\n}\n\nvoid toh(int n, char source, char dest, char aux){\n  if(n==1){\n    cout<< \"%c -> %c \\n\"<< source<< dest;\n    return;\n  }\n  toh(n-1, source, aux, dest);\n  cout<< \"%c -> %c \\n\"<< source<< dest;\n  toh(n-1, aux, dest, source);\n}\n<\/pre>\n
Implementation of Tower of Hanoi in Java:<\/h3>\n
import java.util.*;\nimport java.io.*;\nimport java.math.*;\nclass TechVidvan\n{\nstatic void toh(int n, char source, char dest, char aux)\n{\n  if (n == 1)\n  {\n    System.out.println(\"Move disk 1 from rod \"+ source +\" to rod \"+ dest);\n    return;\n  }\n  toh(n - 1, source, aux, dest);\n  System.out.println(\"Move disk \"+ n + \" from rod \" + source +\" to rod \" + dest );\n  toh(n - 1, aux, dest, source);\n}\n\npublic static void main(String args[])\n{\n  int n = 6; \n  toh(n, 'A', 'C', 'B'); \n}\n}\n<\/pre>\n
Tower of Hanoi Implementation in Python:<\/h3>\n
def toh(n , source, dest, aux):\n  if n == 1:\n    print(\"Move disk 1 from tower\",source,\"to tower\",dest)\n    return\n  toh(n-1, source, aux, dest)\n  print(\"Move disk\",n,\"from rod\",source,\"to rod\",dest)\n  toh(n-1, aux, dest, source)\n\nn = 6\ntoh(n, 'A', 'C', 'B')\n<\/pre>\n
Conclusion:<\/h3>\n
The puzzle Tower of Hanoi is like a mathematical disk game that was invented in 1883. We can play this puzzle with 3 towers\/pillars and any number of disks. The solution for this puzzle is recursive. In this article, we have seen the recursive solution for Tower of Hanoi along with the rules of the puzzle.<\/p>\n","protected":false},"excerpt":{"rendered":"
The Tower of Hanoi is a mathematical puzzle containing 3 pillars\/towers with n disks each of a different size\/diameter. These disks can slide onto any pillar. The following diagram shows the initial state of...<\/p>\n","protected":false},"author":1,"featured_media":84156,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[4078,4079],"class_list":["post-83576","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-tower-of-hanoi","tag-tower-of-hanoi-in-data-structure"],"yoast_head":"\nTower of Hanoi in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Tower of Hanoi is like a mathematical disk game that was invented in 1883. Learn about it and its implementation in C, C++, Java & python.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Tower of Hanoi in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Tower of Hanoi is like a mathematical disk game that was invented in 1883. Learn about it and its implementation in C, C++, Java & python.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-21T03:30:28+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Tower-of-Hanoi.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Tower of Hanoi in Data Structure - TechVidvan","description":"Tower of Hanoi is like a mathematical disk game that was invented in 1883. Learn about it and its implementation in C, C++, Java & python.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/","og_locale":"en_US","og_type":"article","og_title":"Tower of Hanoi in Data Structure - TechVidvan","og_description":"Tower of Hanoi is like a mathematical disk game that was invented in 1883. Learn about it and its implementation in C, C++, Java & python.","og_url":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-08-21T03:30:28+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Tower-of-Hanoi.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Tower of Hanoi in Data Structure","datePublished":"2021-08-21T03:30:28+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/"},"wordCount":343,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Tower-of-Hanoi.jpg","keywords":["Tower of Hanoi","Tower of Hanoi in data structure"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/","url":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/","name":"Tower of Hanoi in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Tower-of-Hanoi.jpg","datePublished":"2021-08-21T03:30:28+00:00","description":"Tower of Hanoi is like a mathematical disk game that was invented in 1883. Learn about it and its implementation in C, C++, Java & python.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Tower-of-Hanoi.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Tower-of-Hanoi.jpg","width":1200,"height":628,"caption":"Tower of Hanoi"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/tower-of-hanoi\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Tower of Hanoi in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83576","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=83576"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83576\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/84156"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=83576"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=83576"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=83576"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}