Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

N cubes placed side by side like the above picture. I have to Correct vertex numbering is shown in picture. From left to right, every face is numbered in counter-clockwise order. So first face has number 1-2-3-4, second face 5-6-7-8 and so on. So if N cubes are placed then, there are 4*(N+1) numbers (1 to 4N + 4).

Now initially the numbers are placed in random order. I have to make them correct order. To bring them in correct order, I can only swap 1 and an adjacent number of 1

enter image description here For example, in the above diagram, we can swap (1, 8) and then (1, 5) to bring it into correct form.

Given, N-1(<=40) at input and number currently at 1, number currently at 2, … number currently at 4*N. I have to find out minimum number of moves

So if I have given the following input :

5 2 3 4 8 6 7 1

I have to output 2 .

I have tried several times to solve this problem but failed . Guyz , can you help me in this regard ?

share|improve this question
    
You need $1,2,3,4$ to be in the leftmost plane in any order, then $5,6,7,8$ in the next one, and so on? –  Ross Millikan May 3 '13 at 4:56
    
In your example, it looks like you should delete the first $8$ in the input. –  Ross Millikan May 3 '13 at 5:11
    
I have edited my question –  Way to infinity May 3 '13 at 5:15
add comment

1 Answer

up vote 1 down vote accepted

This is essentially a sliding block puzzle, like the 15 puzzle or the minus cube (which is exactly the $N=1$ version of this question). Think of the number $1$ as an empty space, which other numbers take turns filling.

Unfortunately for you, although algorithms to solve larger versions of the 15-puzzle are plentiful, finding the shortest solution is NP-hard, and this is likely to be the same. I don't know about the minus cube, that one might be small enough to go through the entire search tree.

share|improve this answer
    
I'm not sure. If the question is as I indicate in my comment to OP, it seems a greedy algorithm will work. But I don't think we know yet what a solution is. –  Ross Millikan May 3 '13 at 5:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.