Is there any program that solves scrambled Rubik cube in 20 moves?
From what I searched on the internet, the answer is probably NO.
Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
the Rubik cube remaining only 2 mismatched corners may still need 17 moves
to finish, this suggests to me all other strategies commonly seen on the
internet (e.g. layer by layer, cross centers first,...) are not much different
from any chosen random cubes that are ~3 steps closer to the goal.
Is my understanding of the Rubik cube problem right?

On 05/08/2022 23:02, wij wrote:
> Is there any program that solves scrambled Rubik cube in 20 moves?

The reference I gave a few days ago, "http://www.cube20.org",
has a link to their source. I don't know whether this is what you
want.

> From what I searched on the internet, the answer is probably NO.
> Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
> the Rubik cube remaining only 2 mismatched corners may still need 17 moves
> to finish, this suggests to me all other strategies commonly seen on the
> internet (e.g. layer by layer, cross centers first,...) are not much different
> from any chosen random cubes that are ~3 steps closer to the goal.
> Is my understanding of the Rubik cube problem right?

Probably not. Solving layer by layer, etc., is certainly far
from optimal, witness the much larger upper bounds given by the early
solvers [such as Singmaster, Conway, Thistlethwaite]. Note that ~98%
of all positions are >= 17 moves from solution; it wouldn't be at all
surprising if some of them are visually quite nearly solved. In the
days when I was interested in this sort of problem in relation to
sliding-block puzzles [see

http://www.cuboid.me.uk/anw/Research/CMate

(includes source, of a sort); very old] and chess endgame databases,
there were always "surprises" where problems turned out to have very
long or very short solutions.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Hertel

On Saturday, August 6, 2022 at 7:57:45 PM UTC+8, Andy Walker wrote:
> On 05/08/2022 23:02, wij wrote:
> > Is there any program that solves scrambled Rubik cube in 20 moves?
> The reference I gave a few days ago, "http://www.cube20.org",
> has a link to their source. I don't know whether this is what you
> want.
> > From what I searched on the internet, the answer is probably NO.
> > Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
> > the Rubik cube remaining only 2 mismatched corners may still need 17 moves
> > to finish, this suggests to me all other strategies commonly seen on the
> > internet (e.g. layer by layer, cross centers first,...) are not much different
> > from any chosen random cubes that are ~3 steps closer to the goal.
> > Is my understanding of the Rubik cube problem right?
> Probably not. Solving layer by layer, etc., is certainly far
> from optimal, witness the much larger upper bounds given by the early
> solvers [such as Singmaster, Conway, Thistlethwaite]. Note that ~98%
> of all positions are >= 17 moves from solution; it wouldn't be at all
> surprising if some of them are visually quite nearly solved. In the
> days when I was interested in this sort of problem in relation to
> sliding-block puzzles [see
>
> http://www.cuboid.me.uk/anw/Research/CMate
>
> (includes source, of a sort); very old] and chess endgame databases,
> there were always "surprises" where problems turned out to have very
> long or very short solutions.
>
> --
> Andy Walker, Nottingham.
> Andy's music pages: www.cuboid.me.uk/andy/Music
> Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Hertel

I just find out Rubik's cube (algorithm) is a NPC problem.
https://jcrouser.github.io/CSC250/projects/rubiks-cube/index.html
All the strategy I saw are 'illusion'. Any cubic configuration can be sub-goal.

On 11/16/2022 10:59 AM, wij wrote:
> On Saturday, August 6, 2022 at 7:57:45 PM UTC+8, Andy Walker wrote:
>> On 05/08/2022 23:02, wij wrote:
>>> Is there any program that solves scrambled Rubik cube in 20 moves?
>> The reference I gave a few days ago, "http://www.cube20.org",
>> has a link to their source. I don't know whether this is what you
>> want.
>>> From what I searched on the internet, the answer is probably NO.
>>> Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
>>> the Rubik cube remaining only 2 mismatched corners may still need 17 moves
>>> to finish, this suggests to me all other strategies commonly seen on the
>>> internet (e.g. layer by layer, cross centers first,...) are not much different
>>> from any chosen random cubes that are ~3 steps closer to the goal.
>>> Is my understanding of the Rubik cube problem right?
>> Probably not. Solving layer by layer, etc., is certainly far
>> from optimal, witness the much larger upper bounds given by the early
>> solvers [such as Singmaster, Conway, Thistlethwaite]. Note that ~98%
>> of all positions are >= 17 moves from solution; it wouldn't be at all
>> surprising if some of them are visually quite nearly solved. In the
>> days when I was interested in this sort of problem in relation to
>> sliding-block puzzles [see
>>
>> http://www.cuboid.me.uk/anw/Research/CMate
>>
>> (includes source, of a sort); very old] and chess endgame databases,
>> there were always "surprises" where problems turned out to have very
>> long or very short solutions.
>>
>> --
>> Andy Walker, Nottingham.
>> Andy's music pages: www.cuboid.me.uk/andy/Music
>> Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Hertel
>
> I just find out Rubik's cube (algorithm) is a NPC problem.
> https://jcrouser.github.io/CSC250/projects/rubiks-cube/index.html
> All the strategy I saw are 'illusion'. Any cubic configuration can be sub-goal.

