wu :: forums - Print Page


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

        riddles >> cs >> Generalized tower of hanoi with optimal solution
        
(Message started by: getafix78 on Jan 19^th, 2012, 7:04pm)

Title: Generalized tower of hanoi with optimal solution
Post by getafix78 on Jan 19^th, 2012, 7:04pm

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg..
At anypoint of time, the decreasing radius property of all the pegs must be maintained..

Constraints:
1<= N<=8
3<= K<=5

Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.

Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

Sample Input #00:

2 3
1 1
2 2

Sample Output #00:

3
1 3
1 2
3 2

Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1

Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1

Title: Re: Generalized tower of hanoi with optimal soluti
Post by birbal on Jan 22^nd, 2012, 7:14am

for k = 3, moves = 2^n -1;
for k = 4,5 looks like its still an open problem :/

Title: Re: Generalized tower of hanoi with optimal soluti
Post by getafix78 on Jan 22^nd, 2012, 8:47pm

I think solutions exist for k=4 and 5 as well. Shouldnt it be easier to solve the problem with more pegs? As in, in the regular tower of hanoi problem, the number of moves needed reduces as the number of pegs increase

Title: Re: Generalized tower of hanoi with optimal soluti
Post by towr on Jan 22^nd, 2012, 10:09pm

Yeah, it becomes easier to solve the problem with more pegs, but it may be harder to find the optimal number of moves.

Title: Re: Generalized tower of hanoi with optimal soluti
Post by getafix78 on Jan 27^th, 2012, 10:06pm

I found this problem as a facebook programming challenge question, so I assume there does exist a reasonably efficient way to solve this, but I am stumbled by this so far.

Title: Re: Generalized tower of hanoi with optimal soluti
Post by towr on Jan 28^th, 2012, 11:59am

Well, you could try the frame-stewart algorithm (http://en.wikipedia.org/wiki/Tower_of_Hanoi#Frame.E2.80.93Stewart_algorithm), but there is no proof that it gives the optimal solution (though there are no counterexamples known at the moment, unless wikipedia is out of date).
The algorithms that are known to give optimal solution tend not to be so efficient.

Title: Re: Generalized tower of hanoi with optimal soluti
Post by arun gupta on Mar 22^nd, 2012, 10:11pm

i rememberd tower of hanoi is one of the popular topic in my semester when i was studying computer science in amritsar and i had to travel by cab daily :)