{"id":9278,"date":"2022-08-29T11:11:48","date_gmt":"2022-08-29T11:11:48","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9278"},"modified":"2023-11-24T07:14:16","modified_gmt":"2023-11-24T07:14:16","slug":"iterative-tower-of-hanoi","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/iterative-tower-of-hanoi\/","title":{"rendered":"Iterative Tower of Hanoi"},"content":{"rendered":"

\"\"<\/p>\n

The Tower of Hanoi puzzle has fascinated mathematicians and puzzle enthusiasts alike for centuries with its elegant simplicity and complex nature. Originally formulated by the French mathematician \u00c9douard Lucas in 1883, this classic problem involves moving a stack of disks from one peg to another, adhering to specific rules. While the traditional Tower of Hanoi puzzle employs a recursive algorithm, the concept of an iterative solution has emerged as an intriguing alternative.<\/p>\n

What is the Tower of Hanoi?<\/h2>\n

In the Tower of Hanoi problem you are given three rods (\u201cSource\u201d, \u201cDestination\u201d, \u201cAuxiliary\u201d) and n disks. Initially, all the disks are stacked on the source rod in decreasing order of disk\u2019s size making a conical shape. Your task is to move all the stacked disks to the destination rod by obeying the following rules:<\/p>\n

    \n
  1. You can move only one disk in one step.<\/li>\n
  2. The topmost disk can be removed from any rod and placed on the top of the other rod.<\/li>\n
  3. A disk can not be placed on another disk that is smaller in size than it.<\/li>\n<\/ol>\n

    Test cases:<\/strong>
    \nInput:<\/strong>
    \n2<\/p>\n

    Output:<\/strong>
    \nMove Disk 1 from \u201cS\u201d to \u201cA\u201d
    \nMove Disk 2 from \u201cS\u201d to \u201cD\u201d
    \nMove Disk 1 from \u201cA\u201d to \u201cD\u201d<\/p>\n

    Explanation:<\/h3>\n

    Iterative Approach<\/h4>\n

    Algorithm<\/h4>\n
      \n
    1. Find the total number of moves required to solve the problem.<\/li>\n
    2. If the number of disks is n, then the total moves required is 2n – 1.<\/li>\n
    3. If n % 2 == 0, i.e, n is even then exchange the position of destination rod and auxiliary rod.<\/li>\n
    4. Iterate i in 1 to moves
      \na. if i % 3 == 1:
      \na.1. Move the topmost disk of the source pole and place it on the top of the destination pole.
      \nb. If i%3 == 2:
      \nb.1. Move the topmost disk of the source pole and place it on the top of the auxiliary pole.
      \nc. If i%3 == 0:
      \nc.1. Move the topmost disk of the auxiliary pole and place it on the top of the destination pole.<\/li>\n<\/ol>\n

      Code Implementation:<\/h3>\n\t\t\t\t\t\t