14
$\begingroup$

When writing a program to permute a Rubik's Cube and then subsequently detect whether it is solved or not, what is the absolute minimum amount of programmatic effort required to determine if the cube is solved?

One can obviously check all six sides to determine if the cube is solved, and return early if anything appears out of order. One can also reduce that effort, by always ignoring one side, since five solved sides implies that the sixth side is solved.

Are there any other optimizations one can introduce?

Note: My attempts at googling this answer ended up with a lot of cube solving materials, and some code that actually detects solved cubes, but nothing in the way of optimal solutions to programmatically detecting a solved cube.

Improve this question
$\endgroup$
3
  • $\begingroup$ I assume we can ignore cases where one or more pieces were incorrectly rotated during solving (i.e. ignore "the cube is not solvable due to hardware malfunction" case) $\endgroup$
    – Joel Rondeau
    Commented Oct 21, 2021 at 14:17
  • 1
    $\begingroup$ Correct. The intention is to permute a 3x3x3 cube modeled in computer memory and determine when/if it is in a solved state. We can assume that there are no cube hardware malfunctions. $\endgroup$
    – Chuck Wolber
    Commented Oct 23, 2021 at 23:29
  • $\begingroup$ The answer will depend much on how you represent your cube in memory. If you model the colors of the facelets you want to verify the colors of 6x9 = 54 facelets. If you model the pieces forming the cube you want to verify the position of the 20 pieces. If you model the cube in terms of the colors of the facelets then my question puzzling.stackexchange.com/questions/115494/… might be what you are asking. $\endgroup$
    – Florian F
    Commented May 22, 2022 at 21:49

2 Answers 2

Reset to default
7
$\begingroup$

I think:

2 solved opposite layers and 3 of the remaining edges (from 4) is optimal

Also

3 faces in a horseshoe and a missing edge (from 2)

This leaves:

3 orthogonal faces and 2 of the missing edges (from 3)

Beyond this:

Any combination of 4 faces involves one of the above cases.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Maybe I'm misunderstanding something, but about the first one, don't you mean layers (so the complete 2/3 -sided cubies) instead of faces (a side of 3x3 stickers)? If not, how would you differentiate from a solved cube and let's say this cube? The white/yellow faces are solved, as well as the four edges in the middle layer. $\endgroup$
    – Kevin Cruijssen
    Commented Aug 6, 2019 at 20:42
  • 1
    $\begingroup$ @KevinCruijssen; good point, I've fixed it. $\endgroup$
    – JMP
    Commented Aug 6, 2019 at 20:46
  • $\begingroup$ Thanks for the help. I used your answer in my C++ Cube class implementation. github.com/chuckwolber/Cube $\endgroup$
    – Chuck Wolber
    Commented Aug 29, 2019 at 7:32
  • $\begingroup$ I have a hard time believing that checking all but two of the stickers is optimal. If you checked all stickers except the three on one of the corners, you'd be at leaving out three stickers and still come to the same conclusion. $\endgroup$
    – Ian MacDonald
    Commented Oct 21, 2021 at 15:32
2
$\begingroup$

Think of this in terms of orientation and permutation of edges and corners.

Corners can be uniquely identified by checking any two facelets. And a single corner cannot be out of place or orientation by itself. So you need to check any two facelets of 7 of the corners.

Both facelets must be checked to identify an edge, but checking 7 of 8 facelets for the edges on each layer would suffice. This can be further improved for the last layer because 1 edge can’t be out of place or orientation by itself. So you could check 4 facelets on the outer face of the first layer along with 3 remaining facelets of these edges, all 8 facelets on the second layer, and then only 3 of the adjacent facelets on the last layer. As stated earlier, the last face doesn’t need to be checked at all.

This comes out to checking 32 of the 48 facelets. If you don’t know the orientation of the centers, you would also need to check 3 adjacent ones (one for each axis). So less than 67% are required.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "last 2 edges can’t be out of (...) orientation by themselves" Sure they can. It is possible to flip two edges without affecting anything else. $\endgroup$
    – Jaap Scherphuis
    Commented Sep 5, 2019 at 5:05
  • $\begingroup$ You're right, thanks. I updated the answer. I'm so used to doing OLL before PLL :) $\endgroup$
    – StevenWhite
    Commented Sep 5, 2019 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.