Application Center - Maplesoft

The Tower of Hanoi

You can switch back to the summary page by clicking here.

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

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.