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

As Peter Lang says, the number of states in the graph is $(n+2)!/2$. From each state, there are at most $6$ possible moves. So the diameter of the graph is at least $$\log_6 \frac{(n+2)!}{2} = n \frac{\log n}{\log 6} + O(n).$$

On the other hand, Jaap Scherphuis's really clever Radix Sort argument (see comment thread above) shows that the diameter is at most $$n+2 n \lceil \log_2 n \rceil = 2 n \frac{\log n}{\log 2} + O(n).$$

Thus, I would suggest focusing our efforts on finding the constant $c$ such that the diameter grows like $c n \log n$.

---

I can improve the lower bound a little bit. It never makes sense to move a disc from peg A to peg B and then move it back, nor is it ever a good idea to move a peg from A to B and then move it from B to C (because we could have just done that in one step, A to C). So, while we have $6$ choices for the first move, we only have $4$ reasonable choices for the moves after that. This improves the lower bond to $$1+\log_4 \frac{(n+2)!}{12} = n \frac{\log n}{\log 4} + O(n).$$

---

I can also improve the upper bound, by using a variant of merge sort rather than radix sort. Let $F(n)$ be the largest number of steps to get from any position where all discs are on one peg to the position where the discs are sorted on another peg. Let $G(n)$ be the same, except that I ask for the discs to end on the same peg they started on. Since we can always use $n$ steps at the start to stack all our discs up, the diameter of the graph is $F(n) + O(n) = G(n) + O(n)$.

Now, start with all the discs on peg 1 (in some order). Using $F(\lfloor n/2 \rfloor)$ steps, take the top $n/2$ discs and put them, in upside down order, on peg 2, leaving the bottom $\lceil n/2 \rceil$ discs alone. Then take the discs that remain on peg 1 and move them to peg 3 in upside down order, leaving the discs which were moved earlier alone. Finally, merge both stacks back into peg 1, using $n$ steps. This shows $$G(n) \leq F(\lfloor n/2 \rfloor) + F(\lceil n/2 \rfloor) + n.$$ Similarly, we have $$F(n) \leq F(\lfloor n/2 \rfloor) + G(\lceil n/2 \rfloor) + n.$$ (This time, move half the pegs from 1 to 3 while sorting them, leave the others in place on 1 while sorting them, then merge unto 2.)

I believe this inductively gives us $F(n)$ and $G(n) \leq n \frac{\log n}{\log 2} + O(n)$.

---

There is still a factor of $2$ difference between $\tfrac{1}{\log 4}= \tfrac{1}{2 \log 2}$ and $\tfrac{1}{\log 2}$. Let's see if we can shrink it!

Answer 2

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