Rubik's Cube Solver

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×3×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 27th 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×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 Format

Nine lines in the format described above.

Output Format

A string on a single line in the format given, that is, matching the regular expression ^([UDLRFB][2']?)*$, no longer than 10000 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 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.

All Submissions
Best Solutions

Point Value: 50 (partial)
Time Limit: 2.00s
Memory Limit: 512M
Added: Dec 25, 2008
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I'm guessing this is more of a computing question, because the scoring is based on how many moves you return...
I actually solve Rubik's cubes and I average around 60 moves -.-
When you mention the A* algorithm do you expect a pathfinding type of answer?

Solving a Rubik's Cube [i]is[/i] a pathfinding problem. You can represent this problem as a graph.

Think of the current configuration of the cube to be a node, or vertex. Each move is an edge; so, every node has 18 adjacent nodes (6 faces * 3 rotations). The initial configuration is the starting vertex V_s, and the solved state is the destination vertex V_d. You then simply have to produce the shortest (or a fairly short, anyway) path from V_s to V_d.

hmm... are the centers always going to be:
U 1
L 2
F 3
R 4
B 5
D 6
?

No, they are random non-whitespace ASCII characters.

AWWW...... >.< that just makes it more annoying.... 
oh well... =/
guess it's not that hard to deal with...

lol, you actaully know how to do this problem?

Jacob only used brute force, and got 20 points.

Hey, you can't say "only brute force". That was the hardest brute force I've ever done, hardcoding those rotations is SUCH a nitch.

It was worth 20 points.

lol, i think we should designate you as "The Ultimate Hard-Coder in PEG (TUHCIPEG)

Where did the G come from? 

LOL

Bosco should take English lessons from either Hao (RCM = Royal Mountain Police) or Toby (BIT = Bacon Lettuce Tomato).

TUHCIPEG challenge accepted
:P i haz fastest hardcode

Damn this question is hard to hardcode.
I actually have to assemble the cube into the correct position for all cases past 3

It's not supposed to be an easy problem.

is there a limit to how long your code can be?

Hanson says that PHP limits your submissions to 2 MB. That being said, you shouldn't really be concerned with code length.
By the way, congratulations on the COMC this year. Once again I find myself with a rank worse than 50th...

thanks xD
good luck on the CCC this year!

I think the problem should be scored out of 23 --> 30, 22 is a little ridiculous for your time constraints.

All right, 22 is changed to 23 (not a lot of difference that will make, but here I must defer to one greater than I) but the scoring algorithm stands as it is.