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]