Hanoi Tower Solution When All Drives Are Not in A

Question

As you know, there are some ways to solve the Tower of Hanoi, but they require all the drives to be in the same tower at the beginning.

Now I want to know if there is a way to solve this problem when the drives are already randomized among the towers in the beginning.

Answer 1

Yes, it is still solvable (assuming there are no large disks on large disks). For instance:

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

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

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

Repeat the steps above. The next continuous stack containing 1 is now {1,2,3}. Move it to 4

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

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

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

Move {1,2,3,4,5} to 6 now and you're done. If you need to move the entire stack to a specific binding, use the standard solution again.

Answer 2

I am not an expert, but looking at this problem, given the three stacks AB and C, and, as a package, 6 disks should end in stack C, like most ordinary Hanoi towers, they solved this problem with 43 movements. I do not know if this is the best solution, but there is a very interesting site that can be seen here

Answer 3

The solution for any legal agreement follows the same pattern. There are only two types of steps in a solution:

• Move the specified drive to the binding
• Move the specified drive and everything smaller than it to the binding

To move a disk to a binding, either the disk is already on the binding and everything is ready, or the disk is not on the binding, and there is only one way to perform this step:

• Move all smaller drives to the third remaining binding
• Move this drive from its current binding to the target binding

To move a given drive and smaller drives to a specific binding, the only way to achieve this goal is to follow these steps in the following order:

• Move this drive to the target binding
• Move all smaller disks to the target binding

Answer 4

Your question ruined my productivity!

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

First you need to figure out the place where each drive wants to go, from the largest to the smallest. There are 3 simple rules:

• The largest drive wants to go right.
• If a disk with a large number of disks moves, the disk wants to "get out of the way" (if N+1 wants to switch from LEFT to MIDDLE , then N wants to go to RIGHT ).
• If a disk with a large volume does not move, the disk wants to go to the same place (if N+1 remains in RIGHT , N wants to go to RIGHT ).

Then it will move to the right place on the smallest disk that does not want to remain mated . (edit: as an alternative, you can transfer the first disk you encounter that wants to make a legal move, but that means your code has an idea of ​​what the legal move is)

Iterate until it decides.

Example

Take Justin's example.

Starting tower

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

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

The first step should be to place disk 1 on the left pointer (the smallest disk that does not want to stay in place).

Further

The following steps 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 these rules, they work for any initial tower (including the usual all-left tower). In addition, they always take the shortest path.

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