Click here to Skip to main content
15,935,728 members
Please Sign up or sign in to vote.
2.00/5 (1 vote)
See more:
I am trying to understand the problem.

I have 3 pegs and 5 disks. I have to eventually get the last disk to the destination peg. I can move the disks but a larger disk cannot be on top of a smaller disk.

I keep reading 'N-1' disks. This refers to the number of disks but how does the program know which is the largest and which is the smallest. I've looked up examples and none explicitly addresses this. (at least i don't think they did)

Also DFS is an uninformed search meaning that child nodes have to be built from the different 'states' of each possible move.
I am not sure how these states are represented.
Also what connects the disk to the peg it was moved onto. It feels like I am missing a lot of things underneath the representing code.
Posted
Updated 7-Oct-14 6:28am
v2
Comments
[no name] 7-Oct-14 12:17pm    
Not everybody here maybe knows "DFS". Maybe you can write the complete Name of it?
Sergey Alexandrovich Kryukov 7-Oct-14 12:20pm    
DFS?
—SA
Sergey Alexandrovich Kryukov 7-Oct-14 12:24pm    
The problem has at least two solutions: one is recursive and another one (less known) is the circular moving to the first allowed position, on each step. I don't know if one of those algorithms is the fastest and which algorithm is faster, in terms of number of steps. You can figure the second by yourself and try to find the fastest theoretically.

Both needs nothing but knowing the number of disks on each peg before any next move. This should be apparent from the formulation of the problem.

—SA

1 solution

Please see my comment to the problem. It's obvious that the only state needed to apply any algorithm is the number of disks on each peg at the moment. So, this would be an array of 3 integers. I don't understand what could be a problem here. It seems to be way too trivial.

—SA
 
Share this answer
 
v2
Comments
mri3iguns 7-Oct-14 12:44pm    
Yea i think it is because i don't really understand how it works. Maybe I am being to literal of wanting to know things like "How does the algorithm know not to put a big disk on top of a small disk?" Maybe it doesn't need to know because the algorithm handles it for you.
There may be a lot for me to understand and asking it here may not be the best place as i need step by step explanation of what is going on. Thank you for your help.
Sergey Alexandrovich Kryukov 7-Oct-14 12:51pm    
Algorithm 1: solve the problem for, say, two disks.
For N disks, reduce it to N-1 disks. Use recursion. Stop the recursion when you have only two disks 2 move.

Algorithm 2:
Move disks in one fixed direction, say, clockwise. Put the disk on the first allowed peg on each step.

—SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900