Are there local maxima in the number of moves required to solve a Rubik's Cube?

[susan12]

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the n×n×n Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As Peter pointed out, my approach fails in some instances. One potential case of such an instance is where there exists a local maxima in the path length. By this I mean that it may take SA moves to solve the cube from configuration A, and either SA or SA−1 moves to solve the cube from any position which can be reached in one move from A.

Now, this isn't necessarily such a problem if SA is maximum number of moves required to solve the cube in general (God's Number for that cube), but is definitely a problem if SA is strictly less than God's Number for that cube. So my question is do such local maxima exist? Even an answer for the 3×3×3 cube would be of interest to me.

Susan.

 

[ThomasJE]

God's number for 3x3 is 20. 2x2 is 11.

 

[Mike Hughey]

God's number for 3x3 is 20. 2x2 is 11.

I suspect Susan already knew this.

I have a feeling that such local maxima might be common (of course, that means absolutely nothing - my feeling could be totally wrong). If they are common, then it might be rather easy to prove it by example programmatically with a hack of Cube Explorer, by generating a 17 or 18 move scramble, applying all possible single moves to that scramble, and then running each of the results to see if any go beyond the starting number. It shouldn't take but a few minutes to try each one, so I would think if they're common, you might find one rather quickly. Of course, if they're not common, it wouldn't do much good...

 

[whauk]

http://cube20.org/ look at the table at the bottom. there are 3*10^8 positions that are 20 moves away from solved but there are 1.5*10^16 positions that are 19 moves away. assuming every position could be made "harder" there would be no more than 18*3*10^8 that are 19 moves away from solved if the 20-moves-number is correct. this is significantly less even if you assume the estimates are bad. so as mike said they must be pretty common and they exist.
pretty interesting question. i wonder whether there's a "non-computer" proof...

 

[Stefan]

The most well-known local maximum is probably R2 L2 U2 D2 F2 B2.

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the n×n×n Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP.

What exactly is the question? Whether a certain state can be solved in a certain number of moves?

 

[Stefan]

Actually, what the F is this thread? Compare to http://cstheory.stackexchange.com/q...mber-of-moves-required-to-solve-a-rubiks-cube

 

[Mike Hughey]

Actually, what the F is this thread? Compare to http://cstheory.stackexchange.com/q...mber-of-moves-required-to-solve-a-rubiks-cube

That's spooky.

 

[Lucas Garron]

Actually, what the F is this thread? Compare to http://cstheory.stackexchange.com/q...mber-of-moves-required-to-solve-a-rubiks-cube

I presume also Susan wanted to ask here, where there were likely to be cube experts? I don't see anything unreasonable in that.

Anyhow, between that thread and this one, all the basic arguments are covered, so I don't have much more to say. It might be interesting to know what kind of structure the local maxima have, though (i.e. which ones are the asymmetric ones, and how many short ones of those there are
).

 

[Stefan]

I presume Susan wanted to ask somewhere where there were likely to be cube experts? I don't see anything unreasonable in that.

The point is that that was posted two years ago and by a different person. At the very least, "Susan" should have adapted the background story instead of copy&pasting someone else's.

 

[Mike Hughey]

It feels to me almost like something a bot might try to post. A less-braindead-than-average bot.

 

[Nils]

I don't think local maxima and minima can exist in the path length of a Rubik's cube solution, simply because it's discrete.
Local minima and maxima from a function f: X --> Y can only exist in a point x є X if the function f is continuous in that point x (that's why it is "local", you need to be able to get infinitesimally close to point x).
Since the path length in a Rubik's Cube is discrete, the function that gives you the path length is a discrete function (in this case both domain and image are discrete). This means that that function is discontinuous in every point of it's domain.

But of wich function do you want to know the local maxima anyway? Path length in function of ... ?


_____

Nils

 

[Godmil]

This thread is too weird, if it's not a bot, it's someone who's copy/pasted in an attempt to pass off as a legit member.
(I was suspicious of Nils too, but his post doesn't seem to be copy/pasted, and is really useful, so welcome to the forums Nils)
Susan, prove you're not a bot: what's half of a dozen?

 

[Stefan]

But of wich function do you want to know the local maxima anyway? Path length in function of ... ?

Read the last sentence of the first paragraph of the first post.

(I was suspicious of Nils too, but his post doesn't seem to be copy/pasted, and is really useful

How so? His answer and explanation are wrong and apparently he doesn't even understand the question. He also seems to confuse himself, first stating that the domain is discrete and then asking what the domain is...

 

[Godmil]

Ok, busted, I skimmed over the first few lines and it went over my head, so I presumed he knew what he was talking about.

 

[A Leman]

This thread is too weird because among other things Nils and Susan both address their name with the same syntax under their post and they are both one time posters. And their first and last activity was on this thread. With all of the math in this forum, did they both not have anything else to check out?

 

[Stefan]

Nils and Susan both address their name with the same syntax under their post

No they don't.

 

[Edward]

‎People assume that solving the cube is a strict progression of case to alg, but actually from a non-linear, non-subjective viewpoint - it's more like a big ball of wibbly wobbly... cubey wubey... stuff

 

[Stefan]

I can somewhat understand the part before the first comma, but I'm confused by the rest

 

[Mike Hughey]

I can somewhat understand the part before the first comma, but I'm confused by the rest

You must not be a Doctor Who fan:
http://tvtropes.org/pmwiki/pmwiki.php/Main/TimeyWimeyBall

 

[Edward]

I can somewhat understand the part before the first comma, but I'm confused by the rest

Don't lock up. Don't even lock up. Lock up and you're dead. They are fast, faster than you can believe. Don't turn slow, don't drop the cube, and DON'T LOCK UP. Good luck...