SOLVE3X, A RUBIK CUBE ANALYZER Despite its title, the `solve3x' program is not limitted to the 3x3x3 Rubik cube. Rather, the program is capable of analyzing any permutation group based on its generators. Given an arbitrary word in that group, it produces a reasonably short (though by no means minimal) path back to start using the original generators (moves). There is a host of Rubik puzzles that fit this paradigm, including the 2x2x2 pocket cube, the 4x4x4 super cube, the Rubik tetrahedron, and the Rubik Magic Square puzzle. Many other "Rubik-clone" puzzles also exist, including a relatively new puzzle that permutes colored marbles by rotating opposing plates. Finally, you can analyze a completely theoretical permutation group that has no physical manefestation. FROM A WEB SITE If this program is run from a web server, any arguments or options are ignored (there shouldn't be any), and the program analyzes the standard Rubik cube. The input configuration and the output solution are in HTML, and the common error legs print an HTML error page, rather than a simple message to stderr. But you're going to be running this program on your PC, not from a web site, so I won't waste any more time on this topic. USAGE Typing `solve3x -h' produces the following usage message. usage: solve3x [-d] [-s#] perm_grp_desc_file 20 23 26 19 22 25 18 21 24 11 14 17 10 13 16 9 12 15 47 50 53 46 49 52 45 48 51 33 30 27 34 31 28 35 32 29 2 5 8 1 4 7 0 3 6 38 41 44 37 40 43 36 39 42 > 35 34 33 32 31 30 29 28 27 0 1 2 3 4 5 6 7 8 20 23 26 19 22 25 18 21 24 53 52 51 50 49 48 47 46 45 42 39 36 43 40 37 44 41 38 9 10 11 12 13 14 15 16 17 > 2 1 0 5 4 3 8 7 6 11 10 9 14 13 12 17 16 15 38 37 36 41 40 39 44 43 42 29 28 27 32 31 30 35 34 33 20 19 18 23 22 21 26 25 24 47 46 45 50 49 48 53 52 51 For convenience, I include the centers in my permutations, even though each move leaves the centers fixed. Therefore there are 6*9 or 54 squares on the Rubik cube. I number the squares 0 through 53 as follows: top face, back to front, left to right; front face, top to bottom, left to right; right face; back face; left face; bottom face. The first move, presented on line 3, is a clockwise turn of the bottom face, and it is given the label 'B'. The next move, labeled 'F', is a clockwise twist of the front face. Together these 6 moves describe the Rubik cube. The lines that begin with '>' define the rotations that preserve symmetry. The first rotation spins the cube around the X axis, the second spins the cube around the Y axis, and the third reflects the cube through the XZ plane. These rotational permutations are optional, but their presence leads to significantly shorter solutions. The program first solves your Rubik cube as it sits, and stores the lenth of the path back to start. Then it spins the cube and solves it again. Perhaps this yields a shorter solution. If so, it translates the moves back through the rotation and stores the shorter solution. With rotations present, solutions tend to be much shorter than the average length printed in the statistics section. Finally, the line that begins with a '*' is the remapping permutation. If present, it must be the first permutation in the file. This permutation directs the solution of the cube. Try to get this square in position, then the next, then the next, and so on. If no permutation is specified, the program proceeds in numerical order, moving square 0 into position 0, then square 1, then square 2, and so on. Since squares are usually numbered for human convenience, this is rarely an optimal strategy. The above remapping permutation tells the program to start at the top-back edge (square 1), and then spread to the top-left corner, the top-left edge, and then the left-back edge. Once these pieces are in place, the right, front, and bottom faces can all be twisted without disturbing the progress that has already been made. This freedom makes it easier to solve the rest of the cube. Next the solution spreads to the right-back edge, leaving the bottom and front faces free to turn. The search for an optimal remapping order is more an art than a science, and hundreds of trials may be necessary. If you have built a pretty good remapping permutation, disturb it slightly, run the program, and see if the statistics improve. You may wish to write a program that generates hundreds of "reasonable" permutations, and feed them into solve3x, looking for the best statistics. The solve3x program handles any "reasonable" permutation group, provided you have the patience to encode said group in a group-description file. SOLVE2X, A COMPLETE POCKET CUBE ANALYZER The stand-alone program solve2x is a brute-force asault on the Rubik 2x2x2 cube, also known as the pocket cube. The program draws upon a database of cube configurations, which can be constructed via `solve2x -w'. The database takes about a half hour to build, and lives in the megabyte file "pocket.dat". Once the file has been created, run `solve2x' to derive a minimal path (14 moves or less) back to start. The program asks for the configuration of your pocket cube, using the I/O routines described above. The program prints a minimal solution, and then asks for the next configuration. This program consumes most of the resources of a modern PC, yet it analyzes only the pocket cube, having 3 milllion combinations. This underscores the difficulty in attacking the standard cube, with its 43 quintillion combinations.