Solving tower of Hanoi with given arrangements

Question

I am given an arrangement of valid tower of Hanoi disks. The arrangement is given as an array.

For example [2,2,0]: the indices of the array are the identifiers of the disks, ordered from small to large, and the values of the array are the positions of the corresponding disks (positions are always 0, 1 or 2). In the case of [2,2,0], the smallest two disks are at the third pole, while the largest disk is at the first pole:

      |           |           |
      |           |          [0]
   [22222]        |         [111] 
  ----+----   ----+----   ----+----

Another example: [0,2,1]

      |           |           |
      |           |           |
     [0]       [22222]      [111] 
  ----+----   ----+----   ----+----

Would it be possible to solve the problem recursively for the remaining steps required to move all disks to the target pole (second pole)?

public int solveForSteps(int[] disks){
    // Is there a possible way to solve with given arrangements?
}

Answer 1

To solve the Towers of Hanoi from an arbitrary position, you can use a recursive procedure similar to the standard solution that works from the standard start position.

It just has to be a little more general.

Write a recursive procedure moveDisks(maxSize,targetPeg) that moves all the disks with size <= maxSize to the peg targetPeg, like this:

1. Find the largest disk m such that m.size <= maxSize and m is not on targetPeg. If there is no such disk, then return, because all the disks with size <= maxSize are already in the right place.

2. Let sourcePeg be the peg where m is currently, and let otherPeg be the the peg that isn't sourcePeg or targetPeg.

3. Call moveDisks(m.size-1, otherPeg) recursively to get the smaller disks out of the way.

4. Move m from sourcePeg to targetPeg.

5. Call moveDisks(m.size-1, targetPeg) recursively to put the smaller disks where they belong.

In Java, I would write it like this:

/**
 * Solve towers of hanoi from an arbitrary position
 * 
 * @param diskPositions the current peg for each disk (0, 1, or 2) in increasing
 *                      order of size.  This will be modified
 * @param disksToMove  number of smallest disks to moves
 * @param targetPeg target peg for disks to move
 */
static void moveDisks(int[] diskPositions, int disksToMove, int targetPeg)
{
    for (int badDisk = disksToMove-1; badDisk >= 0; --badDisk) {
        int currentPeg = diskPositions[badDisk];
        if (currentPeg != targetPeg) {
            // found the largest disk on the wrong peg

            // sum of the peg numbers is 3, so to find the other one:
            int otherPeg = 3 - targetPeg - currentPeg;

            // before we can move badDisk, we have to get the smaller
            // ones out of the way
            moveDisks(diskPositions, badDisk, otherPeg);

            // Move
            diskPositions[badDisk] = targetPeg;
            System.out.println(
                "Move " + badDisk + " from " + currentPeg + " to " + targetPeg
            );

            //Now we can put the smaller ones in the right place
            moveDisks(diskPositions, badDisk, targetPeg);
            break;
        }
    }
}

... well, I wouldn't write it exactly like this in real life. You can actually remove the second recursive call and the break, because the remaining iterations in the loop will accomplish the same thing.

Answer 2

I do not have a recursive solution for you. When you look at the usual recursive algorithm for Tower of Hanoi, the actual states can occur deep within the recursion tree, and if you would imagine that such a state is passed to your function, then to further solve the problem from that state requires not only a recursive call, but also rebuilding the stack of "outer" recursive calls. This seems to make it quite complex.

But you can do it iteratively. Here is one way to do it:

static void solveForSteps(int[] disks) {
    int n = disks.length;
    // Calculate the next target rod for each of the disks
    int target = 2; // The biggest disk should go to the rightmost rod
    int[] targets = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        targets[i] = target;
        if (disks[i] != target) {
            // To allow for this move, the smaller disk needs to get out of the way
            target = 3 - target - disks[i];
        }
    }
    int i = 0;
    while (i < n) { // Not yet solved?
        // Find the disk that should move
        for (i = 0; i < n; i++) {
            if (targets[i] != disks[i]) { // Found it
                target = targets[i]; // This and smaller disks should pile up here 
                System.out.format("move disk %d from rod %d to %d.\n", i, disks[i], target);
                disks[i] = target; // Make move
                // Update the next targets of the smaller disks
                for (int j = i - 1; j >= 0; j--) {
                    targets[j] = target;
                    target = 3 - target - disks[j];
                }
                break;
            }
        }
    }
}

This will print the remaining moves that are necessary to move all disks to the rightmost pole. If instead you want to target the centre pole, then just change int target = 2 to int target = 1.