            ************************************************
             *******  ACube 3.1c  ***  Java Edition  ********
              ************************************************

Program to help searching for optimal and sub-optimal move sequences
to transform the 3x3x3 Cube into the (even partially) solved state.

                ------------------------------------------

--------------
 Please note:
--------------
This program is not associated with or sponsored by the owner of the Rubik's
Cube trademark. This owner is Seven Towns Ltd. (http://rubiks.com)
The program and the source code are freeware.
Use on your own risk...

Please, read carefully the following text in order to use all advantages of
the ACube program...
If you have any questions/comments, send me an e-mail to <gloom@email.cz> with
a subject starting with "ACube:".
I would like to correct any bugs in the program, so if you think you have
found one, send me a description and the input causing it (if possible).


---------------
 About Project
---------------
This program have been started to be my university project at the
Czech Technical University in Prague, Faculty of Electrical Engineering,
Department of Computer Science in 2001.
Programmed by Jelinek Josef <gloom@email.cz>
Other information can be found at
http://rubikscube.info and
http://cube.misto.cz.
The program was initially created in GNU C++ (EGCS).
Since the version 3.0 the program was converted to Java language.


--------------
 Requirements
--------------
 - an operating system with installed Java Runtime Environment (version >=1.1)
 - some more memory (64MB should be enough (maybe even 32MB))
 - interest in the cube
 - patience while writing the input configurations ;-)


-------------------
 Versions and Bugs
-------------------
3.1c 02/14/2005 The same fix as in 3.1 - How this bug could return?
                (thanks to Per Kristen Fredlund)
3.1b 07/28/2004 Fixed exceptions and incorrect results when using some premoves
                (thanks to Mike Godfrey again)
3.1  05/11/2004 Fixed bug in "restrict moves" feature (thanks to Mike Godfrey).
                Double moves were not set up correctly.
3.0  02/17/2004 Completely rewritten into Java language - removed many
                (mostly harmless) bugs.
                Added useful features:
                  - support for specification of allowed turns
                  - support for leading and trailing turns

2.6  ??/??/???? The mostly internal version with the first attempts
                to add user defined allowed moves
                Some bugs fixed

2.5  08/28/2001 The fixed version (could be bug-free now :-))
                the serious bug when you specified 2, 3, 4 or 5
                unoriented edges then the program did not work is fixed.
                I cannot believe that nobody meets this bug
                because I have not got any mail about this!!
                Or am I developing this program only for me?
                With that bug the program was a little useless
                so is it useless now too or what?

                Also saving of the current session and then
                possibility to continue somewhere else
                was been added (key-code generating)

2.1  ??/??/2001 The next version
                Solving of the incomplete cube added!!

2.0  ??/??/2000 The first public version
                Many things was added

1.x  ??/??/???? Simple 2-phase algorithm

TODO:
 - GUI
 - cube rotations for transformation of sequences to another rotation
   mostly for orientation of middle layer to E position
 - utilizing bigger precomputed (saved to a disk) tables
   (complete 2x2x2, etc.)

-----------------------------------
 Introduction and the Main Purpose
-----------------------------------
This program tries to help you during searching for the short sequences
to transform a special cube state into another one, which is closer
to the solved one. So it helps a man to be able to solve the Cube
step by step with the low number of turns.

It also helps corner-starter cubers because it can output sequences in
middle-slice move form and it can optimize for slice-turn metrics.

