I thought four-peg Hanoi was easy

The problem

AcWing 96, Strange Hanoi. Four pegs: $A$, $B$, $C$, $D$. $n$ distinct disks, all on $A$ at the start, increasing size from top to bottom. Move the whole stack from $A$ to $D$.

Rules: one disk at a time. A disk may go on an empty peg or onto a larger disk.

For each $n$ from $1$ to $12$, the minimum number of moves. No input. Twelve lines of output, line $i$ for $n = i$.

Sample output:

1
3
5
9
13
17
25
33
41
49
65
81

Three pegs

Write $T_3(n)$ for the minimum moves with three pegs and $n$ disks. The recurrence is

You can read the moves off the formula. Goal: $n$ disks from src to dest, the leftover peg aux.

1. Move the top $n-1$ from src to aux. Same problem, fewer disks.
2. Move the largest disk from src to dest. One move.
3. Move the $n-1$ from aux to dest.

int min_moves_three_pegs(int disk_count, int src_peg, int dest_peg, int aux_peg,
                         std::vector<Move>* moves) {
  if (disk_count == 1) {
    record_move(moves, src_peg, dest_peg);
    return 1;
  }

  int move_count = 0;
  move_count +=
      min_moves_three_pegs(disk_count - 1, src_peg, aux_peg, dest_peg, moves);
  record_move(moves, src_peg, dest_peg);
  ++move_count;
  move_count +=
      min_moves_three_pegs(disk_count - 1, aux_peg, dest_peg, src_peg, moves);
  return move_count;
}

Four pegs

Write $T_4(n)$ for four pegs. I thought this would be easy. I was wrong. It is a hard problem. I looked at the answer — poke at it yourself first, then look:

Pegs: src, aux1, aux2, dest. The min is over $n-1$ ways to split. For each $i$:

1. Move the top $i$ disks from src to aux1. Four pegs, fewer disks.
2. Move the remaining $n-i$ from src to dest. Those $n-i$ are all larger than the $i$ sitting on aux1, so aux1 is off limits. What is left is three pegs: src, dest, aux2.
3. Move the $i$ from aux1 to dest. Four pegs again.

Try every $i$, keep the best.

int min_moves_four_pegs(int disk_count, int src_peg, int dest_peg, int aux_peg1,
                        int aux_peg2, std::vector<Move>* moves) {
  if (disk_count == 1) {
    record_move(moves, src_peg, dest_peg);
    return 1;
  }

  int min_move_count = 0;
  int best_split = 1;
  for (int split = 1; split < disk_count; ++split) {
    int trial_move_count = 0;
    trial_move_count += min_moves_four_pegs(split, src_peg, aux_peg1, dest_peg,
                                            aux_peg2, nullptr);
    trial_move_count += min_moves_three_pegs(disk_count - split, src_peg,
                                             dest_peg, aux_peg2, nullptr);
    trial_move_count += min_moves_four_pegs(split, aux_peg1, dest_peg, src_peg,
                                            aux_peg2, nullptr);

    if (split == 1 || trial_move_count < min_move_count) {
      min_move_count = trial_move_count;
      best_split = split;
    }
  }

  if (moves != nullptr) {
    min_moves_four_pegs(best_split, src_peg, aux_peg1, dest_peg, aux_peg2,
                        moves);
    min_moves_three_pegs(disk_count - best_split, src_peg, dest_peg, aux_peg2,
                         moves);
    min_moves_four_pegs(best_split, aux_peg1, dest_peg, src_peg, aux_peg2,
                        moves);
  }

  return min_move_count;
}

The first loop only counts: moves is nullptr. Then, if you want the actual sequence, replay the winning split.

From writing down this recurrence for the optimal number of moves, to a proof, took decades. The proof is Bousch [1]. Maybe some day I will be able to read it.

Discrete math is often like that. Change one parameter — three pegs to four — and the whole problem changes. Nature and hardness both.

Five pegs I am not ready for. Four took until 2014. For five or more, whether this kind of recurrence is actually optimal is still open [2].

References

[1] T. Bousch, La quatrième tour de Hanoï, Bull. Belg. Math. Soc. Simon Stevin 21 (2014), no. 5, 895–912. https://doi.org/10.36045/bbms/1420071861

[2] C. Grosu, A new lower bound for the Towers of Hanoi problem, Electron. J. Combin. 23 (2016), no. 1, Paper 1.22. https://doi.org/10.37236/5503