From cube-lovers-errors@mc.lcs.mit.edu Fri Jul 31 16:44:32 1998 Return-Path: Received: from sun28.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.8/mc) with SMTP id QAA01768; Fri, 31 Jul 1998 16:44:31 -0400 (EDT) Precedence: bulk Errors-To: cube-lovers-errors@mc.lcs.mit.edu Mail-from: From cube-lovers-request@life.ai.mit.edu Fri Jul 31 16:24:59 1998 Date: Fri, 31 Jul 1998 16:24:49 -0400 From: michael reid Message-Id: <199807312024.QAA10616@euclid.math.brown.edu> To: cube-lovers@ai.mit.edu Subject: new optimal solver lately i've been working on a new optimal solver. this is similar to the previous program, but uses different subgroups. let H be the subgroup in which the four edges FR, FL, BR and BL are all in place, and are correctly oriented and the four U corners are on the U face (and thus the four D corners are on the D face, and they are oriented so that the U [respectively D] facelet is on the U [respectively D] face. then the cosets H \ G are described by triples (e, cl, ct) where e describes the location and orientation of the four edges FR, FL, BR and BL, cl describes the location of the four U corners, and ct describes the orientation of the eight corners. there are 24 * 22 * 20 * 18 = 190080 different e coordinates, / 8 \ \ 4 / = 70 different cl coordinates, and 3^7 = 2187 different ct coordinates. all combinations are possible, so there are 190080 * 70 * 2187 = 29099347200 cosets. the subgroup H has 16-fold symmetry; it is invariant under any symmetry of the cube that preserves the U-D axis. therefore the coset space H \ G also has this symmetry. up to symmetry, there are 12094 e coordinates. thus, we can reduce the coset space to 12094 * 70 * 2187 = 1851470460 configurations. store each configuration in half a byte of memory (storing its distance from start). the whole thing can be stored in a tiny array of 925735230 bytes, approximately 883 megabytes. the number of cosets (actual numbers, not reduced by symmetry) at each distance is distance quarter turns face turns 0 1 1 1 8 12 2 76 162 3 696 2044 4 6418 25442 5 57912 316290 6 514318 3899553 7 4496206 46650252 8 38304572 517476714 9 308312232 4480840746 10 2142297548 16776040760 11 9789496784 7259620140 12 14800845359 14475084 13 2014724044 14 291026 i have this running on one processor of a sun ultra enterprise 450, configured with 1024Mb of RAM. startup time is significant: it takes about 85 minutes for quarter turns, 125 minutes for face turns, to exhaustively search the coset space. some rough estimates are that it is 6.7 times faster than my previous optimal solver for quarter turns, 3.4 times faster for face turns. this is not nearly as good as i'd hoped. there seems to be some performance issue with this machine. it appears to be significantly slower when accessing large amounts of memory at random, despite the fact that it is all real memory, so no swapping is occurring. the performance drop off starts at about 256Mb. my program runs slower by a factor of 3 or maybe even 4 because of this. my sysadmin has reproduced the same behavior on a small test program, so the problem is unlikely to be caused by my code. i'm told that it is probably some gross inefficiency in the cache paging system of the operating system (solaris). the os seems to have plenty of options, so perhaps one of them will fix this problem and speed up my program by a factor of 3 or maybe 4. it seems ridiculous to me that things work this way, but apparently they do. nevertheless, the program is already fast enough for the tasks at hand. mike