Is it a Rubik's Cube?

Question

A venerated pass time of pedants is to point out that pictures of "Rubik's Cubes" (on t-shirts, posters etc.) are not actually solvable.

The first thing that should be checked is that the cube is made up of the right pieces. To be solvable a cube needs six colors each with nine squares. The cube also needs each edge and corner unit (these are the smaller cubes that make up the cube) to be unique. Not only must they be unique but if two center pieces are opposite each other no edge or corner piece can contain both of those colors.

Once you have a cube that is made up of all the right pieces you still need to verify it can be solvable. There are a couple of rules here, so I'll defer to an expert to explain them, the spoiler below explains how we can do this. If you are interested in solving the problem on your own you don't need to visit the site to understand or participate in this challenge.

Linked explanation

Your task is to take a pattern as input and determine if it is in fact a solvable Rubik's cube. To be solvable there must be a way to perform valid moves on a cube so that the cube has only one color on each face (and the different faces have different colors). Most Rubik's cubes have a standard coloring (White is opposite Yellow, etc.) you may not assume that the solve state follows this particular coloring.

A valid move is either the clockwise or anti-clockwise rotation of a single face of the cube. With the rotation of the face of the cube any squares bordering the face are rotated as well, staying connected to the face they were previously touching.

IO

You may take the cube in any reasonable manner. If your language has some builtin "cube-face" type, good for you, that is fine as input, other wise you can take a 2D array of the net, of the cube, 1 3 by 3 lists for each face. Just be reasonable. If you want to know if a specific format is acceptable comment or ping me in chat and I will add to the challenge to state its validity.

Your input format need only support up to 9 possible colors.

For output this is a decision problem so you should output one constant value for "Yes, this is a valid Rubik's cube" and one different constant value for "No, this is not a valid Rubiks cube".

---

This is code-golf so answers will be scored in bytes with less bytes being better.

Test Cases

Here are test cases. They are formatted as the net of a cube with each square as a single letter. Different letters represent different colors. Any more testcases can be added upon request.

Solvable

   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
   YYY
   YYY
   YYY


   GRR
   GRR
   ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
   WYO
   YYB
   YYB

Unsolvable

   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
   YWY
   YYY
   YYY


   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
   YWY
   YYY
   YYY


   RRR
   RRR
   GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
   BBB
   YWY
   YYY


   RRW
   RRW
   GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
   BBB
   YYW
   YYO

Answer 1

Cubically, 1664 1631 1089 bytes

⇒FD2F'R'D2RUR'D2RFD2F'U'
⇒Ff1F'
⇒LFf1F'L'
⇒F'f1F
⇒F2f1F2
⇒L'F2f1F2L
⇒D'F'f1FD
⇒LR'FLR'DLR'B2L'RDL'RFL'RU2
⇒LFf8F'L'
⇒R'F'f8FR
⇒Ff8F'
⇒F'f8F
⇒ULU'f8UL'U'
⇒U'R'Uf8U'RU
⇒F2f8F2
⇒Df15D'
⇒D'f15D
⇒D2f15D2
⇒UF2UF2D'L2B2U'B2DL2F2D2B2D2F2
⇒U'DL2UD'B2
⇒UF2UF2D'L2B2D'R2UR2F2D2B2U2B2
⇒BL'BU2D2F'RF'U2D2
⇒LD'F2U'B2U'RU2R'F2R2F2D'R2DF2D
⇒B2URB2D2B2RB2U'D'L2D'B2
⇒B2LF'U'B2UFL'R2B2U'D2L2D'B2U
⇒B2RB2D2B2RB2U'L2UD'F2U'F2B2
⇒D2R'FUB2U'F'RU2B2D'F2R2UF2UF2
⇒B2R2U'L'D2B2U2R'U2R2F2L2R2UR2
⇒D2L'B2U2F2RUL2U'F2R2U'R2U2F2DL2D'
⇒UB2U'L2DL2B2DB2D'B2
⇒BR'BL2B'RBL2B2
⇒UF2B2U'F2B2U'F2L2R2B2R2
⇒R2U'F2DR2UF2D'R2DF2R2D'F2
⇒U'F2DF2UL2F2DL2DF2L2D2F2
⇒U2D'L2U'F2L2U'B2L2R2U'L2B2
⇒F2D'R2U2L2B2UF2L2U2F2L2UF2R2
⇒[f1]3
⇒[f2f37]3
⇒[f3f38]3
⇒[f4f39]3
⇒[f5f40]3
⇒[f6f41]3
⇒[f7f42]3
⇒[f8f43]2
⇒[f9f44]2
⇒[f10f45]2
⇒[f11f46]2
⇒[f12f47]2
⇒[f13f48]2
⇒[f14f49]2
⇒[f15f50]2
⇒[f16f51]2
⇒[f17f52]2
⇒[f18f53]2
⇒[f19f54]2
⇒[f20f55]3
⇒[f21f56]4
⇒[f22f57]5
⇒[f23f58]6
⇒[f24f59]7
⇒[f25f60]8
⇒[f26f61]9
⇒[f27f62]9[f27f62]2
⇒[f28f63]9[f28f63]3
⇒[f29f64]9[f29f64]4
⇒[f30f65]2
⇒[f31f66]3
⇒[f32f67]4
⇒[f33f68]5
⇒[f34f69]6
⇒[f35f70]7
rs[f36f71]8

