wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 4-Peg Tower of Hanoi
        
(Message started by: Barukh on Nov 9^th, 2003, 4:47am)

Title: 4-Peg 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 3-Peg version is not on the site?

Title: Re: 4-Peg 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: 4-Peg Tower of Hanoi
Post by Eigenray on Nov 9^th, 2003, 10:49pm

I've got something that's O(bⁿ) for any b>1. I can't really bound it any better than that:[hide]
T(n) = min_0<k<n 2T(k)+2^n-k-1.
The optimal value of k is approximately n-sqrt(2n), according to Excel[/hide].

Title: Re: 4-Peg Tower of Hanoi
Post by Barukh on Nov 11^th, 2003, 2:40am

on 11/09/03 at 22:49:14, Eigenray wrote:

I've got something that's O(bⁿ) 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)?

Title: Re: 4-Peg 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(1-1/m), then
T(n) [le] 2T(n(1-1/m)) + 2^n/m - 1
< 2C 2^n(1-1/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 n-k using the first three pegs in 2^n-k-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: 4-Peg 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 Frame-Stewart conjecture.

In 1999, it was verified that for 4-pegs this approach agrees with the optimal solution up to 17 disks.

Title: Re: 4-Peg 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(topN-1, from, to, inter); // from-->inter
System.out.println("Disk " + topN +
" from " + from + " to "+ to);
doTowers(topN-1, inter, from, to); // inter-->to
}
}
//----------------------------------------------------------

}

Title: Re: 4-Peg Tower of Hanoi
Post by towr on Jul 6^th, 2008, 6:57am

on 07/06/08 at 03:31:30, 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.