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 

 

>

restart:

 

Packages 

 

>	with(plots):with(plottools):with(RandomTools):

 

Parameters 

 

Number of disks 

 

>

n:=7;

 

(3.1.1)

 

 

Final state rod 

 

>

f:=3;

 

(3.2.1)

 

Speed 

 

Minimum is 1 

>

t:=1;

 

(3.3.1)

 

Create game 

 

Storage media 

 

Steps 

 

>	Type:=standard:

 

>	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:

 

>	steps:=array(1..2**n):

 

Disks 

 

>	steps[1]:=array(1..n):

 

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 

 

>	N:=n:moves:=[];

 

(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:

 

>	sol:=hanoi(n,1,3,2);

 

(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 

 

>

SIM:=[]:

 

>	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.