1 | README file for optimal Rubik's cube solver |
---|
2 | |
---|
3 | |
---|
4 | 1. Preliminaries. |
---|
5 | |
---|
6 | After you gunzip and untar the file you should have (besides the |
---|
7 | tar file) three files: |
---|
8 | |
---|
9 | % ls -l |
---|
10 | -rw------- 1 501 100 4629 2004-06-03 00:05 README |
---|
11 | -rw------- 1 501 100 133158 2004-06-03 00:05 optimal.c |
---|
12 | -rw------- 1 501 100 20552 2004-06-03 00:05 twist.c |
---|
13 | |
---|
14 | README is the file you are presently examining. optimal.c is the |
---|
15 | source code for the optimal solver. twist.c is the source code to |
---|
16 | a related utility (see below). |
---|
17 | |
---|
18 | |
---|
19 | 2. System requirements |
---|
20 | |
---|
21 | At least 80Mb RAM for the optimal cube solver. With less than 80Mb |
---|
22 | it probably won't run at any reasonable speed. I'm not even sure it |
---|
23 | will run well with 80Mb, so 88Mb or 96Mb is preferred. |
---|
24 | |
---|
25 | If you get it running on your system, I would appreciate if you let me |
---|
26 | know, so that I know it works on that type of system. Please send me |
---|
27 | e-mail to let me know that you have it working!! |
---|
28 | |
---|
29 | The program was developed on a Linux system, but should use only |
---|
30 | ANSI standard C. |
---|
31 | |
---|
32 | |
---|
33 | 3. Compiling the optimal solver |
---|
34 | |
---|
35 | The source file is optimal.c . It is presently configured to search by |
---|
36 | quarter turns. If you want to search by face turns, change line #5 to |
---|
37 | |
---|
38 | #define USE_METRIC FACE_TURN_METRIC |
---|
39 | |
---|
40 | You can also change the value of SEARCH_LIMIT if you desire. |
---|
41 | This will limit how far the program searches. The default value of 0 |
---|
42 | means no limit. |
---|
43 | |
---|
44 | My preferred method of compilation is |
---|
45 | |
---|
46 | % gcc -Wall -O2 optimal.c |
---|
47 | |
---|
48 | but feel free to use something else. |
---|
49 | |
---|
50 | |
---|
51 | 4. Startup time |
---|
52 | |
---|
53 | Startup time is significant. On my processor (200 MHz PentiumPro), it |
---|
54 | takes about 11 minutes to generate all the tables. While it's working |
---|
55 | on this, be sure to read the next section about input format. |
---|
56 | |
---|
57 | This is greatly reduced on newer computers. On a 933MHz P3, it should |
---|
58 | only take 2 or 3 minutes. |
---|
59 | |
---|
60 | |
---|
61 | 5. Input to the optimal solver |
---|
62 | |
---|
63 | A solved cube is represented as |
---|
64 | |
---|
65 | UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR |
---|
66 | |
---|
67 | To input a scrambled cube, first give the cubie that's in the UF location, |
---|
68 | then the cubie in the UR location, and so forth, according to this list |
---|
69 | above. For example, "cube in a cube" would be |
---|
70 | |
---|
71 | UF UR RD RB LU LF DB DL FR UB DF BL UFR RFD RDB RBU LFU LUB DLB LDF |
---|
72 | |
---|
73 | This input should all be on one line. Some people have expressed their |
---|
74 | displeasure with this system. I can't say I disagree, but I can't think |
---|
75 | of any system that's easy. So your ideas here would be useful. Read on |
---|
76 | to the next section about using "twist.c" to convert a sequence of twists |
---|
77 | into a cube in the desired format. |
---|
78 | |
---|
79 | Sequences that are produced as output solve the cube from the input state. |
---|
80 | |
---|
81 | You may also interrupt a search by typing Ctrl-C . Instead of exiting, |
---|
82 | it will prompt you for another cube. (To exit, type Ctrl-D .) |
---|
83 | |
---|
84 | |
---|
85 | 6. Using "twist.c" |
---|
86 | |
---|
87 | This is just a hack. Input to this program is a sequence of twists, all |
---|
88 | on one line. It outputs two cubes, the position created by applying the |
---|
89 | sequence to a solved cube, and the inverse position. The twists should |
---|
90 | be in the form F F2 F' etc. this program doesn't require any |
---|
91 | optimization. I compile it using |
---|
92 | |
---|
93 | % gcc -o twist.out -Wall twist.c |
---|
94 | |
---|
95 | |
---|
96 | 7. Miscellaneous |
---|
97 | |
---|
98 | The number of nodes overflows on long searches. With gcc this can be |
---|
99 | fixed by changing the global variable n_nodes to type long long int. |
---|
100 | |
---|
101 | |
---|
102 | 8. To do list |
---|
103 | |
---|
104 | a. Experiment with other "pattern databases." |
---|
105 | b. Perhaps unroll subfunctions in initialize_distance_table |
---|
106 | to reduce startup time. |
---|
107 | c. Consider solving the inverse position if this is a little |
---|
108 | bit easier |
---|
109 | |
---|
110 | |
---|
111 | 9. Changes since last version |
---|
112 | |
---|
113 | The main change is that I have implemented automatic symmetry reductions. |
---|
114 | This means that the program will analyze the symmetry of the input |
---|
115 | position, and use this to reduce the search space. If you input a |
---|
116 | position with 12-fold symmetry, it will run 12 times as fast. |
---|
117 | This feature is turned on by default. You can turn it off by #define-ing |
---|
118 | the symbol USE_SYMMETRY to 0 . |
---|
119 | |
---|
120 | Some other minor things: fixed a bug in twist.c when there's white |
---|
121 | space at the end of the input line. I also reverted to new-style |
---|
122 | function declarations. And the program should run fine without needing |
---|
123 | excess stack space. |
---|
124 | |
---|
125 | |
---|
126 | 10. Feedback |
---|
127 | |
---|
128 | e-mail me with any questions, comments, etc. at reid@math.ucf.edu . |
---|
129 | Currently, there is a pointer to the files on the web page |
---|
130 | |
---|
131 | http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html |
---|
132 | |
---|
133 | Good luck, and enjoy the program. If you make any interesting discoveries |
---|
134 | with the program, please share them with me and the cube-lovers mailing list. |
---|
135 | |
---|
136 | June 3, 2004 |
---|