Unit 4 - Divide & Conquer
The Three Towers
The problem of Benares Temple
In Benares, India, there stood the great temple of Brahma. It is made of 64 discs made of gold, each one smaller than the last. This spurred the creation of a legend way back in 1883.
According to the legend, there exists a large room with three poles surrounded by 64 golden disks, the priests of Brahma have been moving these golden disks, in accordance with the rules of a puzzle.
Based on an ancient prophecy, when the last move of the puzzle is completed, the world will end. The puzzle has appeared many times in popular culture. In the film Rise of the Planet of the Apes in 2011, it appeared as an intelligence test for apes.
The rules are very simple:
Disks are stacked smallest to largest on pole #1 (A).
Disks must end up stacked smallest to largest on another pole - typically #3 (C).
Only one disk may be moved at a time.
A larger disk may not be put on top of a smaller disk.
(Note, the labels of the poles are in the picture are arbitrary)
The process of moving a disk is simple. You may only take the singular top disk off a pole and place it onto another pole if the top disk of that destination is larger than the disk in your hand (or the destination is empty).
Iteration and Stacks
An iterative algorithm (loops) that moves "disks" from one pole (Stack) to another following the rules stated above.
towers_iterative(n)
Which includes the helper function:
move_disk(src, dest)
The variable "n" represents the number of disks to start with on pole "A". The final destination is "C". Each pole is a Stack object where the top can be peeked or popped but the remainder of the stack cannot move.
You could automate it graphically or print each movement to the console: Move disk 2 from A to B, for example.
Recursion
A recursive algorithm that moves "disks" from one pole to another following the rules stated above.
towers_recursive(num_of_disks, start_rod, dest_rod, aux_rod)
This can be simplified to:
towers_recursive(n, from, to, aux)
The variable "n" represents the number of disks currently on the "from" pole. Each pole is just a string to name the pole. This is helpful for debugging (printing to the console).
You could automate it graphically or print each movement to the console: Disk 2 moved from A to C, for example.