Towers of Hanoi if big disks can go on top of small disks

Question

The Tower of Hanoi puzzle is concerned with moving $n$ disks between three pegs so that a larger disk cannot be placed on top of a smaller disk. Based on a (now deleted) StackOverflow question, suppose that one can place larger disks above smaller ones.

One can represent the game state by a 3-tuple of ordered sets $(A, B, C)$.

For example, the solved state with $3$ disks is given by $([3,2,1], [], [])$:

1
2
3
* * *

Question: given an arbitrary game state, what is a minimal sequence of moves that reaches the solved state? (this thread suggests that reaching the solved state is always possible).

• There is a unique solved state with all disks placed on the first peg in order (illustrated above).
• Ideally, I am interested in an algorithm that reaches the solved state with fewest moves.
• If describing such an algorithm is difficult, I would also be interested in the minimal number of moves required to reach an arbitrary game state from any other game state (the diameter of the game state graph).
• Calculation by @PeterLang suggests that the diameter of the game state graph is given by [1, 4, 7, 10, 13, 16, 19, 22, 26, 29] for the number of disks ranging from 1 to 10. There appears to be only one OEIS sequence matching this pattern, and I have no clue if it should generalize.

---

Here is an example of solving the game with $3$ disks:

Given an initial state $([2], [1], [3])$, one can reach the solved state as follows:

                                      1        
           2         2      2         2     
2 1 3      1 3     3 1      3 1       3    
* * * => * * *  => * * * => * * * =>  * * *

with associated sequence of moves $[1 \to 2], [3\to 1], [2 \to 1], [2 \to 1]$.

---

I computed a graph $G$ with vertices corresponding to game states, so that an edge is drawn between two game states whenever one can be reached from another with a single legal move. Here is an example with two disks:

