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

• Wheat Wizard: @H.PWiz No, you can't. That was implicit in my definitions but I will make it explicit in the question.
• totallyhuman: @DJMcMayhem By "normal", you mean 3×3. :P That could be a 2×2 cube. The symbols are definitely unlike a Rubik's cube, though.
• Level River St: Your specification does not include a complete description of the three parity laws of the cube. 1. It is impossible to have only 1 edge flipped 180 degrees (mentioned) 2. It is impossible to have only 1 corner twisted 120 degrees (not mentioned) 3. It is impossible to have an odd permutation of the cubies (not mentioned.). I'm casting a close vote until this is resolved. See ryanheise.com/cube/cube_laws.html for an explanation.
• user202729: @LevelRiverSt Note that the Rubik's cube is self-contained, anyone can derive at the mathematical formulation and parity laws independently.
• Level River St: @WheatWizard Thanks your intent is clearer now. Your original spec discussed swapping 2 stickers on the same cubie. This has the same effect as flipping an edge. But when 2 stickers are swapped on a corner it transforms into its mirror image, making the cube unsolvable for geometric (not parity) reasons even if dismantled. This is quite different from rotating a single corner 120 degrees. In that case the cube can be solved without peeling if dismantled, but cannot be solved by normal moves for parity reasons. The latter is harder to detect and I don't think it is covered in your original spec

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.

• Wheat Wizard: Does this work if we swap sides? For example 2 is opposite 4 in the cube dump, does it work if 2 is opposite 5 and 4 is opposite 0?
• MD XF: @WheatWizard Yes it does, solvemode checks if each face has a unique integer, and if that integer is the only one on the face.
• Wheat Wizard: Ok as it ought. I was not familiar with Cubically enough to know if this was the case or not from your description.
• MD XF: @WheatWizard Just making sure I understand you correctly - this is (along the lines of) what you were referring to, is that right?
• Wheat Wizard: Yes. And it should be solvable.

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