Solution of "Tower of Hanoi" When all disks are not in A

Question

As you know there are some ways to solve Tower of Hanoi, but they require all disks to be in one tower at the begining.

Now I wanna know is there any way to solve it, where the disks are already spread out randomly among the towers at the start.

Answer 1

Yes, it is still solvable (assuming that there are no large disks on top of smaller disks). For example:

        1
  4     2
  6     5     3
  -------------

Find the largest contiguous stack containing 1. Here, it is {1,2}. Move that stack onto the next largest disk, ignoring any others. You can use the standard Tower of Hanoi algorithm for this step.

              1
  4           2
  6     5     3
  -------------

Repeat steps above. Next contiguous stack containing 1 is now {1,2,3}. Move it onto 4

  1
  2
  3           
  4           
  6     5  
  -------------

Same thing -- move {1,2,3,4} onto 5.

        1
        2
        3     
        4     
  6     5    
  -------------

Move {1,2,3,4,5} onto 6 now, and you're done. If you need to move the whole stack to a specific peg, use the standard solution once more.

Answer 2

There is no constraint on obtaining a solution when starting with larger discs on smaller ones (for example, the discs could be in reverse order with smallest at the bottom, and the solution is then trivial). It does make the problem a little more interesting, but the puzzle does start to look like stacks of larger discs and smaller discs at some point. To move a regular small-to-large pile to accomplish the reordering, there are generally 2 moves. If the number of discs to be moved is odd, then start by moving the top (i.e. smallest) disc to the desired location, then the next smallest to the other peg, then put the smallest on top of that, and the next disc where the first one was, etc.. If the number of discs to be moved is even, then the smallest disc should be moved to the peg that is not the desired location. When the discs are in random size order, there can be some short cuts, or some complications, but the puzzle is still solvable. I should add that the aim of the random start game is simply to get the discs in correct size order on any peg, but it is obvious that the regular recursive algorithm could then be applied to move such a stack to any peg.

Answer 3

I'm no expert either but looking at this problem, considering the three stacks A B and C and as a premiss the 6 disks must finish in stack C, like the most conventional towers of Hanoi, solved this problem with 43 movements. I don't know if this is the optimal solution but there is a very interesting site one may see here

Answer 4

The solution for any legal arrangement follows the same pattern. There are only two kinds of steps in the solution:

• Move a given disk to a peg
• Move a given disk and everything smaller than it to a peg

To move a disk to a peg, either the disk is already on the peg and you're done, or the disk is not on the peg, and there is only one way to accomplish this step:

• Move all smaller disks to the third remaining peg
• Transfer the given disk from its current peg to the target peg

To move a given disk and all smaller disks to a particular peg, the only way to accomplish this goal is to follow both of the following steps in order

• Move the given disk to the target peg
• Move all of the smaller disks to the target peg

Answer 5

Your question destroyed my productivity!

I just spent my precious time trying to answer it and here is the result:

First, you have to calculate the place each disk wants to go, from the biggest to the smallest. There are 3 simple rules to follow:

1. The biggest disk wants to go to the right.
2. If the slighly bigger disk moves, a disk wants to go "out of the way" (if N+1 wants to go from LEFT to MIDDLE, then N wants to go to RIGHT).
3. If the slighly bigger disk doesn't move, a disk wants to go to that same location (if N+1stays in RIGHT, N wants to go to RIGHT).

Then move to its desired location the smallest disk that doesn't want to stay on its peg. (edit: alternatively, you can move the first disk you encounter that wants to perform a legal move, but that implies your code has a notion of what is a legal move)

Iterate until solved.

Example

Let's take Justin's example.

Initial tower

| | |
| | |
| | |
| 1 |
4 2 |
6 5 3

• 6 want to go from LEFT to RIGHT (rule 1).
• 5 want to go from CENTER to CENTER (rule 2).
• 4 want to go from LEFT to CENTER (rule 3).
• 3 want to go from RIGHT to RIGHT (rule 2).
• 2 want to go from CENTER to RIGHT (rule 3).
• 1 want to go from CENTER to LEFT (rule 2).

The first move must be placing disk 1 on the left peg (smallest disk that doesn't want to stay in place).

Next

The next moves will look like this:

| | |
| | |
| | |
1 | |
4 2 |
6 5 3

| | |
| | |
| | |
1 | |
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
2 4 |
6 5 3

etc.

// TODO : commenting

I implemented those rules, they work for any initial tower (including the regular all-left tower). Also, they always take the shortest path.

YAY! A non-recursive way to solve the tower of hanoi!