How do optimal solvers and random state scramblers work?

[TheSquareOne]

It'd be great if we lived in a time with computers powerful enough to allow such a mindless approach to prove useful in solving any cube bigger than a 2x2x2, but we don't.

Technically we do, though Google call it ‘trespassing’.

 

[Lucas Garron]

Technically we do, though Google call it ‘trespassing’.

From what Tom Rokicki has estimated, Google could maybe solve a single 4x4x4 optimally, but not *much* more.

We live in a time with very powerful computers. The problem here is that the problem fundamentally gets very difficult very quickly for larger cubes (as far as we know). We're never going to be able to solve a 100x100x100 using the current approach. It doesn't have to do with our computers; it's purely a matter of the math.

However, it *would* be cool if we lived in a time/universe where we found a way to completely shortcut the search using clever math.

 

[AlphaSheep]

I want to see the code for a random-state scrambler in JavaScript so that I can understand better. What I can understand is it's generating a state, applying some rules to make it solvable, making it solvable in <R2,L2,F2,B2,U,D>, then solving it from there, and then inverting the scramble. I want to see code for it to know how it is applied.

http://www.qqtimer.net/scramble_333_edit.js
Good luck...

 

[Lucas Garron]

http://www.qqtimer.net/scramble_333_edit.js
Good luck...

How about looking at the source instead?

 

[Renslay]

From what Tom Rokicki has estimated, Google could maybe solve a single 4x4x4 optimally, but not *much* more.

We live in a time with very powerful computers. The problem here is that the problem fundamentally gets very difficult very quickly for larger cubes (as far as we know). We're never going to be able to solve a 100x100x100 using the current approach. It doesn't have to do with our computers; it's purely a matter of the math.

However, it *would* be cool if we lived in a time/universe where we found a way to completely shortcut the search using clever math.

The diameter of the nxnxn cube has the order of n^2 / log(n), so that's how fast God's number is increasing with bigger cubes.

 

[Lucas Garron]

The diameter of the nxnxn cube has the order of n^2 / log(n), so that's how fast God's number is increasing with bigger cubes.

Indeed. Unfortunately, we don't know any optimal solving approaches better than O(n) ^ O(diameter).

 

[StachuK1992]

What is 'n' and 'diameter' in this context?

 

[Lucas Garron]

What is 'n' and 'diameter' in this context?

The usual meanings: dimension and God's number.

 

[cuBerBruce]

The usual meanings: dimension and God's number.

Technically, the diameter is the maximum distance between any two positions, and I think God's number is generally regarded to mean the maximum distance from the solved position. (We expect these to be about the same value, of course.)