Tower of Hanoi

Definition

Definition

The Tower of Hanoi is a classic recursive algorithm used to solve the problem of moving a stack of discs from one rod to another, following certain rules

Explanation

Recursively moving disks from one rod to another, adhering to three rules: (1) Only one disk can be moved at a time. (2) A disk can only be moved onto a rod if it's either empty or has a larger disk on top of it. (3) Each move must involve moving the top disk of one rod onto another rod. The algorithm follows a pattern where it moves n-1 disks from the source rod to the auxiliary rod, then moves the nth disk from the source rod to the destination rod, and finally moves the n-1 disks from the auxiliary rod to the destination rod, all recursively

Guidance

• Start with all disks stacked on one rod, called the source rod
• Identify the target rod where you want to move all the disks
• Choose an auxiliary rod to assist in the movement
• Move n-1 disks from the source rod to the auxiliary rod using the target rod as a helper
• Move the nth disk from the source rod to the target rod
• Move the n-1 disks from the auxiliary rod to the target rod using the source rod as a helper
• Repeat the process recursively for the remaining disks until all disks are moved to the target rod

Tips

• keep track of the number of disks being moved at each step to ensure proper recursive function calls
• ensure that the disks are moved in the correct order to maintain the rules of the Tower of Hanoi puzzle
• use the recursive nature of the algorithm efficiently to minimize unnecessary movements

Practice

Practice

tower_of_hanoi(n, source, target, auxiliary):
  if n == 1:
    move_disk(source, target)
  else:
    tower_of_hanoi(n-1, source, auxiliary, target)
    move_disk(source, target)
    tower_of_hanoi(n-1, auxiliary, target, source)

move_disk(source, target):
  print "Move disk from", source, "to", target

Solution

package main

func towerOfHanoi(n int, source, auxiliary, destination string) {
    if n == 1 {
        fmt.Println("Move disk 1 from", source, "to", destination)
        return
    }
    towerOfHanoi(n-1, source, destination, auxiliary)
    fmt.Println("Move disk", n, "from", source, "to", destination)
    towerOfHanoi(n-1, auxiliary, source, destination)
}

public class TowerOfHanoi {

  public static void towerOfHanoi(int n, String source, String auxiliary, String destination) {
    if (n == 1) {
      System.out.println("Move disk 1 from " + source + " to " + destination);
      return;
    }
    towerOfHanoi(n - 1, source, destination, auxiliary);
    System.out.println("Move disk " + n + " from " + source + " to " + destination);
    towerOfHanoi(n - 1, auxiliary, source, destination);
  }
}

function towerOfHanoi(n, source, auxiliary, destination) {
  if (n === 1) {
    console.log(`Move disk 1 from ${source} to ${destination}`);
    return;
  }
  towerOfHanoi(n - 1, source, destination, auxiliary);
  console.log(`Move disk ${n} from ${source} to ${destination}`);
  towerOfHanoi(n - 1, auxiliary, source, destination);
}

fun towerOfHanoi(n: Int, source: String, auxiliary: String, destination: String) {
    if (n == 1) {
        println("Move disk 1 from $source to $destination")
        return
    }
    towerOfHanoi(n - 1, source, destination, auxiliary)
    println("Move disk $n from $source to $destination")
    towerOfHanoi(n - 1, auxiliary, source, destination)
}

def tower_of_hanoi(n, source, auxiliary, destination):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    tower_of_hanoi(n - 1, source, destination, auxiliary)
    print(f"Move disk {n} from {source} to {destination}")
    tower_of_hanoi(n - 1, auxiliary, source, destination)

fn tower_of_hanoi(n: u32, source: char, auxiliary: char, destination: char) {
    if n == 1 {
        println!("Move disk 1 from {} to {}", source, destination);
        return;
    }
    tower_of_hanoi(n - 1, source, destination, auxiliary);
    println!("Move disk {} from {} to {}", n, source, destination);
    tower_of_hanoi(n - 1, auxiliary, source, destination);
}

function towerOfHanoi(
  n: number,
  source: string,
  auxiliary: string,
  destination: string,
) {
  if (n === 1) {
    console.log(`Move disk 1 from ${source} to ${destination}`);
    return;
  }
  towerOfHanoi(n - 1, source, destination, auxiliary);
  console.log(`Move disk ${n} from ${source} to ${destination}`);
  towerOfHanoi(n - 1, auxiliary, source, destination);
}