The Tower Of Hanoi
Maple Simulation
Andy Gijbels
andy.gijbels@student.kuleuven.be
gijbelsandy@hotmail.com
www.agshome.tk
Belgium
Copyright ? 2007 by Andy Gijbels
All rights reserved
Introduction
The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape.
The objective of the game is to move the entire stack to another peg, obeying the following rules:
* Only one disk may be moved at a time.
* Each move consists of taking the upper disk from one of the pegs and sliding it
onto another peg, on top of the other disks that may already be present on that
peg.
* No disk may be placed on top of a smaller disk.
This Maple worksheet calculates the solution with minimum number of steps and visualises it in an animation.
Initialsiation
Restart
Packages
| > |
with(plots):with(plottools):with(RandomTools): |
Parameters
Number of disks
 |
(3.1.1) |
Final state rod
 |
(3.2.1) |
Speed
Minimum is 1
 |
(3.3.1) |
Create game
Storage media
Steps
| > |
if Type=standard then o:=[seq(1,i=1..n)] elif Type=random then o:=[seq(Generate(integer(range=1..m)),i=1..n)] end if: |
Disks
Heights
| > |
Heights:=array(1..2**n):seq(Heights[i]=array(1..3),i=1..2**n): |
| > |
for i from 1 to 3 do Heights[1][i]:=0:end do: |
Placing Algoritm
| > |
place:=proc(i,j,k) [-(n+1-i)+2*(j-1)*(n+1),Heights[k][j]],[(n+1-i)+2*(j-1)*(n+1),Heights[k][j]+n/5] end proc: |
Place Disks on initial positions
| > |
for i from 1 to n do
steps[1][i]:=place(i,o[i],1):
Heights[1][o[i]]:=Heights[1][o[i]]+n/5:
end do: |
Optimal Solution Algorithm
![`:=`(moves, [])](/view.aspx?SI=5083/TowersofHanoi_5.gif) |
(5.1) |
| > |
hanoi:=proc(N,source,dest,aux) global moves;
if N>0 then
hanoi(N-1,source,aux,dest):
moves:=[moves[],[N,source,dest]]:
hanoi(N-1,aux,dest,source);
end if:
end proc: |
 |
(5.2) |
Replacement Algorithm
| > |
for i from 1 to nops(moves) do
for j from 1 to n do Heights[i+1][j]:=Heights[i][j] end do:
Heights[i+1][moves[i][2]]:=Heights[i][moves[i][2]]-n/5:
Heights[i+1][moves[i][3]]:=Heights[i][moves[i][3]]+n/5:
for j from 1 to n do steps[i+1][j]:=steps[i][j] end do:
steps[i+1][n+1-moves[i][1]]:=place(n+1-moves[i][1],moves[i][3],i):
end do: |
Graphics
Platform
| > |
platform:=rectangle([2*(-1)*(n+1),-2*n/5],[2*(3)*(n+1),0],color=black): |
Rods
| > |
rods:=proc(j) display(seq(pointplot([[2*(i-1)*(n+1),Heights[j][i]],[2*(i-1)*(n+1),n/5*(n+1)]],connect=true,thickness=2),i=1..3)) end proc: |
Disks
| > |
disks:=proc(j) display(seq(rectangle(steps[j][i],color=tan),i=1..n),axes=none) end proc: |
Solver
Implementation
| > |
for i from 1 to 2**n-1 do
for j from 1 to t do
tek:=display(disks(i),platform,rods(i),title="Solving...",scaling=constrained):
SIM:=[op(SIM),tek]:
end do:
end do:
for j from 1 to t do
tek:=display(disks(2**n),platform,rods(2**n),title="Solved",scaling=constrained):
SIM:=[op(SIM),tek]:
end do: |
Visualisation
| > |
display(SIM,insequence=true,axes=none,scaling=constrained); |
Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.
