Cheap and Secure Web Hosting Provider : See Now

[Solved]: Rubik Cube Algorithm for general n

, , No Comments
Problem Detail: 

I am not sure if this is the right place , but:

Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots \times n$ ($d$ times) rubic cube , is there an algorithm that works effiecently for this case?(of course now it depends also on $d$ and not just on $n$)

I haven't found anything online/on wikipedia and I was just wondering.

Asked By : UserB95

Answered By : Tom van der Zanden

Algorithms for Solving Rubik's Cubes by Demaine et al. shows that an $n\times n\times n$ Rubik's Cube can be solved in $O(\frac{n}{\log n})$ moves and this is (asymptotically) optimal.

I am not certain on the complexity of actually computing such a solution but I suspect that (by closely following the steps in the proof) it can be done in polynomial time (probably $O(n^2)$ or $O(n^2\log n)$).

There likely isn't anything out there on higher-dimensional cubes. If there was, they would certainly have cited the Demaine paper. There is a trivial way to solve a $n\times n\times n$, since there exist move sequences that solve an individual cubie in $O(1)$ time. Therefore, if such sequences also exist for higher-dimensional cubes, they could be solved in $O(n^{d-1})$ steps since that is how many cubies are on the surface. And perhaps by extending Demaine's technique you could get that down to $O(\frac{n^{d-1}}{\log n})$ by solving multiple ($O(\log n)$) cubies in one go.

You might be able to find more information here: http://www.superliminal.com/cube/solution/solution.htm

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39846

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback