Tower of Hanoi - Solution #1
To demonstrate how I came up with the recursive solution, I will use a Tower of Hanoi game with 4 discs:
The game is solved if these 4 discs are moved from the first peg to the third peg. I'm going to use a method called move() which has inputs of: # of discs, start location, and finish location. Thus, to solve the problem, I should call move(4,0,2). The first peg is the '0' peg for ease in programming.
However, we can't actually move all 4 discs when move() is called since that isn't allowed in the game. Instead we'll have to figure out move()s that are smaller and only single disk move()s will be allowed to move a disk (an array or stack value).
move(4,0,2) can be broken into these smaller move()s:
This can be described by:
- > move(3,0,1) //move 3 from 0 to 1
- > move(1,0,2) //move 1 from 0 to 2
- > move(3,1,2) //move 3 from 1 to 2
This simplification can be done recursively on the stack of 3 disks and eventually every move() is only moving 1 disk at a time. The proper recursion can be inferred for moving n discs from start to finish:
- > move(n-1,start,other) //other is the other peg (not the start peg or finish peg)
- > move(1,start,finish)
- > move(n-1,other,finish)
And that's it, we've solved the Tower of Hanoi by recursion!
NOTE: I solve for the other peg variable by boolean logic! Make a 3 element boolean array with the start and finish positions set to true then you can find the index that is still false to determine other.