-1

I'm doing a program for my robot arm to build the tower of Hanoi. I got the algorithm working on a standing tower (replacing the tower to a different place using only 3 locations).

Locations: A, B, C
Pieces: 5

I'd like to build up the tower step-by-step (I'll place a piece on location C, the arm places the piece onto/into the tower on location A). The code is working if the current piece goes on top.

Question: Is there a (recursive) algorithm to place a piece into the tower using only 3 places (A is the current tower, C is the new piece, B empty)?

EDIT: I'm not trying to build the tower on a different place. I'm asking for an algorithm, that could place a piece on C into the tower on A (let's say tower is 5-3-2-1 and I place the final '4' piece on C. The algorithm should place it into the right place for it to become 5-4-3-2-1).

  • 2
    Possible duplicate of [Tower of Hanoi: Recursive Algorithm](https://stackoverflow.com/questions/1223305/tower-of-hanoi-recursive-algorithm) – Renat Oct 18 '19 at 17:56

1 Answers1

0

You already "...got the algorithm working on a standing tower (replacing the tower to a different place using only 3 locations)...", so proceed as follows:

  1. Determine how many pieces in stack A are smaller than the one on stack C. Call this number k. It could be zero, in which case you can just move the piece from stack C to stack A in one operation. If not:

  2. Completely ignore the pieces in stack A that are below the top k pieces. Perform this and the following steps as if they don't exist. Now use your existing algorithm (to move a stack completely to another location), to move the top k elements from stack A to position B. The pieces we ignored do not participate in this move.

  3. Then move the piece from stack C to stack A. Now also ignore this piece in the next step. So we can act as if stack A is empty now.

  4. Use your algorithm again to move stack B to location A. Again, we ignore the pieces that are already at location A: they do not move during this step.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • Yes, after a day of thinking I realized I just have to offset a stack as if there was already one placed. Thank you! –  Oct 20 '19 at 16:59