Rubik's Cube Solver

View as PDF

Submit solution

All submissions

Best submissions

Points: 50 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

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$ $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$ $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$ $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$ $90$ -degree clockwise rotation is denoted by the letter corresponding to the face to be rotated; a $180$ $180$ -degree rotation is denoted by the letter followed by the numeral $2$ $2$ ; and a $90$ $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$ $180$ degrees, then rotate the front face clockwise. Order is important. Any rotation, whether it is clockwise, counterclockwise, or $180$ $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:

Copy

      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$ $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:

Copy

      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$ $1$ to $6$ $6$ used to denote the faces; one could just as well use the letters $A$ $A$ to $F$ $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$ $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

Copy

      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

Copy

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$ $20$ . However, this requires impractical computer resources. A gentler solution method using A* gives solutions within $23$ $23$ moves within a reasonable length of time on a desktop computer. Now, of the $25$ $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$ $0$ and $1$ $1$ inclusive, will be calculated as $\frac K N$ $\frac{K}{N}$ , where $N$ $N$ is the number of moves used by your solution. For the easier cases, $K$ $K$ is the minimum number of moves required; for the harder cases, $K$ $K$ is $23$ $23$ , although if you get more than $1$ $1$ , your score is adjusted to $1$ $1$ .

Comments

1

TechnobladeNeverDies commented on Aug. 6, 2021, 1:53 a.m.

For faces that are not the front face, what are "clockwise" and "counterclockwise" relative to?

1

chika commented on Aug. 6, 2021, 3:39 a.m.

As one would expect by convention, the normal vector.

-2

TechnobladeNeverDies commented on March 25, 2022, 9:04 a.m.

which normal vector

-4

justin_g_20 commented on Sept. 20, 2020, 3:06 a.m.

The time limit....

4

Kirito commented on Sept. 20, 2020, 3:30 a.m.

The AC solution takes 0.021s worst case.