Tower of Hanoi

Hard Recursion

Solve the Tower of Hanoi puzzle for n disks and print each move. Classic recursion problem.

Sample input

3 disks (A, B, C)

Sample output

Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C

Solution

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

hanoi(3, "A", "C", "B")

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

hanoi(3, "A", "C", "B");

public class Main {
    static void hanoi(int n, char source, char target, char auxiliary) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + target);
            return;
        }
        hanoi(n - 1, source, auxiliary, target);
        System.out.println("Move disk " + n + " from " + source + " to " + target);
        hanoi(n - 1, auxiliary, target, source);
    }

    public static void main(String[] args) {
        hanoi(3, 'A', 'C', 'B');
    }
}

fun hanoi(n: Int, source: Char, target: Char, auxiliary: Char) {
    if (n == 1) {
        println("Move disk 1 from $source to $target")
        return
    }
    hanoi(n - 1, source, auxiliary, target)
    println("Move disk $n from $source to $target")
    hanoi(n - 1, auxiliary, target, source)
}

fun main() {
    hanoi(3, 'A', 'C', 'B')
}

func hanoi(_ n: Int, _ source: String, _ target: String, _ auxiliary: String) {
    if n == 1 {
        print("Move disk 1 from \(source) to \(target)")
        return
    }
    hanoi(n - 1, source, auxiliary, target)
    print("Move disk \(n) from \(source) to \(target)")
    hanoi(n - 1, auxiliary, target, source)
}

hanoi(3, "A", "C", "B")

void hanoi(int n, String source, String target, String auxiliary) {
  if (n == 1) {
    print('Move disk 1 from $source to $target');
    return;
  }
  hanoi(n - 1, source, auxiliary, target);
  print('Move disk $n from $source to $target');
  hanoi(n - 1, auxiliary, target, source);
}

void main() {
  hanoi(3, 'A', 'C', 'B');
}

#include <iostream>
using namespace std;

void hanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << target << endl;
        return;
    }
    hanoi(n - 1, source, auxiliary, target);
    cout << "Move disk " << n << " from " << source << " to " << target << endl;
    hanoi(n - 1, auxiliary, target, source);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

#include <stdio.h>

void hanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, target);
        return;
    }
    hanoi(n - 1, source, auxiliary, target);
    printf("Move disk %d from %c to %c\n", n, source, target);
    hanoi(n - 1, auxiliary, target, source);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}