CSES Solutions – Tower of Hanoi
The Tower of Hanoi game consists of three stacks (left, middle, and right) and n round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom. The goal is to move all the disks to the right stack using the middle stack. On each move, you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.
The task is to find a solution that minimize the number of moves.
Examples:
Input: n=2
Output: 3
Explanation: Move the topmost(2nd) disk from Stack 1 to Stack 3. Then move the 1st disk from Stack 1 to Stack3 and then, again move the 2nd disk from Stack2 to Stack3.Input: n=1
Output: 1
Explanation: Move the topmost disk from Stack1 to Stack3.
Approach:
The idea is solve Tower of Hanoi problem using recursion. A recursive approach is employed, breaking down the problem into three main steps: moving ‘n-1′ disks to an auxiliary stack, transferring the largest disk to the target stack, and finally, moving the ‘n-1‘ disks from the auxiliary stack to the target stack. This recursive strategy ensures an optimal solution with minimal moves for the Tower of Hanoi puzzle.
Follow the steps to solve the problem:
- Initialize three stacks (
sourceStack
,destinationStack
,auxiliaryStack
) representing the left, right, and middle stacks, respectively. - In the recursive moveDisk function,
- If there is only one disk (
diskNumber == 1
), move it directly from the source to the destination and return. - Recursively call
moveDisk
for ‘n-1’ disks from the source to the auxiliary stack, swapping the roles of destination and auxiliary stacks. - Add the current move to the
moves
vector, indicating the source stack and destination stack. - Recursively call
moveDisk
for ‘n-1’ disks from the auxiliary to the destination stack, swapping the roles of source and auxiliary stacks.
- If there is only one disk (
- Print the total number of moves and Display the sequence of moves, indicating the source stack and destination stack for each move.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
// Recursive function to move 'diskNumber' disks from
// 'sourceStack' to 'destinationStack' using
// 'auxiliaryStack'
void moveDisk(int diskNumber, vector<vector<int> >& moves,
int sourceStack, int destinationStack,
int auxiliaryStack)
{
// Base case: If there is only one disk, move it
// directly from source to destination
if (diskNumber == 1) {
moves.push_back({ sourceStack, destinationStack });
return;
}
// Recursive call 1: Move 'n-1' disks from source to
// auxiliary, swapping roles of destination and
// auxiliary stacks
moveDisk(diskNumber - 1, moves, sourceStack,
auxiliaryStack, destinationStack);
// Add the current move to the moves vector
moves.push_back({ sourceStack, destinationStack });
// Recursive call 2: Move 'n-1' disks from auxiliary to
// destination, swapping roles of source and auxiliary
// stacks
moveDisk(diskNumber - 1, moves, auxiliaryStack,
destinationStack, sourceStack);
}
// Function to solve Tower of Hanoi problem
void towerOfHanoi(int numberOfDisks)
{
vector<vector<int> >
moves; // Vector to store the sequence of moves
int sourceStack = 1, destinationStack = 3,
auxiliaryStack = 2; // Initialize stack indices
moveDisk(numberOfDisks, moves, sourceStack,
destinationStack,
auxiliaryStack); // Call the recursive function
// Output the total number of moves
cout << moves.size() << "\n";
// Output the sequence of moves (source stack to
// destination stack)
for (auto move : moves) {
cout << move[0] << " " << move[1] << "\n";
}
}
// Driver Code
int main()
{
int numberOfDisks = 2;
towerOfHanoi(
numberOfDisks); // Call the Tower of Hanoi function
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class GFG {
// Function to move 'diskNumber' disks from the 'sourceStack' to 'destinationStack' using 'auxiliaryStack'
public static void moveDisk(int diskNumber, List<int[]> moves, int sourceStack, int destinationStack, int auxiliaryStack) {
// Base case: If there is only one disk and move it directly from source to destination
if (diskNumber == 1) {
moves.add(new int[]{sourceStack, destinationStack});
return;
}
// Recursive call 1: Move 'n-1' disks from the source to auxiliary, swapping roles of destination and auxiliary stacks
moveDisk(diskNumber - 1, moves, sourceStack, auxiliaryStack, destinationStack);
moves.add(new int[]{sourceStack, destinationStack});
moveDisk(diskNumber - 1, moves, auxiliaryStack, destinationStack, sourceStack);
}
// Function to solve Tower of the Hanoi problem
public static void towerOfHanoi(int numberOfDisks) {
List<int[]> moves = new ArrayList<>(); // List to store the sequence of moves
int sourceStack = 1, destinationStack = 3, auxiliaryStack = 2; // Initialize stack indices
moveDisk(numberOfDisks, moves, sourceStack, destinationStack, auxiliaryStack); // Call the recursive function
System.out.println(moves.size());
// Output the sequence of moves.
for (int[] move : moves) {
System.out.println(move[0] + " " + move[1]);
}
}
// Main method
public static void main(String[] args) {
int numberOfDisks = 2;
towerOfHanoi(numberOfDisks);
}
}
# Function to move 'diskNumber' disks from 'sourceStack' to 'destinationStack' using 'auxiliaryStack'
def moveDisk(diskNumber, moves, sourceStack, destinationStack, auxiliaryStack):
# Base case: If there is only one disk, move it directly from source to destination
if diskNumber == 1:
moves.append([sourceStack, destinationStack])
return
# Recursive call 1: Move 'n-1' disks from source to auxiliary, swapping roles of destination and auxiliary stacks
moveDisk(diskNumber - 1, moves, sourceStack, auxiliaryStack, destinationStack)
# Add the current move to the moves list
moves.append([sourceStack, destinationStack])
# Recursive call 2: Move 'n-1' disks from auxiliary to destination, swapping roles of source and auxiliary stacks
moveDisk(diskNumber - 1, moves, auxiliaryStack, destinationStack, sourceStack)
# Function to solve Tower of Hanoi problem
def towerOfHanoi(numberOfDisks):
moves = [] # List to store the sequence of moves
sourceStack, destinationStack, auxiliaryStack = 1, 3, 2 # Initialize stack indices
moveDisk(numberOfDisks, moves, sourceStack, destinationStack, auxiliaryStack) # Call the recursive function
# Output the total number of moves
print(len(moves))
# Output the sequence of moves (source stack to destination stack)
for move in moves:
print(move[0], move[1])
# Driver Code
if __name__ == "__main__":
numberOfDisks = 2
towerOfHanoi(numberOfDisks) # Call the Tower of Hanoi function
// Recursive function to move 'diskNumber' disks from
// 'sourceStack' to 'destinationStack' using
// 'auxiliaryStack'
function moveDisk(diskNumber, moves, sourceStack, destinationStack, auxiliaryStack) {
// Base case: If there is only one disk, move it
// directly from source to destination
if (diskNumber === 1) {
moves.push([sourceStack, destinationStack]);
return;
}
// Recursive call 1: Move 'n-1' disks from source to
// auxiliary, swapping roles of destination and
// auxiliary stacks
moveDisk(diskNumber - 1, moves, sourceStack, auxiliaryStack, destinationStack);
// Add the current move to the moves vector
moves.push([sourceStack, destinationStack]);
// Recursive call 2: Move 'n-1' disks from auxiliary to
// destination, swapping roles of source and auxiliary
// stacks
moveDisk(diskNumber - 1, moves, auxiliaryStack, destinationStack, sourceStack);
}
// Function to solve Tower of Hanoi problem
function towerOfHanoi(numberOfDisks) {
let moves = []; // Array to store the sequence of moves
let sourceStack = 1, destinationStack = 3, auxiliaryStack = 2; // Initialize stack indices
// Call the recursive function
moveDisk(numberOfDisks, moves, sourceStack, destinationStack, auxiliaryStack);
// Output the total number of moves
console.log(moves.length);
// Output the sequence of moves (source stack to
// destination stack)
for (let move of moves) {
console.log(move[0] + " " + move[1]);
}
}
// Driver Code
let numberOfDisks = 2;
towerOfHanoi(numberOfDisks); // Call the Tower of Hanoi function
Output
3 1 2 1 3 2 3
Time Complexity: O(2n), where n is number of disks.
Auxilary Space: O(n)
Contact Us