Towers of Hanoi with K pegs

Question

The Towers of Hanoi problem is a classic problem for recursion. You are given 3 pegs with disks on one of them, and you must move all the disks from one peg to another, by following the given rules. You must also do this with the minimum number of moves.

Here's a recursive algorithm that solves the problem:

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

Now, imagine the same problem, only with 4 pegs, so we add another intermediary peg. When faced with the problem of having to choose which intermediary peg to choose at any one point, we will choose the leftmost one, in case more than 1 is free.

I have the following recursive algorithm for this problem:

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

Now, my question is how would I generalize this recursive approach to work for K pegs? The recursive function would receive a char[] which would hold the labels of each stack, so the function would look something like this:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

I know about the Frame-Stewart algorithm, which is most likely optimal but not proven, and which gives you the number of moves. However, I am interested in a strictly recursive solution that follows the pattern of the recursive solutions for 3 and 4 pegs, meaning it prints the actual moves.

For me at least, the pseudocode of the Frame-Stewart algorithm presented on Wikipedia is rather abstract, and I haven't been successful at translating it into code that prints the moves. I would accept a reference implementation of that (for random k), or even more detailed pseudocode.

I tried to come up with some sort of algorithm that permutes the labels array accordingly, but I've had no luck getting it to work. Any suggestions are appreciated.

Update:

This seems to be a lot easier to solve in a functional language. Here's an F# implementation based on LarsH's Haskell solution:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty        
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)    
        | p1::p2::p3::rest when not rest.IsEmpty    
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

And without treating 3 pegs as an edge case:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest     
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2) 
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

Note that this does not handle degenerate cases for which there is no solution, such as HanoiK 2 [1; 2]

user_371753 · Answer

Hinze, Ralf. Functional Pearl: La Tour D'Hanoi, http://www.comlab.ox.ac.uk/ralf.hinze/publications/ICFP09.pdf

This pearl aims to demonstrate the ideas of wholemeal and projective programming using the Towers of Hanoi puzzle as a running example. The puzzle has its own beauty, which we hope to expose along the way.

user_2535251 · Answer

I would like to contribute with what I believe is the optimal k in the Frame-Stewart algorithm. The algorithm itself is not defined for cases where Towers of Hanoi cannot be solved.

frameStewart :: Integer -> Integer -> Integer
frameStewart d c
  | c <= 2    = error "must have more than two pegs"
  | c == 3    = 2^d-1
  | d <  c    = 2*d-1
  | otherwise = frameStewart k c + frameStewart (d-k) (c-1) + frameStewart k c
    where
      k = solve $ div (4*d-2*c) c
        where
          solve a
            | a*2*d-a*a <= d^2-2*a = a
            | otherwise  = solve (a-1)

The wikipedia page shows that n disks minus the square root of 2*n + 1, within special brackets to find the nearest integer, + 1 is equal to k. I found it useful to break free of those brackets by considering d = 4 (d for disks) and k = 2, and manipulated the formula until I arrived at the inequality that is present in the code. That alone solves the problem with 4 pegs.

The final step was to figure out which value to solve that inequality with, and considered it to be 4*d-2*c (c for pegs or "cavilhas" in my language) divided by the number of pegs c. I think that its results match the tables for 4 pegs in Ben Houston's research, which are present here.

This does not give you a list of moves, however, only the minimum number of them.

Towers of Hanoi with K pegs

7 Answers