fifi129
asked on
tower of hanoi
What is the algorithm for depth-first search for tower of hanoi!
Is this a school assignment>
..
Looks like it doesn't it.
Can you be a bit more precise? We don't want to make your homework, but we can help with problems you encounter while making the assignment.
Can you be a bit more precise? We don't want to make your homework, but we can help with problems you encounter while making the assignment.
the graph describe the search:
(n,0,0)
| \
(n-1,1,0) (n-1,0,1)
| \ | \
(n-2,1,1) (n-1,0,1)(n-1,1,0) (n-2,1,1)
....................
the algorithm will look like:
move_tower(a,b,c)
{
//source a,target c,b is additional:
check feasible placement,then choose one;
move_piece(1,a,b or c);//move one piece from a to b or c;
if(succeed()) return;
move_tower(a b c);
}
You need to add depth limit to the recursive calls,and to record its status so not to do the non-stop calling.Then the second level's second status,won't appear ,for it is the same as the third level's second status.
Perhaps it's wrong.
(n,0,0)
| \
(n-1,1,0) (n-1,0,1)
| \ | \
(n-2,1,1) (n-1,0,1)(n-1,1,0) (n-2,1,1)
....................
the algorithm will look like:
move_tower(a,b,c)
{
//source a,target c,b is additional:
check feasible placement,then choose one;
move_piece(1,a,b or c);//move one piece from a to b or c;
if(succeed()) return;
move_tower(a b c);
}
You need to add depth limit to the recursive calls,and to record its status so not to do the non-stop calling.Then the second level's second status,won't appear ,for it is the same as the third level's second status.
Perhaps it's wrong.
ASKER
Thanks a lot
But how can i perform the backtrack
(check the moved pattern existed in its ancester or not)
(All node in the path of the tree should be unique)
Thank you
Fannie
But how can i perform the backtrack
(check the moved pattern existed in its ancester or not)
(All node in the path of the tree should be unique)
Thank you
Fannie
See
http://www.pangea.ca/kolar/javascript/Hanoi/HTonWebE.html
for links to web resources and(for example)
http://www.pangea.ca/kolar/javascript/Hanoi/algo.html
for fast non recursive algorithm(+source
text)
Alex
http://www.pangea.ca/kolar/javascript/Hanoi/HTonWebE.html
for links to web resources and(for example)
http://www.pangea.ca/kolar/javascript/Hanoi/algo.html
for fast non recursive algorithm(+source
text)
Alex
ASKER
I've already visit the sites.
Anyway, thanks to all of you
Anyway, thanks to all of you
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Is there are reason why you can't post the solution here?