Tag: #towerofhanoi

Tower of Hanoi Solver will soon be available as a
Google Workspace Marketplace Add-on.

For transparency and compliance:

• Privacy Policy
• Terms of Service

 

 

 

 

 

 

 

When I first encountered recursion in my first-year Computer Science course at UC Berkeley, I remember feeling completely lost. The Tower of Hanoi felt like a trick: how could a solution even begin if every step depended on solving a smaller one first?

I took CS 3: Introduction to Symbolic Programming with Oliver Grillmeyer, who patiently helped us trace how pegs dynamically switch roles — source becomes helper, helper becomes target — and showed us that recursion isn’t magic. It’s structure. Still, it took me years to feel that structure rather than follow it blindly.

Understanding recursion, for me, was itself a recursive process: breaking the confusion into smaller, solvable questions. One insight led to another, and eventually something resembling clarity appeared.

🧱 From Idea to Interactive Simulation

Many years later — as an MYP Design teacher — I decided to revisit Tower of Hanoi, but this time through the lens of pedagogy. Could I help students not only solve the puzzle but see recursion as it unfolds?

Together with ChatGPT, I built a full Tower of Hanoi simulator inside Google Sheets, powered entirely by Apps Script. What made the project possible was not raw code, but a design-first conversation with AI:

What should students see? How should each move feel? How can the UI help build computational intuition? Once the experience was clearly mapped out, scripting followed naturally. 

🛠️ From Merged Disks to Painted Pegs

At first, I used merged cells to represent disks: larger disks spanned more columns, smaller disks fewer, all centered on pegs. It looked great — until I tried to move them.

Each step required breaking and re-merging cells dynamically. It was slow, fragile, and unsustainable.

So I pivoted: instead of merged cells, I painted rectangular blocks of adjacent cells, styled with consistent spacing and color. This approach:

• Simplified disk creation and movement
• Improved performance
• Made animation smooth and glitch-free

✅ Core Features

Here’s what the final simulator includes:

• 📐 Tower rendered in a dynamic grid, adjustable from 1 to 10 disks
• 🎨 Branded disk colors (hex-coded palette)
• 🧱 “Create Tower” button builds the stack interactively
• 🔁 “Solve Tower” animates the recursive steps live
• 🛑 Kill Switch (Pause) checkbox to stop long simulations
• 🧭 Sidebar UI with dropdown, buttons, and color-coded disk count
• 📖 Instruction dialog, with zoom-out tips and clear guidance
• 🔧 Gridline toggle, to switch between aesthetic and structural views
• 📊 Logging, toast messages, and pegs that visually rebuild in real time

Watch recursion come to life, one move at a time.

🔁 Recursion, Visualized Step-by-Step

(Quick terminology: the source peg is the starting peg where all disks begin, the auxiliary peg is a temporary helper peg, and the target peg is where all disks should end up.)

Once the interface worked, I implemented recursion faithfully and visibly.

For those new to Tower of Hanoi: solving it recursively always follows the same structure:

1. Move n−1 disks from source to auxiliary
2. Move the nth (largest) disk to target
3. Move n−1 disks from auxiliary to target

With every recursive call, the roles of the pegs rotate. This is the key to recursive thinking — the problem doesn’t just repeat, it reorganizes. In our code, I didn’t pre-generate moves. Each move happened only when its subproblem had been resolved. The simulation feels like how humans approach the problem — slowly, logically, recursively.

🧠 Recursive Move Breakdown for 1–11 Disks:

For 1 disk:

– Only 1 move: Source → Target

– T(1) = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

For 2 disks:

– To move 2 disks:

1. Move 1 disks from Source to Helper → T(1) moves
2. Move disk 2 to Target → 1 move
3. Move 1 disks from Helper to Target → T(1) moves

T(2) = T(1) + 1 + T(1) = 2×T(1) + 1

       = 2×(2 – 1) + 1

       = 2 + 1 = 3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

For 3 disks:

– To move 3 disks:

1. Move 2 disks from Source to Helper → T(2) moves
2. Move disk 3 to Target → 1 move
3. Move 2 disks from Helper to Target → T(2) moves

T(3) = T(2) + 1 + T(2) = 2×T(2) + 1

       = 2×(4 – 1) + 1

       = 6 + 1 = 7

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

For 4 disks:

– To move 4 disks:

1. Move 3 disks from Source to Helper → T(3) moves
2. Move disk 4 to Target → 1 move
3. Move 3 disks from Helper to Target → T(3) moves