Surprisingly, the graph diameter seems to grow slowly. I wonder if it is always possible to reach the solved state in at most $1 + 3n$ moves, where $n$ is the number of disks (Peter's answer disproves this).

                 Graph Diameter  Number of Vertices
Number of Disks                                    
1                             1                   3
2                             4                  12
3                             7                  60
4                            10                 360
5                            13                2520

Answer 1

For $N$ disks the state-space consists of $\frac{(N+2)!}{2!}$ vertices.

These are the results from exhaustive search:

Disks	1	2	3	4	5	6	7	8	9	10
Diameter	1	4	7	10	13	16	19	22	26	29

This disproves the assumption of Diameter: $3N-2$

Examples of states which would require more steps to solve:

N=9, Steps=26, State: 3rd peg: 0 7 8 5 6 3 4 1 2

N=10, Steps=29, State: 3rd peg: 0 8 7 9 5 6 3 4 1 2

(In this representation, the desired end-state is: 1st peg: 0 1 2 ...)

The results were produced by the following code. It walks through the state-space in a Breadth-First Search manner, from the desired state, thus computes the minimal number of steps required to reach the desired state from all other states:

#include <deque>
#include <array>
#include <iostream>
#include <set>
#include <string>
#include <sstream>
#include <utility>

#ifndef DISKS
#define DISKS 1
#endif

const int Size = DISKS;
const int ArraySize = Size + 2;
typedef std::array<char, ArraySize> Hanoi;
// representation:
// 0. peg starts at: array[2]
// 1. peg starts at: array[array[0]]
// 2. peg starts at: array[array[1]]

Hanoi init() {
  Hanoi result;
  result[0] = ArraySize;
  result[1] = ArraySize;
  for (int i = 0; i < Size; i++) {
    result[2+i] = i;
  }
  return result;
}

Hanoi move_0_1(const Hanoi& h) {
  Hanoi result;
  int idx = 2;
  result[0] = h[0]-1;
  result[1] = h[1];
  for (int i = 2; i < h[0]-1; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[0]; i < h[1]; i++) {
    result[idx++] = h[i];
  }
  result[idx++] = h[h[0]-1];
  for (int i = h[1]; i < ArraySize; i++) {
    result[idx++] = h[i];
  }
  return result;
}

Hanoi move_0_2(const Hanoi& h) {
  Hanoi result;
  int idx = 2;
  result[0] = h[0]-1;
  result[1] = h[1]-1;
  for (int i = 2; i < h[0]-1; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[0]; i < h[1]; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[1]; i < ArraySize; i++) {
    result[idx++] = h[i];
  }
  result[idx++] = h[h[0]-1];
  return result;
}

Hanoi move_1_0(const Hanoi& h) {
  Hanoi result;
  int idx = 2;
  result[0] = h[0]+1;
  result[1] = h[1];
  for (int i = 2; i < h[0]; i++) {
    result[idx++] = h[i];
  }
  result[idx++] = h[h[1]-1];
  for (int i = h[0]; i < h[1]-1; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[1]; i < ArraySize; i++) {
    result[idx++] = h[i];
  }
  return result;
}

Hanoi move_1_2(const Hanoi& h) {
  Hanoi result;
  int idx = 2;
  result[0] = h[0];
  result[1] = h[1]-1;
  for (int i = 2; i < h[0]; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[0]; i < h[1]-1; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[1]; i < ArraySize; i++) {
    result[idx++] = h[i];
  }
  result[idx++] = h[h[1]-1];
  return result;
}

Hanoi move_2_0(const Hanoi& h) {
  Hanoi result;
  int idx = 2;
  result[0] = h[0]+1;
  result[1] = h[1]+1;
  for (int i = 2; i < h[0]; i++) {
    result[idx++] = h[i];
  }
  result[idx++] = h[ArraySize-1];
  for (int i = h[0]; i < h[1]; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[1]; i < ArraySize-1; i++) {
    result[idx++] = h[i];
  }
  return result;
}

Hanoi move_2_1(const Hanoi& h) {
  Hanoi result;
  int idx = 2;
  result[0] = h[0];
  result[1] = h[1]+1;
  for (int i = 2; i < h[0]; i++) {
    result[idx++] = h[i];
  }
  for (int i = h[0]; i < h[1]; i++) {
    result[idx++] = h[i];
  }
  result[idx++] = h[ArraySize-1];
  for (int i = h[1]; i < ArraySize-1; i++) {
    result[idx++] = h[i];
  }
  return result;
}


std::pair<Hanoi, int> bfs_path() {
  std::pair<Hanoi, int> result = std::make_pair(init(), 0);
  std::set<Hanoi> states;
  std::deque<std::pair<Hanoi, int>> queue;
  queue.push_back(std::make_pair(init(), 0));
  while (!queue.empty()) {
    auto current = queue.front().first;
    auto path_len = queue.front().second;
    if (path_len > result.second) {
      result = queue.front();
    }
    queue.pop_front();
    Hanoi state;
    if (current[0] > 2) {
      state = move_0_1(current);
      if (states.insert(state).second) {
        queue.push_back(std::make_pair(state, path_len+1));
      }
      state = move_0_2(current);
      if (states.insert(state).second) {
        queue.push_back(std::make_pair(state, path_len+1));
      }
    }
    if (current[1] > current[0]) {
      state = move_1_0(current);
      if (states.insert(state).second) {
        queue.push_back(std::make_pair(state, path_len+1));
      }
      state = move_1_2(current);
      if (states.insert(state).second) {
        queue.push_back(std::make_pair(state, path_len+1));
      }
    }
    if (ArraySize > current[1]) {
      state = move_2_0(current);
      if (states.insert(state).second) {
        queue.push_back(std::make_pair(state, path_len+1));
      }
      state = move_2_1(current);
      if (states.insert(state).second) {
        queue.push_back(std::make_pair(state, path_len+1));
      }
    }
  }
  std::cout << "Visited states: " << states.size() << std::endl;
  return result;
}

std::string to_string(const Hanoi& h) {
  std::stringstream ss;
  for (int i = 2; i < h[0]; i++) {
    ss << (int)h[i] << " ";
  }
  ss <<  "| ";
  for (int i = h[0]; i < h[1]; i++) {
    ss << (int)h[i] << " ";
  }
  ss <<  "| ";
  for (int i = h[1]; i < ArraySize; i++) {
    ss << (int)h[i] << " ";
  }
  return ss.str();
}

int main() {
  auto result = bfs_path();
  std::cout << "Max steps needed: " << result.second << " For State: " << to_string(result.first) << std::endl;
}

It is recommended to compile it with the best optimization, e.g.:

g++ hanoi.cpp -D DISKS=8 -std=c++11 -O3 -o hanoi && ./hanoi