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.