From @mail.uunet.ca:mark.longridge@canrem.com Mon Aug 3 02:57:03 1992 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from mail.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) id AA13101; Mon, 3 Aug 92 02:57:03 EDT Received: from canrem.COM ([142.77.253.2]) by mail.uunet.ca with SMTP id <9679>; Mon, 3 Aug 1992 02:46:15 -0400 Received: from canrem.com by unixbox.canrem.COM id aa15064; Mon, 3 Aug 92 2:39:20 EDT Received: by canrem.com (PCB/Usenet Gateway) Path-id <19923.104.88888@dosgate>; 3 Aug 92 (02:30) Message-Id: <19923.104.88888@dosgate> From: Mark Longridge Date: Sun, 2 Aug 1992 20:00:00 -0400 To: cube-lovers@ai.mit.edu Subject: cube theory 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 = 243 At 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,T since 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