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.

The task for the tower of Hanoi is to transfer all disks from the first tower to the third. What is the task (i.e. the desired end state) in your case? What constraints hold on the initial state? — Martin B, Jan 18 '12 at 13:39
@MoeinHm, I've edited the question. I hope the current version makes sense. Is it clear for you? — Aaron McDaid, Jan 18 '12 at 13:43
@AaronMcDaid ,yes,tnx and I also sorry for my english,I should spend more time to improve it instead of computer:D — Moein Hosseini, Jan 18 '12 at 13:46

score 8 · Accepted Answer · answered Jan 18 '12 at 13:46

8

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.

answered Jan 18 '12 at 13:46

Justin

6,611
3
36
57

1

Is it possible to know the minimal number of movements to do ? Because your algorithm isn't the fastest way to solve it. – Stephane Mathis Dec 24 '13 at 10:11
@StephaneMathis -- It isn't optimal? I can't think of a faster way, but I am certainly no expert, just someone who played with a wooden version of the puzzle long ago. What improvements would you suggest? Feel free to add an answer of your own :) – Justin Dec 27 '13 at 01:21
3

Well, in your example at the second step, it's better to move the 4 above the 5 and then 1-2-3 above the 4. You kind of skip the third step. – Stephane Mathis Dec 27 '13 at 12:14
(12)>4, 3>5, (12)>3, 4>C, (123)>4, 5>6, (1234)>5. – Will Ness Jan 30 '18 at 16:47

score 0 · Answer 2 · edited Jul 21 '16 at 15:14

0

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

edited Jul 21 '16 at 15:14

xenteros

15,586
12
56
91

answered Jul 21 '16 at 13:09

Francisco

1

score 0 · Answer 3 · answered Jul 21 '16 at 15:25

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

score 0 · Answer 4 · edited Jun 20 '20 at 09:12

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:

The biggest disk wants to go to the right.
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).
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).

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.

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

5 Answers5

Example

Initial tower

Next