DeeA7
asked on
towers of hanoi depth first search
Hi!
I need help with towers of hanoi. I need to write program in C/c++ for depth first search algoritam.
Any help apreciated.
I need help with towers of hanoi. I need to write program in C/c++ for depth first search algoritam.
Any help apreciated.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
He just did. Consider the recursive algorithm he provided.
With n==1, it clearly provides a solution. The termination claus (n==1) is invoked and the disk is moved from the source pole to the destination pole; done.
Now suppose n==2. The first step is to call Hanoi with n-1 (which is 1), with the arguments in a different order. The disk is moved from the source, to the *by* pole. Since n==1, this will just happen in the termination clause.
Next the disk on the from pole is moved to the destination pole (again, n is 1, so this just happens).
Finally Hanoi is called again to get the disk on the by pole to the destination pole (again with argument n being 1 so it just happens in the termination clause).
If n is 3, then the first thing that happens is that Hanoi is called with *2* to get 2 disks from the from pole to the by pole. We know that Hanoi with 2 will do that (see above paragraph). Then the ring is moved from the from pole to the destination pole, and finally Hanoi is called again to get the 2 disks displaced to the by pole to the destination pole (which will work for the same reason).
This will go on indefinitely to any level (though, as pointed out, the number of steps increases exponentially with the level; this is an NP-Complete problem). *And* it is depth first, since the first recursive call goes "down" a level.
With n==1, it clearly provides a solution. The termination claus (n==1) is invoked and the disk is moved from the source pole to the destination pole; done.
Now suppose n==2. The first step is to call Hanoi with n-1 (which is 1), with the arguments in a different order. The disk is moved from the source, to the *by* pole. Since n==1, this will just happen in the termination clause.
Next the disk on the from pole is moved to the destination pole (again, n is 1, so this just happens).
Finally Hanoi is called again to get the disk on the by pole to the destination pole (again with argument n being 1 so it just happens in the termination clause).
If n is 3, then the first thing that happens is that Hanoi is called with *2* to get 2 disks from the from pole to the by pole. We know that Hanoi with 2 will do that (see above paragraph). Then the ring is moved from the from pole to the destination pole, and finally Hanoi is called again to get the 2 disks displaced to the by pole to the destination pole (which will work for the same reason).
This will go on indefinitely to any level (though, as pointed out, the number of steps increases exponentially with the level; this is an NP-Complete problem). *And* it is depth first, since the first recursive call goes "down" a level.
Did any of those comments help?
If so, it is now time to choose an answer(s) and grade and close the question.
If not, perhaps a clarifying question would help.
If so, it is now time to choose an answer(s) and grade and close the question.
If not, perhaps a clarifying question would help.
ASKER
I know that recursion solves tower of Hanoi problem, but I need to implement depth first search algoritam that runs trough all posible states and find goal. Pls, can you help me with that?