Solving the Towers of Hanoi at compile-time

Question

I am trying to solve the Towers of Hanoi at compile-time, but I have discovered a problem:

template<int src, int dst>
struct move_disc
{
    // member access will print src and dst
};

template<int n, int src, int tmp, int dst>
struct hanoi
{
    hanoi<n-1, src, dst, tmp> before;
    typename move_disc<src, dst>::lol disc;
    hanoi<n-1, tmp, src, dst> after;
};

template<int src, int tmp, int dst>
struct hanoi<0, src, tmp, dst>
{
    // recursive base case
};

hanoi<3, 1, 2, 3> go;

Unfortunately, the above meta program only prints six moves instead of seven:

prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 3>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 2>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<3, 2>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 3>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<2, 1>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<2, 3>’

The final move from 1 to 3 is missing. Why is that? Can the problem be solved?

Answer 1

I think that's because hanoi<1, 1, 2, 3> has already been instantiated (giving the first error) and is not instantiated again when later "encountered" during template instantiation.

[Edit: To make it maybe clearer, here's a "graph" of recursive template instantiations (with errors):

• hanoi<3, 1, 2, 3>:
  • 1: hanoi<2, 1, 3, 2>:
    • 1.1: hanoi<1, 1, 2, 3>:
      • 1.1.1: hanoi<0, 1, 3, 2>.
      • (move_disc<1, 3>)
      • 1.1.2: hanoi<0, 2, 1, 3>.
    • (move_disc<1, 2>)
    • 1.2: hanoi<1, 3, 1, 2>:
      • 1.2.1: hanoi<0, 3, 2, 1>.
      • (move_disc<3, 2>)
      • 1.2.2: hanoi<0, 1, 3, 2>.
  • (move_disc<1, 3>)
  • 2: hanoi<2, 2, 1, 3>:
    • 2.1: hanoi<1, 2, 3, 1>:
      • 2.1.1: hanoi<0, 2, 1, 3>.
      • (move_disc<2, 1>)
      • 2.1.2: hanoi<0, 3, 2, 1>.
    • (move_disc<2, 3>)
    • 2.2: hanoi<1, 1, 2, 3>: already instantiated at 1.1 (move_disc<1, 3> error not repeated).

-- end edit.]

A "fix" I can think of is to make every specialization unique, e.g. by adding an "id" template parameter (and generate unique new values during recursive instantiation):

template<int n, int src, int tmp, int dst, int id>
struct hanoi
{
    hanoi<n-1, src, dst, tmp, id*2> before;
    typename move_disc<src, dst>::lol disc;
    hanoi<n-1, tmp, src, dst, id*2+1> after;
};

template<int src, int tmp, int dst, int id>
struct hanoi<0, src, tmp, dst, id>
{
    // recursive base case
};

hanoi<3, 1, 2, 3, 1> go;

Live: http://ideone.com/0lQaXs