8.6 Towers of Hanoi Problem Explained With Solutions In Ruby, Javascript and Python: Mastering Algorithms

Unlocking Recursive Puzzles: A Multilingual Approach to Algorithmic Proficiency

The Towers of Hanoi problem is pivotal in computer science and mathematics education as it exemplifies essential concepts like recursion and the divide-and-conquer algorithmic strategy. It provides a practical approach to understanding how complex problems can be decomposed into simpler, solvable subproblems, fostering analytical and logical thinking. The problem’s inherent use of stack data structure and its exponential runtime, O(2n), offer insights into algorithm efficiency and optimization. Studying this problem equips learners with foundational problem-solving skills and a deeper comprehension of algorithm design, crucial for advancements in software development and artificial intelligence.

The Towers of Hanoi is a classic problem that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move can only take the upper disk from one of the stacks and place it on top of another stack or on an empty rod.
3. No disk may be placed on top of a smaller disk.

Ruby Solution

Here’s a simple recursive solution in Ruby. The idea is to move n-1 disks from the source to the auxiliary rod, then move the largest disk from the source to the target rod, and finally, move the n-1 disks from the auxiliary rod to the target rod.

def hanoi(n, source, auxiliary, target)
  if n > 0
    # Move n - 1 disks from source to auxiliary, so they are out of the way
    hanoi(n - 1, source, target, auxiliary)
    
    # Move the nth disk from source to target
    puts "Move disk #{n} from #{source} to #{target}"
    
    # Move the n - 1 disks that we left on auxiliary to target
    hanoi(n - 1, auxiliary, source, target)
  end
end

# Example usage:
# Let's say we have 3 disks on rod "A" and we want to move them to rod "C"
# with the help of auxiliary rod "B"
hanoi(3, 'A', 'B', 'C')

For 3 disks, the output of the above Ruby code would be:

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

This output represents the sequence of moves needed to solve a 3-disk Towers of Hanoi problem, moving one disk at a time from the source rod to the target rod, using the auxiliary rod when necessary, and never placing a larger disk on top of a smaller one.

JavaScript Solution

Below is the equivalent JavaScript code for the Towers of Hanoi problem. The logic is the same as the Ruby example; it’s just the syntax that differs.

function hanoi(n, source, auxiliary, target) {
    if (n > 0) {
        // Move n - 1 disks from source to auxiliary, so they are out of the way
        hanoi(n - 1, source, target, auxiliary);
        
        // Move the nth disk from source to target
        console.log("Move disk " + n + " from " + source + " to " + target);
        
        // Move the n - 1 disks that we left on auxiliary to target
        hanoi(n - 1, auxiliary, source, target);
    }
}

// Example usage:
// Let's say we have 3 disks on rod "A" and we want to move them to rod "C"
// with the help of auxiliary rod "B"
hanoi(3, 'A', 'B', 'C');

For 3 disks, the output of the above JavaScript code would be:

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

You can run this JavaScript code in any JavaScript environment like a web browser’s developer console, or in a Node.js environment.

Python Example

Below is the equivalent Python code for the Towers of Hanoi problem. The logic remains the same as in the Ruby and JavaScript examples; only the syntax is different.

def hanoi(n, source, auxiliary, target):
    if n > 0:
        # Move n - 1 disks from source to auxiliary, so they are out of the way
        hanoi(n - 1, source, target, auxiliary)
        
        # Move the nth disk from source to target
        print(f"Move disk {n} from {source} to {target}")
        
        # Move the n - 1 disks that we left on auxiliary to target
        hanoi(n - 1, auxiliary, source, target)

# Example usage:
# Let's say we have 3 disks on rod "A" and we want to move them to rod "C"
# with the help of auxiliary rod "B"
hanoi(3, 'A', 'B', 'C')

For 3 disks, the output of the above Python code would be:

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

You can run this Python code in any Python environment like Python shell, or any IDE that supports Python.

Object Oriented Design for the Entire Game