Output if solvable: Solved!
Output if unsolvable: (empty, no output)

Input should be formatted as a Cubically cube-dump (see the Debug section). This was explicitly allowed by the OP.

Explanation

This program takes the approach of using a Devil's Algorithm to iterate over every possible state of the cube in the same group as the solved cube. If the cube is solvable, it will be solved at some point before the algorithm has finished (assuming the algorithm I used works properly).

Every line beginning with ⇒ (0x84 in Cubically's codepage) is a function definition; these functions build off of each other to make up the actual Devil's Algorithm. The first line to be executed is the last one:

rs[f36f71]8

r reads a cube from stdin and sets the memory cube to it. s puts the interpreter into "solvemode", which means that it exits and prints Solved! if the cube becomes solved (after being unsolved) at any point. The rest of the commands (which simply repeat f36f71 8 times) correspond to the final algorithm at the bottom of the linked page:

(D) = (CP) = (CPT8) = [(CPC8)(CPT7)]8 (3,847,762,288,469,010,006,992 moves)

(D) is the Devil's Algorithm. If you apply it to the cube, it will be solved at some point before you have done the algorithm once. As you can see, it is terribly long, nearly a thousand times more moves than there are possible positions.

How can I run it?

You can try it online, but that link doesn't work. TIO will almost definitely time out before this algorithm finishes (the maximum runtime for an interpreter is 60 seconds). If the cube is not solvable, this algorithm will take up to 11 million years for Cubically to finish (at ~15.2 million moves per second, which is what my Cloud9 IDE gets).

Additionally, you need a lot of memory to perform 3 sextillion moves. Cubically can perform about 4 million moves per second, but the process will most likely be killed due to overcommitted memory. It dies after 15 seconds on my VM with 512MB of memory. Why should performing moves on an already-allocated flat array cost memory? Found a memory leak (or twenty) and fixed it.

Here is a much more readable version that behaves the same way.

But I really want to see that it works!

The first actual move that is executed in this devil's algorithm is F2, so the quickest cube to solve would be one scrambled with F2:

   000
   000
   555
113222133444
113222133444
113222133444
   000
   555
   555

This indeed executes in 0.007 seconds on TIO.

How can this be improved?

There are certainly more devil's algorithms; I've found one that uses less than a thirtieth of the moves this one does. However, that would come at the cost of several thousand bytes (around 100MB more) and several dozen hours of converting a complex Hamiltonian circuit to Cubically code.

It's also possible to remove some of the functions and put them straight in the loop at the bottom. However, I'm going to sacrifice some bytes for some readability.

Additionally, I'm considering a modification of Cubically's looping behavior so that I can more easily repeat algorithms 7 or 8 times (instead of just hard-coding them with the function calls repeated 7 or 8 times in the source). Or I'll work some magic out with the notepad, and golf this using more loops.

Note that I will continue to optimize anything possible in the interpreter, so this may work on an average PC sometime in the future!

---

Cubically, 2 bytes

r▦

I like the above answer better so I'm adding this as an alternate solution. This runs in under a second, as opposed to a few million years.

r    read cube from standard in
 ▦   and solve it

Output if the cube is solvable: (nothing)
Output if the cube is unsolvable: Error: The cube has reached an unsolvable state.

Answer 2

APL (Dyalog Classic), 190 174 bytes

{∧/~∊(×1 2 3|+.-⌿↑⊃∘⍋¨¨¨a)({2|≢∪{⍵⌊⍵[⍵]}⍣≡⍵,0}¨⍳⌿↑⌽b)((∪≢∩)¨/b←(⊃∘⍋⌽⊢)¨¨¨a),6≢≢∪⊃⊃a←{c←4⍴⊂⍬⋄c[+/1≠i],←(≠/×i←↑⍳3⍴3){⊂⌽⍣⍺⊢⍵~' '}¨,⌿(3|∘.+⍨⍳3)⍉⍤¯1↑1 0 1\⍵⋄1↓c}¨⍵(3 3∘⍴¨1 1∘⌷¨⍵)}

Try it online!

The argument is a 3x2 matrix (row0: front back, row1: left right, row2: up down) of 3x3 character matrices. Returns 1 for a solvable Rubik's cube, 0 otherwise.

In the TIO link, function t, which is not included in the character count, reads 9 lines of input, converts them from the default input format (a net) to the required 3x2 x 3x3 matrix, calls the solution and prints OK if the result is as expected.

The algorithm splits the given cube into 26 cubies - strings of length 3 (corners), 2 (edges), and 1 (centres). It also generates the 26 cubies of a solved cube with the same 6 central cubies. All of the following criteria must be met:

• there are no duplicates among the 6 centres

• the sets of given/solved cubies match, up to rotation - e.g. consider 'WBR' and 'BRW' the same cubie, but not 'BWR'

• the parities of both the corner permutation and the edge permutation are even

• the modulo-3 sum of corner rotation indices (e.g. taking the "smallest" letter B as a reference point we have: 'BRW'→0, 'WBR'→1, 'RWB'→2) match between the given and solved cubes; same for the corners modulo 2