How to Build a Tower of Hanoi Solver in Both C++ and Snap! (BYOB)

This isn’t a typical tutorial where I walk through the building of a program. I was just curious how a C++ Tower of Hanoi solver translates to Snap! I can report that it translates very well. In fact, I prefer the Snap! version because the results are paired with a nice visual, making it easy to follow along.

You can find the C++ code and its Snap! equivalent below. First, a quick explanation of the game.

The Rules

Tower of Hanoi is a mathematical 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.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  • Only one disk can be moved at a time.
  • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  • No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

Screenshot (84)
3 disks take a minimum of 7 moves
Screenshot (87)
Twice as many disks take a lot more moves!

C++ Solver

The C++ program uses a recursive function.

400px-Tower_of_Hanoi_recursion_SMIL.svg.png
Illustration of a recursive solution for the Towers of Hanoi puzzle with 4 disks Source: Wikipedia.org

Wikipedia page for Tower of Hanoi. It’s an interesting read and covers the recursive, non-recursive, binary, and gray-code solutions.

I named my function moveDisks and it takes in 4 variables. n denotes the number of disks while fromTower, toTower, and auxTower denote the rods.

The code:

Screenshot (73).png

The output:

Screenshot (74)

Pretty straightforward and the results work. But wouldn’t the results be a bit more appealing in Snap! form?

Snap! (BYOB) Solver

This version follows the same recipe as the C++ code. I made a custom block, added my variables, inserted an if else statement, created my base case, then used recursion to work through the puzzle.

The custom block:

untitled script pic (3)

Where the magic happens:

untitled script pic (2).png

I used blocks from the following categories:

  • Looks
  • Control
  • Operators
  • Variables

The results:

Screenshot (66)

Screenshot (67)

Screenshot (68)

Screenshot (69)

Screenshot (70)

Screenshot (71)

Screenshot (72)

In actual game play, these are the movements (L to R):

If you’d like to play Tower of Hanoi, here are a few links:

https://www.mathsisfun.com/games/towerofhanoi.html

http://www.coolmath-games.com/0-tower-of-hanoi

That’s all there is to it! The Tower of Hanoi solver demonstrates that even a simple algorithm can be quite powerful. How long would it take to solve a 15 disk run without the solver’s help?

Watch the video below to see a 15 disk run in C++.

 

Advertisements

Comments

One comment on “How to Build a Tower of Hanoi Solver in Both C++ and Snap! (BYOB)”
  1. I like this site, useful stuff on here : D.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s