Step 3, Repeat both steps until all disks have been moved to their final location. Step 2, move another disk legally (there will only be one possibility). Step 1, move the smallest disk to the peg it has not recently come from (or if it’s the very first move, move the smallest disk to the non-target peg if there are an even number of disks, otherwise, move it to the target peg). As we’ll describe briefly in the following Analysis section, this algorithm is in fact an “optimal” solution, in that it solves the problem in the absolute minimal number of moves. Solution for solving 3 peg Tower Of Hanoi An algorithm that solves the Tower of Hanoi problem is shown below. 2.) A disk can only be moved if it is the upper most disk on a peg, and it can only be placed on a destination peg, if it is smaller than the topmost disk currently on the destination peg. The goal of the puzzle is to move all the disks from a source peg, to a destination peg, with a minimal number of moves, without violating the following rules: 1.) Only one disk can be moved at a time. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape. The puzzle consists of three pegs, and a number of disks of different sizes which can slide onto any peg. Tower of Hanoi The Tower of Hanoi puzzle was invented in 1883 by a French mathematician named Edouard Lucas. Then I will look at a very similar problem, called the Reeve’s Puzzle, and it’s algorithm to see if it can be shown to be optimal as well. McCann 1 (of 9) William McCann Professor Langston Discrete Mathematics AugTower Of Hanoi & Reve Puzzles Abstract In this paper I will describe the Tower Of Hanoi puzzle along with an algorithm proven to be an optimal solution.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |