hanoi Algorithm
The Tower of Hanoi Algorithm is a classic mathematical puzzle that was initially invented by the French mathematician Edouard Lucas in 1883. The problem consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks stacked in increasing size on one rod, the smallest disk on top, 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 consists of taking the top disk from one of the stacks and placing it on top of another stack, and (3) no disk may be placed on top of a smaller disk.
The Tower of Hanoi Algorithm is a recursive approach to solve this problem. The key idea of the algorithm is to break down the problem into smaller subproblems, and then solve each subproblem independently. The algorithm first moves the top n-1 disks to an auxiliary rod (using the same rules), then moves the largest disk to the target rod, and finally moves the n-1 disks from the auxiliary rod to the target rod. The algorithm repeats these steps recursively until the base case is reached, which is when there is only one disk to be moved. Due to its recursive nature and simplicity, the Tower of Hanoi Algorithm is often used as an introductory example for teaching recursion and divide-and-conquer techniques in computer science and mathematics courses.
pub fn hanoi(n: i32, from: i32, to: i32, via: i32, moves: &mut Vec<(i32, i32)>) {
if n > 0 {
hanoi(n - 1, from, via, to, moves);
moves.push((from, to));
hanoi(n - 1, via, to, from, moves);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn hanoi_simple() {
let correct_solution: Vec<(i32, i32)> =
vec![(1, 3), (1, 2), (3, 2), (1, 3), (2, 1), (2, 3), (1, 3)];
let mut our_solution: Vec<(i32, i32)> = Vec::new();
hanoi(3, 1, 3, 2, &mut our_solution);
assert_eq!(correct_solution, our_solution);
}
}
