The Rubik's Cube is often said to be the best-selling toy of all time
(given suitable restrictions). Invented in 1974 by Ernő Rubik, a
Hungarian sculptor and professor of architecture, it takes the
appearance of a large cube divided into 
~3 \times 3 \times 3~ smaller cubies, three to
an edge. Centre cubies have one face exposed; edge cubies have two; and
corner cubies have three. Each exposed cubie face has a sticker on it;
other than this, all cubies are identical. Stickers are merely coloured
squares, and cannot be distinguished from 
~90~-degree rotations of
themselves. In a solved configuration of the cube, all stickers on a
particular face have the same colour. A special internal mechanism takes
the place of the 
~27~-th cubie inside the cube; it holds the cubies
together and allows rotation of any of the cube's six faces. When a
face is rotated, each one of the nine cubies on that face revolves
around the centre (although the centre is not visibly affected), taking
their stickers along with them, without disturbing any of the other
cubies. The overall shape of the cube is not changed by rotation, but
the configuration of the stickers is changed.
If one holds the cube such that one of the faces is pointed directly at
oneself, it is possible to assign a notation to the faces of the cube –
F for front (the face directly visible), U for up, D for down, L for
left, R for right, and B for back (the face opposite the front face).
From this it is only a small step to a notation for rotations. A
~90~-degree clockwise rotation is denoted by the letter corresponding to
the face to be rotated; a 
~180~-degree rotation is denoted by the letter
followed by the numeral 
~2~; and a ~90~-degree counterclockwise rotation is
denoted by the letter followed by a single quote ('). For example, R'D2F
means to rotate the right face counterclockwise, then rotate the bottom
face ~180~ degrees, then rotate the front face clockwise. Order is
important. Any rotation, whether it is clockwise, counterclockwise, or
~180~ degrees, is considered a single face turn, often shortened to
move.
In this problem, a configuration of the Rubik's cube will be represented
by a net, such as the following:
1 1 1
1 1 1
1 1 1
2 2 2 3 3 3 4 4 4 5 5 5
2 2 2 3 3 3 4 4 4 5 5 5
2 2 2 3 3 3 4 4 4 5 5 5
6 6 6
6 6 6
6 6 6
Each 
~3 \times 3~ block represents the nine stickers of a face. The actual
configuration represented by this net may be determined by folding it
into the three-dimensional cube shape, and holding it such that the
uppermost block forms the U face and the leftmost block forms the L
face. Similarly, the centre block represents the F face, the block to
the right represents the R face, the rightmost block represents the B
face, and the bottom block represents the D face. This configuration is
solved because all the stickers on each face match. On the other hand,
the following configuration:
3 1 1
3 1 1
3 1 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
5 6 6
5 6 6
5 6 6
requires a clockwise twist of the L face in order to restore to the
solved configuration above. Note that it is not necessarily the numerals
~1~ to 
~6~ used to denote the faces; one could just as well use the letters
~A~ to 
~F~, or perhaps W R B O G Y for white, red, blue, orange, green, and
yellow, a popular set of colours for the stickers.
Given a configuration of the Rubik's cube, you are to find a sequence of
moves that restores it to a "solved" configuration.
Input Specification
Nine lines in the format described above.
Output Specification
A string on a single line in the format given, that is, matching the
regular expression ^([UDLRFB][2']?)*$, no longer than 
~10\,000~ characters,
that corresponds to a sequence of moves that restores the configuration
in the input to a solved configuration. This will always be possible.
Sample Input
3 1 1
3 1 1
3 1 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
2 2 2 6 3 3 4 4 4 5 5 1
5 6 6
5 6 6
5 6 6
Sample Output
L
Scoring
It is known (Rokicki et al., 2010) that the exact upper bound on the
number of moves required to solve any legal configuration of the Rubik's
cube is 
~20~. However, this requires impractical computer resources. A
gentler solution method using A* gives solutions within 
~23~ moves within
a reasonable length of time on a desktop computer. Now, of the 
~25~ test
cases, some can be solved within a small number of moves, and the
minimum number required is known; others were randomly-generated, and
this is why any solution will be accepted. Thus, your score, a number
between 
~0~ and ~1~ inclusive, will be calculated as 
~\frac K N~, where 
~N~ is
the number of moves used by your solution. For the easier cases, 
~K~ is
the minimum number of moves required; for the harder cases, ~K~ is ~23~,
although if you get more than ~1~, your score is adjusted to ~1~.
Comments
For faces that are not the front face, what are "clockwise" and "counterclockwise" relative to?
As one would expect by convention, the normal vector.
which normal vector
The time limit....
The AC solution takes 0.021s worst case.