wu :: forums
wu :: forums - 4-Peg Tower of Hanoi

Welcome, Guest. Please Login or Register.
Sep 23rd, 2018, 9:24am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, Grimbal, SMQ, Eigenray, towr, william wu, Icarus)
   4-Peg Tower of Hanoi
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 4-Peg Tower of Hanoi  (Read 6313 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
4-Peg Tower of Hanoi  
« on: Nov 9th, 2003, 4:47am »
Quote Quote Modify Modify

Propose an efficient algorithm for Tower of Hanoi puzzle with 4 pegs and n disks.
 
P.S. Is it true that the classical 3-Peg version is not on the site?
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: 4-Peg Tower of Hanoi  
« Reply #1 on: Nov 9th, 2003, 7:15pm »
Quote Quote Modify Modify

hmm, apparently it is true, although i mention the answer (without explanation) to 3 peg tower of hanoi in a different thread
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: 4-Peg Tower of Hanoi  
« Reply #2 on: Nov 9th, 2003, 10:49pm »
Quote Quote Modify Modify

I've got something that's O(bn) for any b>1.  I can't really bound it any better than that:
T(n) = min0<k<n 2T(k)+2n-k-1.
The optimal value of k is approximately n-sqrt(2n), according to Excel
.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: 4-Peg Tower of Hanoi  
« Reply #3 on: Nov 11th, 2003, 2:40am »
Quote Quote Modify Modify

on Nov 9th, 2003, 10:49pm, Eigenray wrote:
I've got something that's O(bn) 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: male
Posts: 1948
Re: 4-Peg Tower of Hanoi  
« Reply #4 on: Nov 11th, 2003, 1:55pm »
Quote Quote Modify Modify

b is any number greater than 1; i.e., it grows slower than any exponential.
For any m, T(n) is O(2n/m), because if n is large enough, take k ~ n(1-1/m), then
T(n) [le] 2T(n(1-1/m)) + 2n/m - 1
< 2C 2n(1-1/m)/m + 2n/m
< C 2n/m - n/m^2+1 + 2n/m
< C 2n/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 n-k using the first three pegs in 2n-k-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: male
Posts: 2276
Re: 4-Peg Tower of Hanoi  
« Reply #5 on: Nov 14th, 2003, 3:25am »
Quote Quote Modify Modify

The algorithm proposed by Eigenray is conjectured to be the optimal for any number of pegs > 3, and is known as Frame-Stewart conjecture.  
 
In 1999, it was verified that for 4-pegs this approach agrees with the optimal solution up to 17 disks.
IP Logged
algo.guru4all
Newbie
*





   


Posts: 1
Re: 4-Peg Tower of Hanoi  
« Reply #6 on: Jul 6th, 2008, 3:31am »
Quote Quote Modify 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(topN-1, from, to, inter); // from-->inter
System.out.println("Disk " + topN +
" from " + from + " to "+ to);
doTowers(topN-1, inter, from, to); // inter-->to
}
}
//----------------------------------------------------------
 
}
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: 4-Peg Tower of Hanoi  
« Reply #7 on: Jul 6th, 2008, 6:57am »
Quote Quote Modify Modify

on Jul 6th, 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board