http://www.bbc.co.uk/news/technology-10929159
So this implies you can't mess-up the order (entropy?) more (from an ordered cube) in more than 20 moves... and, that one or two more moves from the most-confused state is re-fixable in less than 21 moves?
That sounds right. In other words, the furthest distance from the solved state is 20 moves. Any move from such a state will only change the cube to a state of 19 moves away from the solution ( or possibly remain 20 moves from the solution).
ReplyDeleteSo it means one more move (any move) would improve the situation....
ReplyDeleteInteresting. Does this computer cranking constitute a rigorous mathematical proof?. When a professor of mathematics says "We now know for certain that the magic number is 20" it sets my alarm bells ringing - I would have thought that the word 'proof' might appear somewhere.
ReplyDeleteThat's my interpretation - but I'm including the possibility that a move might not make the situation worse (still 20 moves from solution).
ReplyDeleteCan you know something without providing a 'proof'? I think so. The Rubiks cube problem probably suits a Monte Carlo simulation rather than a paper proof.
ReplyDelete//
ReplyDeleteAs the exercise went on, he said, the probability of there being a combination which required more than 20 moves to solve "dropped into the very low digits".
//
So - no proof.
Sounds like a nice problem for someone's doctorate... Doesn't sound too impossible … start by calating every unique combination then calculate the number of moves to each of them …simples (sorry I hate that but couldn't resist) ... Being a cube of set number of colours (dur 6) there's bound to be lots of places to take advantage of symmetry eg every move of every slice could be clockwise/anticlockwise -each giving a pair of possible combinations /solutions... Sounds less tricky,say, than a chess problem, to me
ReplyDeleteIt's possibly more straightforward in terms of rules, but I think that the sets of information are quite numerable...
ReplyDeleteA solved cube can be rotated in any one of 6 faces, each face can rotate to 1 positions (0==4). However, each face turn also has the effect of altering the rows of 4 other faces.
I'm thinking that you'd describe each face as a 3x3 matrix, with a rotational transformation also applying a shift transformation in the 4 'adjacent' matrices.
This could turn into a *wicked* information theory exam question! 6 sets of 9 coloured squares distirbuted about the 6 faces... turning one face gives a probability of (blah, blah, yadda-yadda-yadda...).
I had a cheat sheet which would solve the the thing. Having no trouble solving one side, I printed just the remaining patterns, on a wallet card. And boy did that ever come in handy! No! But I think that solution would work out to less than 40 moves, and could have been made a little more efficient. I may still have one of those cards. But I haven't owned a Rubik's Cube in years.
ReplyDelete
ReplyDeleteVideo: CubeStormer II robot beats Rubik's Cube speed record
The world’s fastest Rubik cube solver is made from Lego!