~~~ From:

~~~ Subject:

I've been doing some research to try and figure out some things

about the cube. I've also tried (unsuccessfully) to develop a sort

of CRC or checksum for the cube. With this cube "signature" I could

then find out which depth each pattern requires. I'm puzzled how

some computer types managed to find God's Algorithm for the 3x3x3

squares group. How do you keep track of all the patterns without

repeating yourself? If it is by holding all patterns in an array

the array must become huge.

Maximum Depth (using q and h moves) -------------

2x2x2 sq group 4 (24 total states) Pyraminx 11 (or 14 including the 3 tips) 2x2x2 11 (14 using q turns only) 3x3x3 corners only 11 3x3x3 sq group 15 (half turns only, don't know if using q improves this) 3x3x2 domino 18 (for 1 solution)

A local maxima is a state where any possible move will bring you closer

to a solution. This can occur on the 2x2x2 at depth 4 and on the 3x3x3

at

depth 3. Note that all possible patterns at maximum depth are local

maxima,

however it is surprising that local maxima may occur in patterns much

closer to the surface.

To date, no work has been done to determine the depth of the

dodecahedron

(megaminx) or square 1.

Some questions:

What pattern is an example of local maxima? e.g. 3x3x3 at depth 3

-> 12-flip, 12-flip 8-twist

q+h Depth Patterns 2x2x2 1 9 3x3x3 1 18 Dodecahedron 1 48

Analysis of the full cube group -------------------------------

Moves Deep arrangements (q+h) arrangements (q only) *

0 1 1 1 18 12 2 243 114 3 3,240 1,068 4 > 48,600 10,011

* Work by Zoltan Kaufmann

Notes: At 1 move deep each of the 6 sides can turn 3 ways (+ - 2) giving 18 distinct patterns

At 2 moves deep it is redundant to turn the same side again

so 5 sides can turn 3 ways so 18x15=270

However, with opposite turns order is not significant,

e.g. T,D = D,T F,B = B,F L,R = R,L

since each of these can occur in 9 different ways there are 27

redundancies so 270 - 27 = 243At 3 moves deep with the first 2 moves on opposite faces don't turn the face used in move one since: T,D,T = T2,D F,B,F = F2,B L,R,L = L2,R This can occur in 3x3x3=27 ways for each case so 81 are dropped (Remember the first 2 moves have already been weeded of redundancy!) Also when the 2nd and 3rd moves are of opposite faces e.g. T,R,L = T,L,R B,R,L = B,L,R F,R,L = F,L,R D,R,L = D,L,R T,B,F = T,F,B D,B,F = D,F,B L,B,F = L,F,B R,B,F = R,F,B F,T,D = F,D,T B,T,D = B,D,T L,T,D = L,D,T R,T,D = R,D,Tsince each of these can occur 27 different ways in each of the cases this gives 27x12 = 324 redundancies Thus 243x15 = 3645, removing the redundancies gives 3645-81-324=3240

>At 4 moves deep.... still working on this one! Zoltan Kaufmann

>has done 4 moves deep using quarter turns, but has anyone

>calculated farther using q and h turns? I'd be interested in

>the source code of any programs people have written on finding

>path-lengths. Also what is an example of a local maxima close

>to the surface, e.g. 4 moves. I believe Jim Saxe and Dan Hoey

>have done some work in this regard.

One more question: What is the maximum number of moves required if you do the 3x3x3 one face last? The best results I've seen are 19 q and h moves. -> Mark Longridge -- Canada Remote Systems - Toronto, Ontario/Detroit, MI World's Largest PCBOARD System - 416-629-7000/629-7044