N Disks and K Pegs -- General Problem of Hanoi Tower.

Problem:  Most people must be aware of the Tower of Hanoi problem that has N disks and 3 pegs. Basic Hanoi problem can be solved either by iterative or recursive approach. However, here we discuss a more general problem. Given N disks and K pegs, also given a start state (e.g., the peg that a particular disc is on) and an end state, try to find the optimal solution (i.e., minimum moves) to move the disks such that we can go from the start state to the end state. Here we still need to follow the similar rule in Hanoi: larger disk should be below smaller disk.

For example, assume we have 4 pegs, and the start state is: pegs[1] = [3,2] (which means disk 3 and disk 2 are on peg 1), pegs[2] = 4, pegs[3] = 1, pegs[4] = []; the end state is pegs[1] = [1], pegs[2] = [3], pegs[3] = [],  pegs[4] = [4,2]. The optimal solution is 2->4, 1-> 4, 1->2, 3->1 ( here "2->4" means move the top of peg 2 to peg 4), totally 4 moves.

Solution: if the N and K are not too large, we can use DFS to solve this problem. Basically, the total space will be K^N, but we are able to prune out some unfeasible paths.

• Basically, we try all the possible moves in a DFS way. If we reach the end state, we stop and return. Meanwhile, we need to remember how many moves it takes to the end and store it in current_min.
• If from the start state, we have already made current_min moves, we don't need to go further, since we can't get a result better than  current_min.
• We need to have a hash table to remember the state we have seen before. If we found we revisited a state, try to compare the moves that we have made now and the previous number of moves to reach that state. If now we take less move to revisit the state, we go forward. Otherwise, we can just return.

The pseudo code is as follow:

// the counter for the number of moves from the 
// start state 
int cnt = 0
// the current minimum moves to the end state
int current_min = INT_MAX
// a hash table to remember the visited states
hash_table ht;

void dfs()
{
  if(cnt >= current_min) return;
  // get the current state of disks   
  string stat = get_state()
 
  // if stat is not in hashtable
  if(!ht.has_key(stat))
  {
    ht[stat] = cnt;  
  }
  else
  {
     // if we take more moves to 
     // visit this state, we just
     // return
     if(ht[stat] <= cnt) return;
     ht[stat] = cnt;
  }   

  // if we reach the end state
  if(stat == end_state)
  {
     if(current_min > cnt)
     current_min = cnt;
     return;
  }
  
  for(int i=0; i<K; i++)
  {
     current_disk = peg[i].top();
     // iterate all the possible moves
     // current_disk can make
     for move in possible_move_set
     {
        make the move;
        cnt++;
        dfs();
        rewind the move;
        cnt--;
     }
  }

}