Program 6: Towers of Hanoi

Program 6: Towers of Hanoi1 In Hanoi, according to legend, are three diamond rods and 64 golden discs of different sizes which can slide onto any rod. Initially all the discs are on a single rod in descending order of size – smallest at the top. Monks move the discs, one per second, from one rod to another obeying the following rules 1. Only one disc can be moved at a time. 2. Each move consists of taking the top disc from one of the stacks and placing it on top of another stack or on an empty rod. 3. No larger disc may be placed on top of a smaller disc. Their objective is to move all the discs onto a second diamond rod at which point the world ends. If we number the rods 1, 2 and 3 there is a simple recursive routine to produce the move sequence Hanoi(int Numdiscs, int source, int destination) { if (Numdiscs>1) Hanoi(Numdiscs-1,source,6-source-desination) output (“move disc on”, source, “to”, destination) if (Numdiscs>1) Hanoi(Numdiscs-1,6-source-destination,destination) } Write a Pep/9 assembly code program that implements an augmented version of the algorithm. Your program should: Prompt for Number of discs (<16) Source rod (1,2 or 3) Destination rod (1, 2 or 3) Whether moves are to be displayed (y/n) A move number (k). Compute the move sequence, outputting the details if requested Output the contents of the rods after move k (if there is one) – see examples Output the total number of moves. Extra credit: Output the rod contents vertically – see Extra Credit examples By the due date, turn in your source code and results of testing it. Grading Correctness 50 Testing 20 Readability 30 1 https://en.wikipedia.org/wiki/Tower_of_Hanoi Example program runs Number of discs (<16): 10 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): n Show discs after move k: -1 Total moves: 1023 Number of discs (<16): 10 Source rod (1,2,3): 1 Destination rod (1,2,3): 2 Show moves? (y/n): n Show discs after move k: 1022 After move 1022 Rod: 1 Rod: 2 10 9 8 7 6 5 4 3 2 Rod: 3 1 Total moves: 1023 Number of discs (<16): 3 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): y Show discs after move k: 0 move disc on rod 1 to rod 3 move disc on rod 1 to rod 2 move disc on rod 3 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 1 move disc on rod 2 to rod 3 move disc on rod 1 to rod 3 Total moves: 7 Number of discs (<16): 15 Source rod (1,2,3): 1 Destination rod (1,2,3): 2 Show moves? (y/n): n Show discs after move k: 5 After move 5 Rod: 1 15 14 13 12 11 10 9 8 7 6 5 4 1 Rod: 2 3 Rod: 3 2 Total moves: 32767 Number of discs (<16): 4 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): y Show discs after move k: 10 move disc on rod 1 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 3 move disc on rod 1 to rod 2 move disc on rod 3 to rod 1 move disc on rod 3 to rod 2 move disc on rod 1 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 3 move disc on rod 2 to rod 1 After move 10 Rod: 1 2 Rod: 2 3 Rod: 3 4 1 move disc on rod 3 to rod 1 move disc on rod 2 to rod 3 move disc on rod 1 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 3 Total moves: 15 Extra Credit Example runs Number of discs (<16): 14 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): n Show discs after move k: 1000 After move 1000 1 2 3 4 6 11 7 12 8 13 9 14 5 10 Rod 1 Rod 2 Rod 3 Total moves: 16383 Number of discs (<16): 10 Source rod (1,2,3): 3 Destination rod (1,2,3): 1 Show moves? (y/n): n Show discs after move k: 1022 After move 1022 2 3 4 5 6 7 8 9 10 1 Rod 1 Rod 2 Rod 3 Total moves: 1023