Solve a Rubik's Cube Your challenge is to write a program to solve a 3x3x3 Rubik's Cube. This challenge is based on this one from 2013, rewritten to adhere to current community standards, and reposted with the original author's permission and help on meta.

Input

The input should represent an unsolved Rubik's Cube.
You may read this input via any standard means, and the input can be in any format you choose, except a sequence of moves to get the cube to an unsolved state (or anything similar); that would trivialize this challenge.

That means that the input can look like this:

    UUU
    UUU
    UUU
 LLLFFFRRRBBB
 LLLFFFRRRBBB
 LLLFFFRRRBBB
    DDD
    DDD
    DDD


U representing cubies on the top/upper face, L representing the left, etc.

It could also look like a Cubically cube-dump, an array of characters/integers, or the weird format in the original challenge; however you like. You must specify how input should be taken in your answer.

You can translate a cube-dump to an ULFRBD scheme here or the other way around here.

Output

You will output, via any allowed means, the moves that must be performed on the inputted Rubik's Cube to return it to the solved state. You may use any chosen notation or method to describe rotation; please specify what you use in your answer.

I recommend that you use Singmaster's notation as it is the simplest and clearest:

R - turn the right face of the cube 90 degrees clockwise
L - turn the left face of the cube 90 degrees clockwise
U - turn the top face of the cube 90 degrees clockwise
D - turn the bottom face of the cube 90 degrees clockwise
F - turn the front face of the cube 90 degrees clockwise
B - turn the back face of the cube 90 degrees clockwise


Append ' to any move to make it counterclockwise and 2 to any move to make it 180 degrees.

If you are unsure of the validity of an I/O method, feel free to comment or ping me in chat.

Examples

Input is in the format of a cube-dump and a ULFRBD layout; output is in Singmaster's notation.

Input -> D'U'R'L'R'L2R'F2U'D'U'D'LR'B'F'U'D'L2R'
Input -> RF2U2R2ULB2R2U2R'L'DB2U2D2B'R'F'B2DFU2RU2L'
Input -> L2FL'R'FB'U2D'F'R'LBF2R2L'F2D2BL2F2RU2D'LF'
Input -> B'U'FURD'B'F'RBF2D'F2R2L2FU'R'U'R2L2F'B2R'F
Input -> R2FUF2D'FR'B'D2L2F'URB2R'U'D'R2L'UD'R2B2UD2

Your program may assume that the given cube is possible to solve; i.e. you do not need to handle the case that the inputted cube is unsolvable.

Restrictions

Answers like this, while valid/interesting on other challenges, are not welcome here. You may not use an algorithm that iterates through every possible state of the cube and prints the moves as it goes, or anything similar.

To define these restrictions, your program must be able to solve each of the test cases above on TIO. So it must:


Exit in under 60 seconds.
Output less than 128KiB.


Validation

To validate that your program indeed solves the Rubik's Cube, you can obviously use a physical cube or an online cube emulator by mixing it how you like, feeding its state into your program, and then performing the output moves on the cube.

However, if you choose to format your input as the cube dump (or the ULFRBD scheme and translate it to a cube dump), you can validate your program via Cubically's online interpreter like so:


Go to the online interpreter.
Type rs into the Code section.
Paste your unsolved cube-dump into the Input section.
Run your program with the unsolved cube-dump. Copy the output into the Footer section.
Click Run. If your program is valid, Solved! will appear in the Output section. 


Winning

As this is code-golf, the shortest code in bytes wins!
Cubically, 3 bytes

rp▦


Try it online! You can use this to print a random cube.

Explanation:

r    read cube from stdin
 p   set PRINTMOVES flag to display moves as they are performed on the cube
  ▦  insert moves to solve the cube at the current point in the program


Capitalize the P to see prettier output (e.g. RLD'U2 as opposed to R1L1D3U2).