source: research/2008-rubik/solver/optimal/README @ 2739

Last change on this file since 2739 was 2739, checked in by kali, 12 years ago
  • introduce Michael Reid's optimal solver code in its original state

(a.out, no work on cpushare integration here)

  • introduce rubikutils, basicaly MR's structures and cube functions, but

adding cube orientation to the cube structure

  • rubikutils' main() inputs and validate a cube with center faces.
  • input order is:

F R U B L D UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

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