The program can find optimal and/or suboptimal sequences in one of three merics:
- quarter-turn (only F, F', R, R', ... counted as one turn)
- face-turn (plus F2, R2, ... counted as one turn)
- slice-turn (plus M, M', M2, ... counted as one turn)


----------
 Controls
----------
The program is started from console (command line).
It requires JRE installed and the 'java' or 'java.exe' command in the PATH.

There are an optional command-line arguments in the program:

 q   for 'quarter-turn' metrics
 f   for 'face-turn' metrics
 s   for 'slice-turn' metrics
 a   for searching all solutions with the current shortest length
 o   for searching only for optimal sequences in the given metrics

Examples:

> java -cp ACube3.jar ACube q a o
 - use quarter-turn metrics and search for all optimal sequences

> java -cp ACube3.jar Acube s
 - find me some nice moves and optimize them in slice turn-metrics

> java -cp ACube3.jar Acube osa
 - I need very short moves and I prefer slice-turns, show me all


After starting the program you will be prompted to input
a cube state that the program will try to solve.
The input is in this form:

  UF UR UB UL DF DR DB DL FR FL BR BL  UFR URB UBL ULF DRF DFL DLB DBR

This configuration represents the solved Cube (similar to the Reid's
program).
The doubles are edges and the triples are corners.
You can also use some simplifications for an incomplete cube.
Instead of an edge or a corner you can use:

 !   this cubie is in its right orientation and place
 @!  this cubie is in its right place but has unknown orientation
 -!  this cubie is in its right place but flipped (edge) or counter-clockwise
     twisted
 +!  as -! but only for corners and it is clockwise twisted
 ?   this cubie is oriented but is not known
 @?  this cubie is neither oriented nor known
 -?  this cubie is flipped (edge) or counter-clockwise twisted (corner) than
     cubie on the solved Cube in this position but is not known
 +?  as -? but only for corners and it is clockwise twisted

For orientation of corners only the first letter of the triple is important.
So UFR is equivalent of URF but not e.g. FUR.
You can also precede the double or triple by '+', '-', or '@'. It affects
the orientation of the given cubie in the same way.
(The @ character could be very useful here!)

You can also use some shortcuts and commands:

 000 to 777
   octal mask number of allowed turns bits corresponds to the UDFBLRESM pattern
   To restrict the available layers that can be used in the solution
   this number can be used. Each bit in the octal number corresponds
   to one layer in this order: UDFBLRESM - the most significant bit
   is on the left hand side. The binary number is written in octal
   (8-based) number format (each bit triple corresponds to one octal
   digit 0..7).
   Example: To find a solution that uses only U, L, R, and M turns
   the binary mask is: 100 011 001. The corresponding octal number to be
   specified is 431.

 000000 to 777777
   the first three digits are exactly the same as for the previous command;
   the last three digits are similar and corresponds to the U2D2F2B2L2R2E2S2M2
   pattern.
   This extended mask is useful to restrict some turns to half-turns only.
   Some cube-like puzzles can be solved using this command.
   For example, the Rubik's domino can be solved using
   U, U2, U', D, D2, D', F2, B2, L2, and R2 turns.
   The corresponding mask is 110 000 000 111 111 000 and the corresponding
   octal number to be specified is 600770.

 ~UDE
   leading and trailing moves (E, E', E2, D, D2 E', U D2 E2, ...)
   The possible combinations are: UDE, FBS, LRM, and their sub-strings
   (UD, UE, DE, U, D, E, ...). The given order of letters is important
   and should be as written (the order is not checked in the program
   and it can result into strange behavior if used wrong way).
   Useful command to search for intermediate sequences of a method, where
   the first and last turn is not significant (mostly is undone by a following
   move sequence).
   For example, an optimal sequence that orients last layer
   (before last layer permutation) is often preceded/followed by
   unimportant U move and the U move should not be counted in the length.
   However, without this command the U move is counted and other
   (not optimal) sequences can be found before this one.

 !!          repeats '!' to the end of edges or corners
 @!!         repeats '@!' to the end of edges or corners
 ??          repeats '!' to the end of edges or corners
 @??         repeats '@!' to the end of edges or corners

 Q           terminates the program
             (end of input can be used too - ^Z on M$, ^D on UN|X)
 N           cancels the input and asks for a new configuration (comment)

Examples:

 !! !!   solved cube
 ~U -? -? -? -? !! !!     flip upper edges and ignore their positions
                          the U, U', or U2 can preceede and finish the move
 ? ? ? ? !! -? -? -? ? !! twist 3 corners clockwise and leave 4 edges oriented
                          (ignore their positions)
 ! ! ! ! ! ! ! ! -! -! -! -! !!  flip edges of the middle layer in their places
 ? ? ? ? !! -! -! -! !!   known 'Sune'-like state
 ! ! ! ! @? @? @? @? !! +! ! ! ! @??  twist corner and ignore the bottom layer
 370 UL UF UR UB !! ULF UFR URB UBL !!  turn top layer without U turn alowed

-----------------------------------------------
 Important note for orientation understanding!
-----------------------------------------------
A Corner is correctly oriented if its facelet with the color of the top
or bottom cube face center is facing up or down.
Else it is twisted (clockwise or counter-clockwise) off this possition.

An edge is fliped if it is on the front resp. back face and you proceed
F or F' resp. B or B'.
Other situations leaves the edge in previous orientation.
The solved cube has all corners and edges correctly oriented.
Oriented edges that belong to the U or D layer have their U or D
facelet facing up or down -- if they are in U or D layer -- or
in the F or B face -- if they are in the E layer.
Oriented edges that belong to the E layer have their R or L
facelet in the R or L face -- if they are in R or L layer -- or
in the U or D face -- if they are in the U or D layer.

Read the previous note more than once to understand it...

Sometimes, you need to utilize the orientation of a middle layer
(in corner-starters method two opposite layers are often solved
regardless the layer between them).
To be able to address the orientation of such middle layer and/or
two opposite layers, the cube should be oriented in such a way that
the middle layer is between the U and D layers.

-------------------
 Output of Program
-------------------
The program outputs the found sequences to the standard output and other
information to the standard error output.

Output is in common format using characters 'U', 'D', 'F', 'B', 'L', and 'R'.
Single quote (apostrophe) means an inversion and '2' means a double turn.
If center slice-turns are allowed then 'E', 'S', and 'M' characters are used
for middle slice turns.

There are lengths in the different metrics in the parentheses at the end of
the found sequence.

Asterisk indicates that sequence is certainly optimal in the given metrics.

If the found sequence starts with some moves that are specified to be
ignored (~ command) they are shown in the begining of the sequence in
parentheses and are not counted in the length of the found sequence.

The found sequences are written to the standard output and can be redirected
to a file from the operating system command line (usually '> file').
Other information (tables, messages etc.) are written to the standard
error output.
The input cube configurations are read from the standard input and
can be redirected in similar way (usually by '< file').

---------
 Credits
---------
I'd like to thank following people:
 - Mike Godfrey for bug report
 - Herbert Kociemba for his algorithm and programs
 - Michael Reid for his algorithms and programs

and also

 - Erno Rubik for the Cube
 - David Singmaster for notation and many other things
 - and cubists on the Yahoo "speedsolvingrubikscube" group and
   the "cube lovers" mailing list)...