T(4) = T(3) + 1 + T(3) = 2×T(3) + 1

       = 2×(8 – 1) + 1

       = 14 + 1 = 15

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 5 disks:

– To move 5 disks:

1. Move 4 disks from Source to Helper → T(4) moves
2. Move disk 5 to Target → 1 move
3. Move 4 disks from Helper to Target → T(4) moves

T(5) = T(4) + 1 + T(4) = 2×T(4) + 1

       = 2×(16 – 1) + 1

       = 30 + 1 = 31

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 6 disks:

– To move 6 disks:

1. Move 5 disks from Source to Helper → T(5) moves
2. Move disk 6 to Target → 1 move
3. Move 5 disks from Helper to Target → T(5) moves

T(6) = T(5) + 1 + T(5) = 2×T(5) + 1

       = 2×(32 – 1) + 1

       = 62 + 1 = 63

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 7 disks:

– To move 7 disks:

1. Move 6 disks from Source to Helper → T(6) moves
2. Move disk 7 to Target → 1 move
3. Move 6 disks from Helper to Target → T(6) moves

T(7) = T(6) + 1 + T(6) = 2×T(6) + 1

       = 2×(64 – 1) + 1

       = 126 + 1 = 127

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 8 disks:

– To move 8 disks:

1. Move 7 disks from Source to Helper → T(7) moves
2. Move disk 8 to Target → 1 move
3. Move 7 disks from Helper to Target → T(7) moves

T(8) = T(7) + 1 + T(7) = 2×T(7) + 1

       = 2×(128 – 1) + 1

       = 254 + 1 = 255

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

For 9 disks:

– To move 9 disks:

1. Move 8 disks from Source to Helper → T(8) moves
2. Move disk 9 to Target → 1 move
3. Move 8 disks from Helper to Target → T(8) moves

T(9) = T(8) + 1 + T(8) = 2×T(8) + 1

       = 2×(256 – 1) + 1

       = 510 + 1 = 511

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 10 disks:

– To move 10 disks:

1. Move 9 disks from Source to Helper → T(9) moves
2. Move disk 10 to Target → 1 move
3. Move 9 disks from Helper to Target → T(9) moves

T(10) = T(9) + 1 + T(9) = 2×T(9) + 1

       = 2×(512 – 1) + 1

       = 1022 + 1 = 1023

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 11 disks:

– To move 11 disks:

1. Move 10 disks from Source to Helper → T(10) moves
2. Move disk 11 to Target → 1 move
3. Move 10 disks from Helper to Target → T(10) moves

T(11) = T(10) + 1 + T(10) = 2×T(10) + 1

       = 2×(1024 – 1) + 1

       = 2046 + 1 = 2047

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

🧪 Proof by Induction: Why T(n−1) = 2ⁿ⁻¹ − 1

We want to prove:

T(n−1) = 2^(n−1) − 1

Which means: moving (n−1) disks takes that many moves.

✅ Base Case: n = 1

(n−1) = 0 disks → takes 0 moves

2^0 − 1 = 1 − 1 = 0 ✅

✅ Case n = 2

(n−1) = 1 disk → takes 1 move

2^1 − 1 = 2 − 1 = 1 ✅

So to move 2 disks:

– Move 1 to helper → 1 move

– Move largest to target → 1 move

– Move 1 to target again → 1 move

Total: 1 + 1 + 1 = 3 ✅

🔁 Inductive Step:

Assume T(n−2) = 2^(n−2) − 1 (true for smaller cases)

Then T(n−1) =

  = 2 × T(n−2) + 1

  = 2 × (2^(n−2) − 1) + 1

  = 2^(n−1) − 2 + 1

  = 2^(n−1) − 1 ✅

So we’ve shown that the number of moves for (n−1) disks is 2^(n−1) − 1, just as expected.

And once we’re confident that (n−1) disks require 2^(n−1) − 1 moves,

then moving n disks requires:

  – 2 × (2^(n−1) − 1)  [to move n−1 disks twice]

  – + 1 move for disk n itself

Which gives:

  2 × (2^(n−1) − 1) + 1 = 2^n − 2 + 1 = 2^n − 1 ✅

If you read this far, nice work!

 

---

💬 Final Reflection

Building this simulator with ChatGPT revealed something profound:
Recursion isn’t just a computer science trick. It’s a way of thinking. A way of trusting that if you solve the smallest pieces with care, the larger problem will resolve itself — naturally, and beautifully.

#DesignThinking #ComputationalThinking #GoogleAppsScript #EdTech #MYPDesign #TeachingInnovation #TowerOfHanoi #Recursion #AIinEducation