Towers of Hanoi with K pegs

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 pseu开发者_如何学Pythondocode 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]

Here is an implementation in Haskell (update: took care of 3-peg case by making k = n-1 when r=3):

-- hanoi for n disks and r pegs [p1, p2, ..., pr]
hanoiR :: Int -> [a] -> [(a, a)]

-- zero disks: no moves needed.
hanoiR 0 _ = []

-- one disk: one move and two pegs needed.
hanoiR 1 (p1 : p2 : rest) = [(p1, p2)] -- only needed for smart-alecks?

{-
-- n disks and 3 pegs -- unneeded; covered by (null rest) below.
hanoiR n [p1, p2, p3] =
    hanoiR (n - 1) [p1, p3, p2] ++
    [(p1, p2)] ++
    hanoiR (n - 1) [p3, p2, p1]
-}

-- n disks and r > 3 pegs: use Frame-Stewart algorithm
hanoiR n (p1 : p2 : p3 : rest) =
    hanoiR k (p1 : p3 : p2 : rest) ++
    hanoiR (n - k) (p1 : p2 : rest) ++
    hanoiR k (p3 : p2 : p1 : rest)
    where k
        | null rest   = n - 1
        | otherwise   = n `quot` 2

So load this in GHCi and enter

hanoiR 4 [1, 2, 3, 4]

I.e. run the Towers of Hanoi with 4 disks and 4 pegs. You can name the 4 pegs whatever you want, e.g.

hanoiR 4 ['a', 'b', 'c', 'd']

The output:

[(1,2),(1,3),(2,3),(1,4),(1,2),(4,2),(3,1),(3,2),(1,2)]

I.e. move the top disk from peg 1 to peg 2, then the top disk from peg 1 to peg 3, etc.

I'm pretty new to Haskell so I must admit I'm proud that this works. But I may have silly mistakes so feedback is welcome.

As you can see from the code, the heuristic for k is simply floor(n / 2). I haven't tried to optimize k, though n/2 seemed like a good guess.

I've verified the correctness of the answer for 4 disks and 4 pegs. It's too late at night for me to verify more, without writing a simulator. (@_@) Here are a few more results:

