Ways we tried to solve the Hanoi Tower problem
For Flatiron School homework this weekend, we had to solve the Tower of Hanoi problem in Ruby.
A quick description of the puzzle, from Wikipedia:
“The Tower of Hanoi is… a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, 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 rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.”
Before I could program the solution to the puzzle, I had to figure out the logic for myself. I was able to solve the puzzle intuitively, but breaking down that intuitive solution into a pattern I could describe programmatically was really difficult.
I’m a visual thinker, so I tried a few different visual solutions to try to parse out the pattern.
First, I took screenshots of every step of the process to solve the problem, from the handy gif on the Wikipedia page.
The interlacing of blocks reminded me of braiding hair, so I tried making a map of the pattern as if it were threads:
That was fun, but it didn’t really get me too far. Then I tried listing out each step numerically:
I noticed from this that the pattern mirrored at the middle step, but I wasn’t sure how that would help me describe it in code, either.
I wound up using stacked pieces of paper:
From that I was able to derive a rule set. The rules I decided on were:
Going from biggest to smallest, check if each ring is topmost on its post. If it is, check if it is smaller than the ring in each of these spaces (or if the space is empty):
1) one to the right
2) two to the right
3) two to the left
4) one to the left
Move the ring to the first matching option in the list 1-4.
I set up each post as an array, with the first array containing four rings of size 1,2,3,4. Then, I started trying to write a complicated if/else statement describing when the rings could and couldn’t move, using the shift and unshift methods to move “rings” between arrays. I made a bit of progress but got stuck and was unable to complete the puzzle.
I came into school the next day feeling utterly frustrated, and wanted to see how other people were trying to solve the problem.
Tyler decided to make a jQuery tower of cheese:
Alex had a cheat sheet that looked like something out of A Beautiful Mind:
David said that if I’d scrolled down a little further on the Wikipedia page, the same page I’d grabbed the handy gif from, I would’ve seen this recursive solution:
let n be the total number of discs
- move n−1 discs from A to B. This leaves disc n alone on peg A
- move disc n from A to C
- move n−1 discs from B to C so they sit on disc n
That’s a lot simpler than my giant pile of conditional statements.
I don’t know that I’d ever have come up with this solution, no matter how many hair braid images or stacks of paper I made. Moving n-1 discs isn’t something I would have thought to do, or if I did eventually think of it, I’m sure it would’ve taken me quite a while to get there.
The moral of the story might be to read the whole damn wikipedia page. It would have been more efficient if I’d done that in the first place. But I am glad I went through the frustrating mental exercise. I got a lot more comfortable with using the shift and unshift methods, and I found some hair-braid maps and towers of cheese along the way.
