How do I understand the Tower of Hanoi problem using Depth First Search (DFS)?

Question

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 7-Oct-14 6:06am

mri3iguns

Updated 7-Oct-14 6:28am

v2

Add a Solution

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

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Sergey Alexandrovich Kryukov · Accepted Answer · 2014-10-07T06:25:00

Solution 1

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

Posted 7-Oct-14 6:25am

Sergey Alexandrovich Kryukov

Updated 7-Oct-14 6:27am

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