ghci>  hanoiR 6 [1, 2, 3, 4, 5]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,4),(1,5),(1,2),
 (5,2),(4,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci>  hanoiR 6 [1, 2, 3, 4]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,2),(1,4),(2,4),(1,2),
 (4,1),(4,2),(1,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci>  hanoiR 8 [1, 2, 3, 4, 5]
[(1,3),(1,2),(3,2),(1,4),(1,3),(4,3),(2,1),(2,3),(1,3),(1,2),
 (1,4),(2,4),(1,5),(1,2),(5,2),(4,1),(4,2),(1,2),
 (3,2),(3,1),(2,1),(3,4),(3,2),(4,2),(1,3),(1,2),(3,2)]

Does this clarify the algorithm?

Really the essential piece is

hanoiR k (p1 : (p3 : (p2 : rest))) ++      -- step 1; corresponds to T(k,r)
hanoiR (n-k) (p1 : (p2 : rest)) ++         -- step 2; corresponds to T(n-k, r-1)
hanoiR k (p3 : (p2 : (p1 : rest)))         -- step 3; corresponds to T(k,r)

where we concatenate the sequences of moves for steps 1, 2, and 3 of the Frame-Stewart algorithm. In order to determine the moves, we annotate F-S's steps as follows:

• Conventionally, when hanoi is called, the goal is defined (without loss of generality) as transferring the disks from the first peg to the second peg, using all remaining pegs for temporary storage. We use this convention when recursing, to define the source, destination, and allowed storage of the divided-and-conquered subproblems.
• Thus the source peg is p1, and the destination peg is p2. All the remaining pegs are available as temporary storage, for the top-level hanoi problem.
• Step 1, "For some k, 1 <= k < n, transfer the top k disks to a single other peg": we choose p3 as "a single other peg".
• Thus "without disturbing the peg that now contains the top k disks" (step 2) means to recurse using all the pegs except p3. I.e. p1, p2, and the rest beyond p3.
• "Transfer the top k disks to the destination peg" (step 3) means transfer from the "other peg" (p3) to p2.

Does that make sense?

To solve the Towers of Hanoi, all you need to do is:

The Frame Stewart Algorithm isn't really that complex. Essentially, you have to move a certain number of the disks (for instance, half of them) to some peg: Treat these disks like their own, separate tower. It's easy to define the solution for 1 or 2 disks, and one you move the first half to its destination, you move the second half to the place it needs to end up.

You can continually segment it if you want to make it easier to write (the only special case becoming 1) but without a significant number of pegs, it won't work.

Additionally, if k >= 3, you can solve it exactly like a 3 peg towers of Hanoi by simply ignoring the rest of the pegs, although that would not be optimal.

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.

Facebook k-peg N discs tower of hanoi can be solved via BFS algorithms. For solution visit http://www.woolor.com/InterviewMitra/41/facebook-k-peg-of-tower-of-hanoi-solution

The Towers of Hanoi puzzle was published to the westren world in 1883 by French mathematician Edouard Lucas, under the pen-name, N. Lucas de Siam. The "legend" which accompanied the game stated that in Benares, during the reign of the Emperor Fo Hi, there was a Indian temple with a dome which marked the center of the world (Kashi Vishwanath). Within the dome, (Brahmin) priests moved golden disks between 3 diamond needlepoints (worn posts), a cubit high and as thick as the body of a bee. God (Brahma) placed 64 gold disks on one needle at the time of creation. (The discs were moved according to the immutable laws from Brahma to transferring them from one peg to another) It was said that when they completed their task, the universe would come to an end. The legend varies across several sites, but it's generally consistent. The 'laws' set by Brahma is as such: 1) Only 1 disc at a time can be moved 2) No disc may be placed on a smaller disc 3) Only the top disc may be removed and then placed at the top of another peg and it's discs The game ends when the whole stack of discs has been moved to another peg. It was quickly discovered that the 3 peg solution exists but none solved for a 4+ peg solution. In 1939, the American Mathematical Monthly held a competition to solve for and m peg and n discs. Two years later two separate (but later proven equal) algorithms were published by J. S. Frame and B. M. Stewart. Both have not yet been proven correct, though they are generally assumed right. There has been no further advances yet on a proper solution. *****This only works on 3 peg problems***** The minimum number of moves for a tower of n disks was quickly shown to be 2n− 1, with the simple recursive solution as follows: Label the three pegs start, goal, and temp. To move n pegs from the start peg to the goal peg via the temp peg: For n > 1, (i) Recursively move the top n−1 disks from start to temp via goal. (ii) Move the nth disk from start to goal. (iii) Recursively move the n−1 disks from temp to goal via start. This solution takes 2n−1 moves: (1) If n = 1, f(n) = 1 = 2n−1 (2) If n > 1, f(n) = 2 ∗ (2n−1−1)+1 = 2n−2+1 = 2n−1 The easy way to solve it... 1,3,7,15,31 are the solutions to the first few n discs. Recursively that resembles nk=2nk-1+1. From there we can induce that n=2n-1. Proving by induction I leave to you. *****the basic Frame/Stewart algorithm***** For m peg and n discs, chose an l such that 0 ≤ l < n (whereas l is an integer that minimizes the steps in the following setup)... • Move the top l discs from the start peg to an intermediate peg; this can be accomplished in Hk(l) moves (since the bottom n−l disks do not interfere with movements at all). • Move the bottom n − l disks from the start peg to the goal peg using Hk−1(n−l) moves. (Since one peg is occupied by a tower of smaller disks, it cannot be used in this stage.) • Move the original l disks from the intermediate peg to the goal peg in Hk(l) moves. So essentially it is Hk(n)= 2Hk(l) + Hk-1(n-1) ----->the l minimized *****Easy as pie!! Not!***** Verifying it works against our 3 peg solution should be easy. Using k=2; we set H2(0)=0, H2(1)=1, and H2(n>1)=∞. For k=3, we can set l=n-1. (It causes our H2(n-1) to become finite) That will permit us to write H3(n)=2H3(n-1)+H2(1) which equals 2n−1. It is a bit of a play on words, but it works. *****A slightly different description to help clarify***** The Frame–Stewart algorithm, giving a presumably optimal solution for four (or even more) pegs, is described below: Define H(n,m)to be the minimum number of moves required to transfer n disks using m pegs The algorithm can be described recursively: 1. For some l, 1

`Option VBASupport 1
Option Explicit
Dim n as double
dim m as double
dim l as double
dim rx as double
dim rxtra as double
dim r as double
dim x as double
dim s1 as double
dim s2 as double
dim i as integer
dim a ()
dim b ()
dim c ()
dim d ()
dim aa as double
dim bb as double
dim cc as double
dim dd as double
dim total as double

Sub Hanoi
on error goto errorhandler

m=inputbox ("m# pegs=??")
n=inputbox ("n# discs=??")
x=-1
l=m-1
rx=1
s1=0
s2=0
aa=0

while n>rx
        x=x+1
        r=(l+x)/(x+1)
        rx=r*rx
wend
rx=1
for i=0 to x-1
        r=(l+i)/(i+1)
        rx=r*rx
        redim a (-1 to x)
        redim b (-1 to x)
        redim c (-1 to x)
        redim d (-1 to x)
            a(i)=rx
            b(i)=i
            bb=b(i)
            c(i)=rx-aa
            aa=a(i)
            cc=c(i)
            d(i)=cc*2^bb
            dd=d(i)
            s1=s1+dd
next

rxtra=n-aa
s2=rxtra*2^(bb+1)
total = 2*(s1+s2)-1
msgbox total

exit sub
errorhandler: msgbox "dang it!!"
'1, 3, 5, 9, 13, 17, 25, 33 first 8 answers for 4 peg
'16=161,25=577,32=1281,64=18433
End Sub`

Disclosure: These sources were used to confirm answers and for some history of the problem. It's hard to give exact credit where's it's due because multiple sites were used to verify... so they are all the sources for many parts of the history.

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.

http://tristan-interview.blogspot.com/2012/02/n-disks-and-k-pegs-extension-problem-of.html