Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

About Rubik cube problems

35 views
Skip to first unread message

wij

unread,
Aug 5, 2022, 6:02:36 PM8/5/22
to
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?

Andy Walker

unread,
Aug 6, 2022, 7:57:45 AM8/6/22
to
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

wij

unread,
Nov 16, 2022, 12:59:48 PM11/16/22
to
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.

Jeff Barnett

unread,
Nov 16, 2022, 1:58:31 PM11/16/22
to
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

wij

unread,
Jan 10, 2023, 3:48:17 AM1/10/23
to
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.

Mike Terry

unread,
Jan 12, 2023, 12:46:19 PM1/12/23
to
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.

wij

unread,
Jan 13, 2023, 12:55:11 AM1/13/23
to
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.

wij

unread,
Jan 17, 2023, 5:07:28 AM1/17/23
to
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)

0 new messages