The disks can be put on the rod, with these RULES: only one disk can be moved at once, and it must be moved on the top of another rod. My point here is that the size of the array required to hold the results becomes unmanageable very quickly. The Towers of Hanoi is a puzzle, and if you are not very familiar with it, here is how it works: The play field consists of 3 rods, and x number of disks, each next one bigger than the previous one. So, for 3 discs, the number of moves is 2^3 - 1, or 7. The total number of moves required to move the stack of discs from one spindle to another is equal to 2^n - 1, where n is the number of discs. There is a point worth noting with regards to how big the results of this can get. game python graphics-library hanoi-towers towers-of-hanoi. It is written in python and makes use of graphics.py library to create visual effects. MovesIndex += 1 ' This recursive call moves the n-1 ' discs back from the temp spindle to the ' destination spindle. This game about solving the Towers of Hanoi containing 3 posts and user-defined number of disks. ' These next two lines move the last ' disc from the source spindle to the n spindle.ĭiscCounts(destSpindle) += 1 ' The next three lines record this ' move in the moves array for use later. If discsToMove > 0 Then ' This next line is a recursive call ' that moves n-1 discs from the source ' spindle to the temp spindle. In this ' situation, if there are discs to ' be moved, then we do some work, ' otherwise we simply do nothing. ' A recursive method needs a case where ' you simply return back (the base case), ' and one or more cases ' where you recursively call the method ' again (the recursive cases). ''' Private Sub DoMoves( ByVal sourceSpindle As Integer, _ ''' to solve the Towers of Hanoi problem. ''' Public Function GetMoves() As Integer(,)Įnd Function ''' ''' Recursive Method to get all disc moves
MovesIndex = 0 End Sub ''' ''' GetMoves is the public method that kicks off the recursive process. ''' Public Sub New( ByVal numDiscs As Integer)ĭiscCounts( 2) = 0 ReDim moves( 2 ^ numDiscs - 2, 1) Private discCounts( 2) As Integer Private moves(,) As Integer Private movesIndex As Integer ''' ''' Constructor simply sets up the local variables that we need.
''' ''' You are free to use this code, but please give me credit for it. ''' myself and my boss about how little code ''' ''' Notes: I wrote this after a discussion between
OK, here is the code for the Hanoi class:Ĭopy Code ''' ''' Author: Shannon M. You should also be able to simply copy and paste the code from here into Visual Studio 2003 and compile it. However, it will open and run correctly in Visual Basic 2005 Express Edition Beta2, which is freely available from Microsoft. The project is a Visual Studio 2005 Beta 2 Project and will not open in earlier versions of Visual Studio. Show Me The Code!Ī quick note about the code files included with this article. I imagine that many who might be reading this are scratching their heads right about now asking, "How (Why) does that work?" Let me say that I fully understand, and hopefully, seeing the code to make this work will help somewhat. That's all there is to it (more or less)! All of this will be done inside a single method in our class, and steps 1 and 3 are recursive calls back to that same method.
So, since we already know how to move a stack of discs, the process looks like this (where n is the total number of discs in the initial stack): I realize that this is counterintuitive at this point, but bear with me. The algorithm that I have implemented starts with an assumption we are assuming that we already have the ability to move a stack of discs. you can never place a larger disc on top of a smaller one.only one disc can be moved at a time, and.There are two rules governing how discs can be moved: The goal is to get the stack of discs from one post to a different post. Basically, you have three posts, one of which contains a stack of discs that get smaller as you go up, like this: In case you’re not familiar with the Towers of Hanoi problem, I’ll describe it briefly here. I was told back in school that there was a way to write a non-recursive algorithm to solve the Towers of Hanoi problem, but after a little thought (and exposure to the recursive approach), I gave up trying to figure out what it is. Really, it is perhaps the best example of a clean, simple problem to demonstrate the power of recursion. The Towers of Hanoi problem is a classic exercise meant to torture, discourage, and otherwise torment all new computer science students (or, at least that’s what they think).
I am learning about recursion in c++ but have been stumped by the following c++ code used to solve the Tower Of Hanoi problem.The purpose of this article is to demonstrate a very clean, recursive algorithm for solving the Towers of Hanoi problem, coded in VB.NET.