Towers of Hanoi if big disks can go on top of small disks 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

 A: 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!
