

Title: 4Peg Tower of Hanoi Post by Barukh on Nov 9^{th}, 2003, 4:47am Propose an efficient algorithm for Tower of Hanoi puzzle with 4 pegs and n disks. P.S. Is it true that the classical 3Peg version is not on the site? 

Title: Re: 4Peg Tower of Hanoi Post by william wu on Nov 9^{th}, 2003, 7:15pm hmm, apparently it is true, although i mention the answer (without explanation) to 3 peg tower of hanoi in a different thread 

Title: Re: 4Peg Tower of Hanoi Post by Eigenray on Nov 9^{th}, 2003, 10:49pm I've got something that's O(b^{n}) for any b>1. I can't really bound it any better than that:[hide] T(n) = min_{0<k<n} 2T(k)+2^{nk}1. The optimal value of k is approximately nsqrt(2n), according to Excel[/hide]. 

Title: Re: 4Peg Tower of Hanoi Post by Barukh on Nov 11^{th}, 2003, 2:40am on 11/09/03 at 22:49:14, Eigenray wrote:
Is b the number of pegs? Also, could you elaborate on the transformation algorithm (although I believe I got some hints on it from your recursive formula)? 

Title: Re: 4Peg Tower of Hanoi Post by Eigenray on Nov 11^{th}, 2003, 1:55pm b is any number greater than 1; i.e., it grows slower than any exponential. For any m, T(n) is O(2^{n/m}), because if n is large enough, take k ~ n(11/m), then T(n) [le] 2T(n(11/m)) + 2^{n/m}  1 < 2C 2^{n(11/m)/m} + 2^{n/m} < C 2^{n/m  n/m^2+1} + 2^{n/m} < C 2^{n/m} As for the algorithm, first [hide]transfer k disks to the last peg using all 4 pegs in T(k) time, then transfer the remaining nk using the first three pegs in 2^{nk}1 time, and then transfer the k disks back on top in T(k) again[/hide]. It appears lg T ~ sqrt(2n) + 2/3 lg n  1. 

Title: Re: 4Peg Tower of Hanoi Post by Barukh on Nov 14^{th}, 2003, 3:25am The algorithm proposed by Eigenray is conjectured to be the optimal for any number of pegs > 3, and is known as FrameStewart conjecture. In 1999, it was verified that for 4pegs this approach agrees with the optimal solution up to 17 disks. 

Title: Re: 4Peg Tower of Hanoi Post by algo.guru4all on Jul 6^{th}, 2008, 3:31am public class TowerOfHanoi { static int nDisks = 6; static int count=0; public static void main (String[] args) { doTowers(nDisks, 'A', 'B', 'C'); System.out.println(count); } public static void doTowers(int topN,char from, char inter, char to) { count++; if(topN==1) System.out.println("Disk 1 from " + from + " to "+to); else { doTowers(topN1, from, to, inter); // from>inter System.out.println("Disk " + topN + " from " + from + " to "+ to); doTowers(topN1, inter, from, to); // inter>to } } // } 

Title: Re: 4Peg Tower of Hanoi Post by towr on Jul 6^{th}, 2008, 6:57am on 07/06/08 at 03:31:30, algo.guru4all wrote:
Also reviving 5 year old dead topics is bad form. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 