Author 
Topic: 4Peg Tower of Hanoi (Read 6272 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


4Peg Tower of Hanoi
« on: Nov 9^{th}, 2003, 4:47am » 
Quote Modify

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?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: 4Peg Tower of Hanoi
« Reply #2 on: Nov 9^{th}, 2003, 10:49pm » 
Quote Modify

I've got something that's O(b^{n}) for any b>1. I can't really bound it any better than that: T(n) = min_{0<k<n} 2T(k)+2^{nk}1. The optimal value of k is approximately nsqrt(2n), according to Excel.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 4Peg Tower of Hanoi
« Reply #3 on: Nov 11^{th}, 2003, 2:40am » 
Quote Modify

on Nov 9^{th}, 2003, 10:49pm, Eigenray wrote:I've got something that's O(b^{n}) for any b>1. 
 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)?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: 4Peg Tower of Hanoi
« Reply #4 on: Nov 11^{th}, 2003, 1:55pm » 
Quote Modify

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 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. It appears lg T ~ sqrt(2n) + 2/3 lg n  1.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 4Peg Tower of Hanoi
« Reply #5 on: Nov 14^{th}, 2003, 3:25am » 
Quote Modify

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.


IP Logged 



algo.guru4all
Newbie
Posts: 1


Re: 4Peg Tower of Hanoi
« Reply #6 on: Jul 6^{th}, 2008, 3:31am » 
Quote Modify

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 } } // }


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13610


Re: 4Peg Tower of Hanoi
« Reply #7 on: Jul 6^{th}, 2008, 6:57am » 
Quote Modify

on Jul 6^{th}, 2008, 3:31am, algo.guru4all wrote:That's for three pegs, and not for four as it was in the problem statement. Also reviving 5 year old dead topics is bad form.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



