Aesquire.135 net.games utzoo!decvax!duke!chico!esquire!psl Wed Sep 9 17:16:32 1981 Rubik's Cube Want to knoe how far away you can get from the solution on a Rubik's Cube? A Simple Lower Bound As everybody knows, the number of discrete configurations of the 3x3x3 Rubik's Cube is: (8! * 12! * 3^8 * 2^12) / 12 = 4x10^19 = 43,252,003,274,489,856,000 One approach to a lower bound is to calculate the maximum possible number of configurations you can reach with a particular number of moves and then see how many moves you would have to make to reach the number above. With no moves at all you get 1, the starting position. The first move gets you 18, (any one of six faces turned one of three ways). The next move gets you 18*15, (no point in turning the same face twice in a row), for a total of 1+18+270 configurations reached after two moves. A table of these values looks like: ---------possible configurations--------- moves new % max total 0 1 0.0% 1 1 18 0.0% 19 2 270 0.0% 289 3 4050 0.0% 4339 4 60750 0.0% 65089 5 911250 0.0% 976339 6 13668750 0.0% 14645089 7 205031250 0.0% 219676339 8 3075468750 0.0% 3295145089 9 46132031250 0.0% 49427176339 10 691980468750 0.0% 741407645089 Notice that 11 10379707031250 0.0% 11121114676339 not until 17 12 155695605468750 0.0% 166816720145089 moves has the 13 2335434082031250 0.0% 2502250802176339 total number 14 35031511230468750 0.1% 37533762032645089 of possible 15 525472668457031250 1.2% 563006430489676339 configurations 16 7882090026855468750 18.2% 8445096457345145089 exceeded the 17 118231350402832031250 273.4% 126676446860177176339 maximum. So there is no possible way to reach some configurations in fewer than 17 moves. However, this analysis has assumed that each configuration generated was a NEW one, but there are MANY cases where this will not be so. A simple example is turning one face 180 degrees, the opposite face 180 degrees, and then repeating those two moves -- four moves that get us to an old, familiar configuration. If we factor out the sequences that involve these opposite face identities the minimum number of moves becomes 18. Needless to say there are still lots of useless move sequences, but detecting them becomes a lot trickier. A Rumored Upper Bound Rumor has it that a computer program exists, (attributed to Thistlethwaite), that provably will solve any Cube configuration in at most 41 moves. Narrowing it Down So the answer is somewhere between 18 and 41. How do you get further? One way is to write a computer program that tries every sequence of moves until it has generated every possible configuration at least once. That sounds easy, and it is, but such a program would take a \\\L O N G/// time to run. However, if we limit the problem a little by considering a Cube that is two squares on a side (2x2x2), we have a chance of learning something. 2x2x2 Cube By the same considerations stated above we can get a lower bound for the 2x2x2 Cube. There are 7! * 3^6 = 3,674,160 configurations and, since we can limit ourselves to moving only three "orthogonal" sides of the 2x2x2 cube, on the n-th move you could reach 9 * 6^(n-1) new configurations thus we find that with 8 moves you could reach at most 3,023,307 and with 9 you could reach at most 18,139,851. (Note that this doesn't have the problem with opposite side moves that the 3x3x3 cube has.) Because the 2x2x2 cube is relatively simple we can actually run a program to try all the possible move sequences and compare our bound with fact. Listed below are the findings ------new configurations------- total configurations moves -----possible---- ---actual--- ---possible --actual number % number % number number 0 1 0.0% 1 0.0% 1 1 1 9 0.0% 9 0.0% 9 10 2 54 0.0% 54 0.0% 63 64 3 324 0.0% 321 0.0% 387 385 4 1944 0.0% 1847 0.0% 2331 2232 5 11664 0.3% 9992 0.3% 13995 12224 6 69984 1.9% 50136 1.4% 83979 62360 7 419904 11.4% 227536 6.2% 503883 289896 8 2519424 68.6% 870072 23.7% 3023307 1159968 9 15116544 411.4% 1887748 51.4% 18139851 3047716 10 90699264 2468.6% 623800 17.0% 108839115 3671516 11 544195584 14811.4% 2644 0.071% 653034699 3674160 Interestingly enough there are 2,644 configurations that require eleven moves to reach a solution; this is less than one tenth of one percent of the total configurations! It's also interesting that it's better than a 50-50 bet that a randomly ordered 2x2x2 cube can be solved in exactly nine moves, (it's not clear how to turn this into a profitable bar bet, however). Noticing that there are only 321 new configurations after three moves instead of 324 leads us to guess that there are six non-trivial sequences of six moves that end with the original configuration, (why?). These results came from a C program running on a VAX 11/780 and even though the 2x2x2 cube is simple compared to the 3x3x3 it took a lot of time. The figures for 11 moves took over 51 hours of cpu time. If you'd like to make a 2x2x2 cube with which to experiment you can simply take all the little labels off a 3x3x3 cube except the ones on the corners and then ignore the unlabeled cubes. Here's one sequence that gets you to one of the 2,644 configurations: f r f r f d2 f d- f d2 r2 f = rotate front face 90 degrees r = rotate right face 90 degrees d2 = rotate "down" face 180 degrees d- = rotate "down" face 270 degrees So Where's That Leave Us? I just thought of a dandy way to get the answer for the 3x3x3 cube, but the margins on this news item are a little too small for me to include it ... ----------------------------------------------------------------- gopher://quux.org/ conversion by John Goerzen of http://communication.ucsd.edu/A-News/ This Usenet Oldnews Archive article may be copied and distributed freely, provided: 1. There is no money collected for the text(s) of the articles. 2. The following notice remains appended to each copy: The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman.