[next] [prev] [up] Date: Sat, 30 May 92 02:32:22 +0200
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
[next] [prev] [up] Subject: Re: Lower-bound Kociemba's algorithm

(About my conjecture of 16 moves for phase 2:)
> Unfortunately Dik's conjecture for phase 2 is too optimistic.
> Recall the maximum distances of the 4 stages of my algorithm:
> 1. 7 moves within the group <R, L, F, B, U,D>
> 2. 10 moves within the group <R, L, F2,B2,U,D>
> 3. 8 moves within the group <R2,L2,F2,B2,U,D>
> 4. 18 moves within the group <R2,L2,F2,B2,U,D>
> (Stage 3 and 4 together requires at most 25 moves.)

> These number of moves are minimal and cannot be improved within their
> group of moves.
Did you (since your article) do an exhaustive search? In your article you
mentioned that you had 6 positions that still do require 18 moves. And you
mention that you doubted that there would be 17 move solvers. Have you
proven since then that it can not be done in less than 18? If not, send me
your positions and I will try.

I have currently a program running that tries all phase 4 positions. It
is possible to reduce the number of searches from 3,981,312 (the article
contains a typo here) to 428,544 by observing equivalent positions (as
I did mention in a previous article (*)). Assuming my conjecture of 16 the
complete calculations would take about 1000 to 1500 hours (%). Not
unprecedented ;-). (There must be a reason that I am a member of the CWI
research group on large scale computing.) There are now only two machines
munching at the problem, but there would be no problem to start up a few more
again. I just did it to see what happens.

* The equivalent positions are found by rotation of the complete cube along
the UD axis for a quarter turn, along the RL axis through a half turn and
mirroring along the FRBL plane. When looking at one dimension only this
reduces the number from 40320 to 2768. Restricting to Hans's initial positions
in phase 4, this reduces the number from 576 to 62. So the count becomes:
62 * 576 * 24 / 2
in stead of
576 * 576 * 24 / 2 (= ((4!)^5) / 2).
% I found that an exhaustive search upto 16 moves takes about 10 seconds.
Increasing to 17 would up the time to 110 seconds. So if you mail me
the situations for which you do not yet have less than 18 moves I will
have an attempt at them.
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland

[next] [prev] [up] [top] [help]