variant of tower of hanoi

Question

I am having a really hard time coming up with the answer for the variants of tower of hanoi. So the puzzle goes like this: there are $n$ disks and $n+1$ pegs. There is also an adjacency restriction where at peg $i$, you can only move to peg $i-1$ or $i+1$. I need an algorithm that runs at most $\mathcal{O}(n^3)$ and $\mathcal{O}(n^2)$, can anyone help me with this? I solved the classic tower of hanoi with adjacency restriction and solved that the recursion solves to $3^n-1$ total moves. I am not sure how I should develop from this.

Answer 1

1a. Move disk $1$ to peg $n+1$, $n$ moves
1b. Move disk $2$ to peg $n$, $n-1$ moves, etc
Total $n(n+1)/2$ moves
2a. Move disk $1$ to peg $1$, $n$ moves
2b. Move the others up one, $n-1$ moves
3. Move disk $2$ to peg $2$, and the others up one
4. Etc until disk $k$ is on on peg $k$ for all $k$,
Total of steps $2$ to $4$ is $n^2$
5. Move all disks onto peg $n+1$, in $n(n+1)/2$ moves
Grand total $2n^2+n$ moves.
But the end of step 4 and the start of step 5 cancel each other, so it should be $2n^2+n-2$ moves