{"id":18707,"date":"2021-06-26T20:00:37","date_gmt":"2021-06-26T20:00:37","guid":{"rendered":"https:\/\/www.askpython.com\/?p=18707"},"modified":"2021-06-26T20:06:28","modified_gmt":"2021-06-26T20:06:28","slug":"tower-of-hanoi-in-python","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/examples\/tower-of-hanoi-in-python","title":{"rendered":"Tower of Hanoi in Python: Complete Step-by-Step"},"content":{"rendered":"\n

Tower of Hanoi is a mathematical problem (puzzle) that consists of 3 poles and ‘n’ number of discs, each disc having different diameters.<\/p>\n\n\n\n

The Objective of the Tower of Hanoi Problem<\/h2>\n\n\n\n

The objective or goal of this problem is to transfer all the ‘n’ discs from source pole to the destination pole in such a way that we get the same arrangement of discs as before. But this goal must be achieved by sticking to the rules. <\/p>\n\n\n\n

\n\n\n\n

Rules and Constraints<\/strong><\/h3>\n\n\n\n

The constraints that must be satisfied while solving the problem are –<\/p>\n\n\n\n

  1. Only one disc can be moved at a time.<\/li>
  2. Only the top-most disc can be removed<\/li>
  3. The larger disc cannot be placed on top of the smaller disc.<\/li><\/ol>\n\n\n\n
    \n\n\n\n

    Visual Representation<\/strong> of the Tower of Hanoi problem<\/h3>\n\n\n\n

    The following picture shows the step-wise solution for a tower of Hanoi with 3 poles (source, intermediate, destination) and 3 discs. The goal is to move all the 3 discs from pole A to pole C.<\/p>\n\n\n\n

    \"STEP<\/figure><\/div>\n\n\n\n
    \"STEP<\/figure><\/div>\n\n\n\n
    \"STEP<\/figure><\/div>\n\n\n\n
    \"STEP<\/figure><\/div>\n\n\n\n

    As we can see from the above solution, the number of moves needed for 3 discs = 8. So, a generalized formula for a total number of moves we need is:<\/p>\n\n\n\n

    Total number of moves = n2<\/sup>\u00a0– 1<\/p>\n\n\n\n

    Where ‘n’ is the total no. of discs.<\/p>\n\n\n\n

    \n\n\n\n

    Solving the Tower of Hanoi Problem in Python<\/h2>\n\n\n
    \ndef TowerOfHanoi(n , s_pole, d_pole, i_pole):           \n    if n == 1:\n        print("Move disc 1 from pole",s_pole,"to pole",d_pole)\n        return\n    TowerOfHanoi(n-1, s_pole, i_pole, d_pole)\n    print("Move disc",n,"from pole",s_pole,"to pole",d_pole)\n    TowerOfHanoi(n-1, i_pole, d_pole, s_pole)\n\nn = 3\nTowerOfHanoi(n, 'A', 'C', 'B')\n# A, C, B are the name of poles\n \n<\/pre><\/div>\n\n\n
    In the above code, we call our function TowerOfHanoi recursively for 3 discs. <\/p>\n\n\n\n
    Here:<\/p>\n\n\n\n
    • s_pole: source pole<\/li>
    • i_pole: intermediate pole<\/li>
    • d_pole: destination pole<\/li><\/ul>\n\n\n\n
      The output of the above code is:<\/strong><\/p>\n\n\n\n
      \"Output<\/figure><\/div>\n\n\n\n
      \n\n\n\n
      Conclusion<\/h2>\n\n\n\n
      So , this is how we solve the problem of Tower of Hanoi.<\/p>\n\n\n\n
      This code can be generalized for any number of discs. So if you want the solution for 4 discs, just change the value of n from 3 to 4 as n = 4, and the output will be displayed for 4 discs and so on.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Tower of Hanoi is a mathematical problem (puzzle) that consists of 3 poles and ‘n’ number of discs, each disc having different diameters. The Objective of the Tower of Hanoi Problem The objective or goal of this problem is to transfer all the ‘n’ discs from source pole to the destination pole in such a […]<\/p>\n","protected":false},"author":34,"featured_media":18726,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-18707","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/18707","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/34"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=18707"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/18707\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/18726"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=18707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=18707"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=18707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}