Below are more detailed object-oriented designs for the Towers of Hanoi game in Ruby, JavaScript, and Python.

Ruby OO Design

class Tower
  attr_accessor :disks
  
  def initialize
    @disks = []
  end
  
  def add(disk)
    @disks.push(disk)
  end
  
  def move_to(tower)
    tower.add(@disks.pop)
  end
end

class Hanoi
  def initialize(n)
    @source = Tower.new
    @auxiliary = Tower.new
    @target = Tower.new
    
    n.downto(1) { |i| @source.add(i) }
  end
  
  def play
    move(@source.disks.size, @source, @auxiliary, @target)
  end
  
  private
  
  def move(n, source, auxiliary, target)
    if n > 0
      move(n - 1, source, target, auxiliary)
      puts "Move disk #{source.disks.last} from #{source} to #{target}"
      source.move_to(target)
      move(n - 1, auxiliary, source, target)
    end
  end
end

# Example usage:
game = Hanoi.new(3)
game.play

JavaScript OO Design

class Tower {
    constructor() {
        this.disks = [];
    }
    
    add(disk) {
        this.disks.push(disk);
    }
    
    moveTo(tower) {
        tower.add(this.disks.pop());
    }
}

class Hanoi {
    constructor(n) {
        this.source = new Tower();
        this.auxiliary = new Tower();
        this.target = new Tower();
        
        for (let i = n; i >= 1; i--) {
            this.source.add(i);
        }
    }
    
    play() {
        this.move(this.source.disks.length, this.source, this.auxiliary, this.target);
    }
    
    move(n, source, auxiliary, target) {
        if (n > 0) {
            this.move(n - 1, source, target, auxiliary);
            console.log(`Move disk ${source.disks[source.disks.length - 1]} from source to target`);
            source.moveTo(target);
            this.move(n - 1, auxiliary, source, target);
        }
    }
}

// Example usage:
const game = new Hanoi(3);
game.play();

Python OO Design

class Tower:
    def __init__(self):
        self.disks = []
        
    def add(self, disk):
        self.disks.append(disk)
        
    def move_to(self, tower):
        tower.add(self.disks.pop())

class Hanoi:
    def __init__(self, n):
        self.source = Tower()
        self.auxiliary = Tower()
        self.target = Tower()
        
        for i in range(n, 0, -1):
            self.source.add(i)
            
    def play(self):
        self.move(len(self.source.disks), self.source, self.auxiliary, self.target)
        
    def move(self, n, source, auxiliary, target):
        if n > 0:
            self.move(n - 1, source, target, auxiliary)
            print(f"Move disk {source.disks[-1]} from source to target")
            source.move_to(target)
            self.move(n - 1, auxiliary, source, target)

# Example usage:
game = Hanoi(3)
game.play()

In each of these implementations, we have two classes: Tower and Hanoi. The Tower class represents each of the three towers and holds the disks. The Hanoi class initializes the game and contains the logic to solve it. The play method in the Hanoi class starts the game, and the move method contains the recursive logic to solve the Towers of Hanoi problem.

Conclusion

Studying the Towers of Hanoi problem is crucial as it exemplifies the core principles of recursion and algorithmic problem-solving, foundational elements in computer science and mathematics. This problem is a classic example of how a seemingly complex task can be broken down into simpler, manageable subproblems, illustrating the divide-and-conquer strategy, which is pivotal in algorithm design. The recursive nature of the problem aids in understanding the concept of base cases and the stack data structure, as it inherently uses a stack to keep track of the function calls. Additionally, the Towers of Hanoi has a direct application in teaching about the runtime of algorithms, as its solution has an exponential runtime, specifically O(2^n), allowing for the exploration of algorithm efficiency and optimization. Furthermore, it provides insights into the concept of state space search, a fundamental idea in artificial intelligence. By studying this problem, learners can develop a deep understanding of critical computer science concepts, enhancing their problem-solving skills, analytical thinking, and ability to write efficient code, which are essential skills for software development and computational thinking.