*****This only works on 3 peg problems***** There has been no further advances yet on a proper solution. Both have not yet been proven correct, though they are generally assumed right. Two years later two separate (but later proven equal) algorithms were published by J. In 1939, the American Mathematical Monthly held a competition to solve for and m peg and n discs. It was quickly discovered that the 3 peg solution exists but none solved for a 4+ peg solution. The game ends when the whole stack of discs has been moved to another peg. The legend varies across several sites, but it's generally consistent.Ģ) No disc may be placed on a smaller discģ) Only the top disc may be removed and then placed at the top of another peg and it's discs (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. God (Brahma) placed 64 gold disks on one needle at the time of creation. 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. 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). The Towers of Hanoi puzzle was published to the westren world in 1883 by French mathematician Edouard Lucas, under the pen-name, N. 'Transfer the top k disks to the destination peg' (step 3) means transfer from the 'other peg' (p3) to p2.Thus 'without disturbing the peg that now contains the top k disks' (step 2) means to recurse using all the pegs except p3.Step 1, 'For some k, 1 All the remaining pegs are available as temporary storage, for the top-level hanoi problem. Thus the source peg is p1, and the destination peg is p2.We use this convention when recursing, to define the source, destination, and allowed storage of the divided-and-conquered subproblems. 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.In order to determine the moves, we annotate F-S's steps as follows: Where we concatenate the sequences of moves for steps 1, 2, and 3 of the Frame-Stewart algorithm. HanoiR k (p3 : (p2 : (p1 : rest))) - step 3 corresponds to T(k,r) HanoiR (n-k) (p1 : (p2 : rest)) ++ - step 2 corresponds to T(n-k, r-1) Really the essential piece is hanoiR k (p1 : (p3 : (p2 : rest))) ++ - step 1 corresponds to T(k,r) Here are a few more results: ghci> hanoiR 6 It's too late at night for me to verify more, without writing a simulator. I've verified the correctness of the answer for 4 disks and 4 pegs. I haven't tried to optimize k, though n/2 seemed like a good guess. But I may have silly mistakes so feedback is welcome.Īs you can see from the code, the heuristic for k is simply floor(n / 2). I'm pretty new to Haskell so I must admit I'm proud that this works. move the top disk from peg 1 to peg 2, then the top disk from peg 1 to peg 3, etc. You can name the 4 pegs whatever you want, e.g. run the Towers of Hanoi with 4 disks and 4 pegs.

n disks and r > 3 pegs: use Frame-Stewart algorithm n disks and 3 pegs - unneeded covered by (null rest) below. HanoiR 1 (p1 : p2 : rest) = - only needed for smart-alecks? one disk: one move and two pegs needed. 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 Note that this does not handle degenerate cases for which there is no solution, such as HanoiK 2 > let k = if rest.IsEmpty then n - 1 else int(n / 2) Hanoi3(nDisks - 1, source, dest, intermed) Īnd without treating 3 pegs as an edge case: let rec HanoiK n pegs = Here's a recursive algorithm that solves the problem: void Hanoi3(int nDisks, char source, char intermed, char dest) You must also do this with the minimum number of moves. 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. The Towers of Hanoi problem is a classic problem for recursion.

Hanoi towers codewars