Author |
Topic: Generalized tower of hanoi with optimal solution (Read 5567 times) |
|
getafix78
Newbie
Posts: 3
|
 |
Generalized tower of hanoi with optimal solution
« on: Jan 19th, 2012, 7:04pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
birbal
Full Member
Gender: 
Posts: 250
|
|
Re: Generalized tower of hanoi with optimal soluti
« Reply #1 on: Jan 22nd, 2012, 7:14am » |
Quote Modify
|
for k = 3, moves = 2^n -1;
for k = 4,5 looks like its still an open problem :/
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
getafix78
Newbie
Posts: 3
|
|
Re: Generalized tower of hanoi with optimal soluti
« Reply #2 on: Jan 22nd, 2012, 8:47pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Generalized tower of hanoi with optimal soluti
« Reply #3 on: Jan 22nd, 2012, 10:09pm » |
Quote Modify
|
Yeah, it becomes easier to solve the problem with more pegs, but it may be harder to find the optimal number of moves.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
getafix78
Newbie
Posts: 3
|
|
Re: Generalized tower of hanoi with optimal soluti
« Reply #4 on: Jan 27th, 2012, 10:06pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Generalized tower of hanoi with optimal soluti
« Reply #5 on: Jan 28th, 2012, 11:59am » |
Quote Modify
|
Well, you could try the frame-stewart 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
arun gupta
Newbie
hello friends :)
Gender:
Posts: 19
|
|
Re: Generalized tower of hanoi with optimal soluti
« Reply #6 on: Mar 22nd, 2012, 10:11pm » |
Quote Modify
|
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 
|
| « Last Edit: Mar 22nd, 2012, 11:43pm by arun gupta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print