I don't believe that is possible. Perhaps the article meant a slightly
different problem where the cubes you must solve have side lengths of n
> 0 and the algorithm must solve any such problem.

When, as with Rubik's, there are only a finite number of problem
instances, the solution time is O(1).
--
Jeff Barnett

On Saturday, August 6, 2022 at 6:02:36 AM UTC+8, wyni...@gmail.com wrote:
> Is there any program that solves scrambled Rubik cube in 20 moves?
> From what I searched on the internet, the answer is probably NO.
> Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
> the Rubik cube remaining only 2 mismatched corners may still need 17 moves
> to finish, this suggests to me all other strategies commonly seen on the
> internet (e.g. layer by layer, cross centers first,...) are not much different
> from any chosen random cubes that are ~3 steps closer to the goal.
> Is my understanding of the Rubik cube problem right?

I just finished a rubik cube solver program. For this specific case,
https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666,
14 steps is enough. Lots of fun and enlightenment in this cubic solving program.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf
seems saying that any scrambled cube can be solved in 18 steps, not 20 steps as
previously thought.

On 10/01/2023 08:48, wij wrote:
> On Saturday, August 6, 2022 at 6:02:36 AM UTC+8, wyni...@gmail.com wrote:
>> Is there any program that solves scrambled Rubik cube in 20 moves?
>> From what I searched on the internet, the answer is probably NO.
>> Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
>> the Rubik cube remaining only 2 mismatched corners may still need 17 moves
>> to finish, this suggests to me all other strategies commonly seen on the
>> internet (e.g. layer by layer, cross centers first,...) are not much different
>> from any chosen random cubes that are ~3 steps closer to the goal.
>> Is my understanding of the Rubik cube problem right?
>
> I just finished a rubik cube solver program. For this specific case,
> https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666,
> 14 steps is enough. Lots of fun and enlightenment in this cubic solving program.
>

Nice!

> https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf
> seems saying that any scrambled cube can be solved in 18 steps, not 20 steps as
> previously thought.

No, 20 steps is the accepted number. I think it was Michael Reid (mathematician) who found examples
requiring at least this many moves to solve.

Assuming 20 is the max required, we'd expect many/most positions to need less than the max. Here
are the first two lines from your link:

We have found the first optimal solutions to random
instances of Rubik's Cube. The median optimal
solution length appears to be 18 moves.

So the claim is 18 moves for the MEDIAN, not max number of moves. 18 is not a surprising number for
the median, but it's not something they've proved - it's just based on a few random tests.

Regards,
Mike.

On Friday, January 13, 2023 at 1:46:19 AM UTC+8, Mike Terry wrote:
> On 10/01/2023 08:48, wij wrote:
> > On Saturday, August 6, 2022 at 6:02:36 AM UTC+8, wyni...@gmail.com wrote:
> >> Is there any program that solves scrambled Rubik cube in 20 moves?
> >> From what I searched on the internet, the answer is probably NO.
> >> Then, from the example https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
> >> the Rubik cube remaining only 2 mismatched corners may still need 17 moves
> >> to finish, this suggests to me all other strategies commonly seen on the
> >> internet (e.g. layer by layer, cross centers first,...) are not much different
> >> from any chosen random cubes that are ~3 steps closer to the goal.
> >> Is my understanding of the Rubik cube problem right?
> >
> > I just finished a rubik cube solver program. For this specific case,
> > https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666,
> > 14 steps is enough. Lots of fun and enlightenment in this cubic solving program.
> >
> Nice!
> > https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf
> > seems saying that any scrambled cube can be solved in 18 steps, not 20 steps as
> > previously thought.
> No, 20 steps is the accepted number. I think it was Michael Reid (mathematician) who found examples
> requiring at least this many moves to solve.
>
> Assuming 20 is the max required, we'd expect many/most positions to need less than the max. Here
> are the first two lines from your link:
That (20) is correct. Data from https://www.cube20.org/ is much more reliable
and valuable, they seemed to have exhaustively explored the cube.
(For 'historical record', the webpage also says "July, 2010 20 20 0 Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge prove that God's Number for the Cube is exactly 20.")

> We have found the first optimal solutions to random
> instances of Rubik's Cube. The median optimal
> solution length appears to be 18 moves.
>
> So the claim is 18 moves for the MEDIAN, not max number of moves. 18 is not a surprising number for
> the median, but it's not something they've proved - it's just based on a few random tests.
>
> Regards,
> Mike.

One aspect the 3x3x3 cube problem is interesting is because it is so small and
the complexity sits between PC-solvable and PC-unsolvable. Another aspects link
to general problem solving (including math. problems, e.g. using instance to
prove theorem or general deduction method...).
However, there seems to be a fast algorithm, stay tuned.

On Friday, January 13, 2023 at 1:55:11 PM UTC+8, wij wrote:

I just verified a Rubik cube solver program can be very fast to yield an
optimal answer for any scrambled cube in, let's say, 0.1 second using average
PC, provided a 'key' is given. I think this is general: Provided a 'key'(short
data), NPC problems can be solved in *fast* P-time. Look like the
definition of NP problem? The difference is that 'key' is not 'certificate',
the program uses the 'key' to solve given cases.

For real applications, we can use large computers to generate the key, then,
an average PC can use this key to compute the answer. (sounds like commercial ads but not)