How to implement a recursive algorithm backwards

Question

I am trying to solve a variant of the Towers of Hanoi Problem where there are three pegs but two towers of the same height and disk sizes. The task is to swap the two towers.

My solution is to stack both towers together to a big tower (disks of the same size can be stacked on top of each other) and split them up again (to switched pegs of course).

I was able to stack both towers together but I am not able to reverse my algorithm to split them up again.

In this situation there are two towers with three disks each. One on the left and one in the middle. After my algorithm there is one tower with six disks on the right peg.

My algorithm is as follows: (I'm using Java)

public void solve() {
    combineTo(3, 0, 1, 2); // parameters: (height, from, to, temp)
    splitUp(?, ?, ?, ?);
}

private void moveDisk(int from, int to){
    // here are also a few other things going on but 
    // that doesn't matter in this case
    System.out.println("from: "+from+" - to: "+to);
}

private void moveTower( int i, int from, int to, int temp) {
    if (i == 0) return;
    else{
        moveTower( i-1, from, temp, to );
        moveDisk(from, to);
        moveDisk(from, to);
        moveTower( i-1, temp, to, from );
    }
}

private void combineTo( int i, int from, int to, int temp ){
    if (i==0) return;
    else{
        combineTo(i-1, from, to, temp);
        moveDisk(to, from);
        moveTower(i-1, temp, to, from);
        moveDisk(from, temp);
        moveDisk(from, temp);
        moveTower(i-1, to, temp, from);
    }
}

private void splitUp( int i, int from, int to, int temp ){
    if (i==0) return;
    else{
        ???
    }
}

So how do I reverse this with the splitUp method?

Answer 1

You've got the hard part! Think of dealing cards off the bottom of a deck. Once they're combined in a single stack, just move the whole stack to where you need the bottom disk to be. Then move the whole stack again minus the bottom element to where the disk second from the bottom needs to be. Etc. Maybe there's a cleverer way, but this surely works.

(You can also do the unstacking by dealing two off the bottom at a time, the reverse of the way you did stacking. This might be a little more efficient.)

Here's a C version with simple text graphics. Note I used a slightly different way of building the single stack. Yours is a bit more efficient in total moves. We're swapping the positive-labeled disks with the negative:

#include <stdio.h>

// Three pegs with various numbers of integer-labeled disks.
struct peg {
  int disks[30];
  int n_disks;
} pegs[3];

// Set up positive-labeled disks on peg 0 and negative ones on peg 1.
void init(int n_disks)
{
  for (int i = 0; i < n_disks; ++i) {
    pegs[0].disks[i] = n_disks - i;
    pegs[1].disks[i] = -(n_disks - i);
  }
  pegs[0].n_disks = pegs[1].n_disks = n_disks;
}

// Draw simple text graphic of pegs.
void show(void)
{
  printf("|\n");
  for (int i = 0; i < 3; i++) {
    printf("|");
    for (int j = 0; j < pegs[i].n_disks; j++)
      printf("|%2d|", pegs[i].disks[j]);
    printf("\n|\n");
  }
  printf("\n");
}

// Move one disk and draw the pegs.
void move_1(int a, int b)
{
  struct peg *peg_a = &pegs[a], *peg_b = &pegs[b];
  int disk = peg_a->disks[--peg_a->n_disks];
  peg_b->disks[peg_b->n_disks++] = disk;
  //printf("move disk %d from peg %c to peg %c\n", disk, 'A' + a, 'A' + b);
  show();
}

// Move top n disks of tower at from to to using tmp as storage.
void move(int n, int from, int to, int tmp)
{
  if (n == 0) return;
  move(n - 1, from, tmp, to);
  move_1(from, to);
  move(n - 1, tmp, to, from);
}

// Stack the towers 0 and 1 of height n into a single tower on 2.
void stack(int n)
{
  if (n == 0) 
    return;
  // Extra base case skips a couple of redundant moves.
  if (n == 1) {
    move_1(0, 2);
    move_1(1, 2);
    return;
  }
  stack(n - 1);
  move_1(0, 1);
  move(2 * (n - 1), 2, 0, 1);
  move_1(1, 2);
  move_1(1, 2);
  move(2 * (n - 1), 0, 2, 1);
}

// Swap contents of pegs 0 and 1 using 2 as temp storage.
void swap(void)
{
  stack(pegs[0].n_disks);
  int n = pegs[2].n_disks;
  move(n, 2, 1, 0);
  while (n > 0) {
    move(--n, 1, 0, 2);
    move(--n, 0, 1, 2);
  }
}

int main(void)
{
  int n = 3;
  init(n);
  show();
  swap();
  return 0;
}

Answer 2

As Gene said, I already had the hardest part. With the algorithm I provided in my question, I already had one big stack on the right.

I then moved that stack with the classic hanoi algorithm to the left and added the following recursive algorithm.

public void solve() {
    combineTo(i, 0, 1, 2); // combines 2 stacks to the right
    hanoi(2*i, 2, 0, 1); // moves big stack to the left
    splitTower(2*i, 0, 1, 2); // splits tower up again
}

private void splitTower( int i, int from, int to, int temp) {
    if (i == 0) return;
    else{
        hanoi(i-1, from, to, temp);
        splitTower( i-1, to, from, temp );
    }
}


private void hanoi( int i, int from, int to, int temp) {
    if (i == 0) return;
    else{
        hanoi( i-1, from, temp, to );
        moveDisk(from, to);
        hanoi( i-1, temp, to, from );
    }
}