The Magnetic Tower of Hanoi
Figure 4: The start-setting (top), an intermediate setting (center) and the end-state (bottom) for the N=2 MToH
Download 2.78 Mb.
|
- Navigate this page:
- Step number Disks From
Figure 4: The start-setting (top), an intermediate setting (center) and the end-state (bottom) for the N=2 MToH puzzle. The number of moves to progress from the start-setting to the intermediate state described by the center figure is 2. The number of moves to progress from the center-described state to the end-state described by the bottom figure is again 2. Thus, the (minimum) number of moves required to solve the puzzle is S(2) = 4. Note that two different solution routes, both of length 4, exist (1,2,1,1 – shown, 1,1,2,1 – not shown). Consulting Figure 4 we find for the N=2 case -  . (4)
The small disk made 3 (=31) moves and the large disk made 1 (=30) move. Thus far then, for the N=1 and N=2 cases, base 3 is elegantly spanned as  and  ; N = 1,2. (5)
Exactly analogous to the base 2 span by the classical ToH (Equation 1 and Equation 2). But let's see now the N=3 case. To conveniently talk about the N=3 case, let's (arbitrarily and without loss of generality) define the posts (refer to Figure 5 below) as
S – the Source Post D – the Destination Post I – the (remaining) Intermediate Post Let's also memorize the disk numbering convention: 1 – the largest disk 2 – the mid-size disk 3 – the smallest disk
Directory: ~dechter -> courses courses -> Ideas for projects 276-2017: Come up with your own idea. Must be relevant to the class Download 2.78 Mb. Share with your friends:
|