wu :: forums - Print Page


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

        riddles >> medium >> Rubik's Cube without seeing
        
(Message started by: codpro880 on Jan 3^rd, 2009, 6:35pm)

Title: Rubik's Cube without seeing
Post by codpro880 on Jan 3^rd, 2009, 6:35pm

Is it possible to solve a rubik's cube without looking at it?

By not looking at it I mean without seeing it at all, hence you're blindfolded BEFORE you look at it (people can easily solve them blindfolded if they look at them first).

If it's not possible for a 3x3, could it be possible for a 2x2?

It it is possible, how?

If it's not, why?

Title: Re: Rubik's Cube without seeing
Post by SMQ on Jan 3^rd, 2009, 7:53pm

With the addition of someone to tell you when you've solved it, I'm sure it's possible, but it's probably not practical. That is, I'm sure there is a sequence of moves which will cycle through all possible permutations of the cube, such that at some point in the sequence it must be solved. However, the number of permutations for the 3-cube is high enough that no human could cycle through all of them in a lifetime... I'm not sure about the 2-cube.

Without someone to tell you when you've solved it, no, it's not possible. Given two distinct starting configurations, performing the same sequence of moves on each will always give distinct ending configurations, so there is no "magic" sequence of moves, however long, which will end with the cube solved regardless of the starting configuration.

--SMQ

Title: Re: Rubik's Cube without seeing
Post by Eigenray on Jan 3^rd, 2009, 8:09pm

If the cube is solved on any given move, there's a unique possibility for the starting configuration. Since there are over 43 quintillion possible starting points, it is possible only in theory. One way is to make a list of all possible sequences of at most 22 moves. Then apply the first sequence, undo it, then apply the second, undo it, etc. Eventually the cube will be solved. But I'm sure there's a better way.

For a 2x2 cube there are "only" 3674160 possible configurations so at one move a second you're looking at a minimum of over 42 days.

Reversing things, you are trying to find the shortest sequence of moves such that if you make these moves simultaneously from all 24 solved positions you'll reach every position~~; I don't think you can identify rotations because the edge labels will be different~~. So it's ~~similar to~~ the metric traveling salesman problem for the Cayley graph. It's conjectured that Cayley graphs are Hamiltonian, but it's still an open problem whether this is true for the 3x3 Rubik's cube ([link=http://www.usna.edu/Users/math/wdj/book/node187.html]source[/link]).

You might find the recently proved [link=http://en.wikipedia.org/wiki/Road_coloring_problem]road coloring theorem[/link] interesting, even though it doesn't really apply here.

Title: Re: Rubik's Cube without seeing
Post by Hippo on Jan 4^th, 2009, 2:53am

OK, without feedback you cannot be sure to end with solved cube.
If you can define several feedback types, it may became feasible.
(Feedback of type k faces are colored well, or edges/corners on k-faces are colored well will be very helpful).
Even the feedback a face is colored well is sufficient for 3 cube.
... You can find which one it is by careful turning edges on remaining faces. ...

Title: Re: Rubik's Cube without seeing
Post by Grimbal on Jan 4^th, 2009, 8:31am

on 01/03/09 at 18:35:52, codpro880 wrote:

By not looking at it I mean without seeing it at all, hence you're blindfolded BEFORE you look at it (people can easily solve them blindfolded if they look at them first).

Being blindfolded before you look at it looks a bit contradictory.
And while some people can solve it blindfolded after looking at it, I wouldn't say people in general can do it easily.

OK, just nitpicking.

Well, I second SMQ that without any feedback, it is impossible to solve it. That is, if nobody even tells you whether it is solved or not, you cannot pick up a scrambled cube and return it solved. Unless you are really lucky.

@Eigenray: I don't see why you should consider 24 starting or ending positions. Considering that the centers don't move, the problem is to bringing the remaining 20 pieces to the right position. And for that there is only one solved position.

I wonder if there are "braille" cubes for the blind.

Title: Re: Rubik's Cube without seeing
Post by Eigenray on Jan 4^th, 2009, 2:48pm

on 01/04/09 at 08:31:22, Grimbal wrote:

@Eigenray: I don't see why you should consider 24 starting or ending positions. Considering that the centers don't move, the problem is to bringing the remaining 20 pieces to the right position. And for that there is only one solved position.

What I meant was that the graph has 24 components, and you don't know which one you're in. Say X' denotes rotating the cube X about some axis. If turning the top face clockwise takes you from X to Y, to get from X' to Y' you have to turn a different face. So the path you travel will be different depending on the initial rotation: the generators are permuted. But you're right that it doesn't matter, because it is still equivalent to finding a sequence of generators and inverses such that 1, x₁, x₂x₁, x₃x₂x₁, ... contains every group element, so it is just a metric TSP on the Cayley graph.