// Type to simulate the steps required to solve the Tower of Hanoi puzzle for N disks.
// `From`, `To`, and `Intermediate` represent the three rods involved.
type Hanoi<N extends number, From = 'A', To = 'B', Intermediate = 'C'>
  = N extends 0 ? []  // Base case: no moves needed for zero disks.
  : [
    ...Hanoi<MinusOne<N>, From, Intermediate, To>,
    [From, To],
    ...Hanoi<MinusOne<N>, Intermediate, To, From>,
  ]

type MinusOne<S extends number>
  = `${S}` extends `${infer L extends number}0` ? L extends 1 ? 9 : `${MinusOne<L>}9` extends `${infer N extends number}` ? N : never
  : ReturnType<<Digits extends [never, 0, 1, 2, 3, 4, 5, 6, 7, 8]>() => {[D in keyof Digits]
    : `${S}` extends `${infer L}${D}` ? `${L}${Digits[D]}` extends `${infer N extends number}` ? N : never
    : never
    }[any]>

Playground

Solution by teamchong #32993

type Hanoi<
  N extends number,
  From = "A",
  To = "B",
  Intermediate = "C"
> = HanoiByArr<NumToArr<N>, From, To, Intermediate>;

type HanoiByArr<
  Count extends any[],
  From = "A",
  To = "B",
  Intermediate = "C"
> = Count extends [infer _, ...infer R]
  ? [
      ...HanoiByArr<R, From, Intermediate, To>,
      [From, To],
      ...HanoiByArr<R, Intermediate, To, From>
    ]
  : [];

type NumToArr<N extends number, Count extends any[] = []> = number extends N
  ? []
  : N extends Count["length"]
  ? Count
  : NumToArr<N, [...Count, 1]>;

Solution by Vampirelee #32596

type Hanoi<
  N extends number,
  From = "A",
  To = "B",
  Intermediate = "C",
  C extends 0[] = [0]
> = N extends 0
  ? []
  : C["length"] extends N
  ? [[From, To]]
  : [
      ...Hanoi<N, From, Intermediate, To, [...C, 0]>,
      [From, To],
      ...Hanoi<N, Intermediate, To, From, [...C, 0]>
    ];

Solution by vangie #32212

type MakeNumberToArray<T extends number, U extends unknown[] = []> = U['length'] extends T
  ? U
  : MakeNumberToArray<T, [...U, unknown]>;

type Hanoi<
  N extends number,
  From = 'A',
  To = 'B',
  Intermediate = 'C',
  U extends unknown[] = MakeNumberToArray<N>,
> = U['length'] extends 1
  ? [[From, To]]
  : U extends [unknown, ...infer Rest]
  ? [...Hanoi<Rest['length'], From, Intermediate, To>, [From, To], ...Hanoi<Rest['length'], Intermediate, To, From>]
  : [];

Solution by leejaehyup #30993

type Hanoi<Rings extends number, FromRod extends string = 'A', ToRod extends string = 'B', IntermediateRod extends string = 'C', Acc extends '🇺🇦'[] = []> = Acc['length'] extends Rings ? [] : [ ...Hanoi<Rings, FromRod, IntermediateRod, ToRod, [...Acc, '🇺🇦']>, [FromRod, ToRod], ...Hanoi<Rings, IntermediateRod, ToRod, FromRod, [...Acc, '🇺🇦']> ]

/* We should move disk from rod-A to rod-B using rod-C as a intemediate helper rod. Only one disk at a time. So, I explain on Hanoi<1> example. By default Acc is empty array and it's length 0, so we skip true branch of our comparison and go to false branch.

1. We should get an array of arrays (combination of A | B | C). So, wrap false branch with [].
2. First recursive spread. 2.1 We run "Hanoi" type with Hanoi<1, 'A', 'C', 'B', [...[], '🇺🇦']>.
   • Here we should take a look on number of rings and length of Acc.
   • We have Rings = 1 and Acc with one '🇺🇦'. So, result gonna be an empty [] with length 1.
   • That's why we use spread operator. When we spread an empty array we get 'never' type and it skiped in our RESULT ARRAY. 2.2 Just an array with ['A', 'B'] 2.3 The same explanation as in a 2.1. */

Solution by ArtDorfman #30769

type Hanoi<N extends number, From = 'A', To = 'B', Intermediate = 'C'> = Helper<N, [], From, To, Intermediate>
type Helper<N extends number, C extends 1[], From extends unknown, To extends unknown, Intermediate extends unknown> = C['length'] extends N
  ? []
  : [...Helper<N, [...C, 1], From, Intermediate, To>, [From, To], ...Helper<N, [...C, 1], Intermediate, To, From>]

Solution by Sun79 #30479