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



## susan12 (Aug 20, 2012)

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 (Aug 20, 2012)

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


----------



## Mike Hughey (Aug 20, 2012)

ThomasJE said:


> 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 (Aug 20, 2012)

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 (Aug 20, 2012)

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



susan12 said:


> 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 (Aug 20, 2012)

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 (Aug 20, 2012)

Stefan said:


> 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 (Aug 20, 2012)

Stefan said:


> 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 (Aug 20, 2012)

Lucas Garron said:


> 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 (Aug 21, 2012)

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


----------



## Nils (Aug 21, 2012)

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 (Aug 21, 2012)

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 (Aug 21, 2012)

Nils said:


> 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.



Godmil said:


> (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 (Aug 21, 2012)

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 (Aug 21, 2012)

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 (Aug 21, 2012)

A Leman said:


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



No they don't.


----------



## Edward (Aug 21, 2012)

‎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 (Aug 21, 2012)

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


----------



## Mike Hughey (Aug 21, 2012)

Stefan said:


> 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 (Aug 21, 2012)

Stefan said:


> 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...


----------



## Mike Hughey (Aug 21, 2012)

Edward said:


> 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...





Spoiler


----------



## Edward (Aug 21, 2012)

Mike Hughey said:


> Spoiler



A Cubing Angel 
How are you not dead?


----------



## Mike Hughey (Aug 21, 2012)

Edward said:


> A Cubing Angel
> How are you not dead?



I haven't locked up ... yet ...


----------



## Edward (Aug 21, 2012)

Mike Hughey said:


> I haven't locked up ... yet ...



Keep it up. The Mad Man with The Twistable Box should be there soon.


----------



## Stefan (Aug 21, 2012)

Mike Hughey said:


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



Ah, ok. But it didn't exactly help that he omitted the first "—" in there. That screws it up.


----------



## Nils (Aug 22, 2012)

Godmil said:


> welcome to the forums Nils)



Thank you 



Stefan said:


> How so? His answer and explanation are wrong



How you mean? What other definition of local minima and local maxima do you know of other than the definition used in analysis and differential calculus? Local maxima and minima requires continuity. You going to tell me all the things they teach me here at university are incorrect? 



Stefan said:


> He also seems to confuse himself, first stating that the domain is discrete and then asking what the domain is...



I was just wondering what the domain was since i don't fully understand what she means with SA and A. Did she means A to be the move itself and SA to be the combination of move S and A, or S times move A?

_____
Nils



PS: "whats the half of a dozen" Good one


----------



## cuBerBruce (Aug 22, 2012)

Nils said:


> How you mean? What other definition of local minima and local maxima do you know of other than the definition used in analysis and differential calculus? Local maxima and minima requires continuity. You going to tell me all the things they teach me here at university are incorrect?



The question is talking about local maxima of an integer-valued function over the elements of a Cayley graph. The function has no local minima, except for the global minimum at the node representing the solved state.

I'll note that there can be two types of local maxima. For a "weak" local maxima, neighboring nodes can have the same distance value as the local maximum node. For a "strong" local maxima, all neighboring nodes have a distance value less than the local maximum node.



Nils said:


> I was just wondering what the domain was since i don't fully understand what she means with SA and A. Did she means A to be the move itself and SA to be the combination of move S and A, or S times move A?



Unfortunately, susan12's pasting of the text lost the subscripts in the original version.


----------



## Nils (Aug 22, 2012)

cuBerBruce said:


> The question is talking about local maxima of an integer-valued function over the elements of a Cayley graph. The function has no local minima, except for the global minimum at the node representing the solved state.
> 
> I'll note that there can be two types of local maxima. For a "weak" local maxima, neighboring nodes can have the same distance value as the local maximum node. For a "strong" local maxima, all neighboring nodes have a distance value less than the local maximum node.
> 
> ...




Oh sorry my bad :S , i did not knew that there was also a definition of local maximum in group theory? Or is it the same as in analysis?

edit: Ok i think i understand it  Thanks!


----------

