13
$\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.

$\endgroup$
6
$\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.

$\endgroup$
  • 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 Aug 6 at 20:42
  • 1
    $\begingroup$ @KevinCruijssen; good point, I've fixed it. $\endgroup$ – JMP Aug 6 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 Aug 29 at 7:32
1
$\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.

$\endgroup$
  • $\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 Sep 5 at 5:05
  • $\begingroup$ You're right, thanks. I updated the answer. I'm so used to doing OLL before PLL :) $\endgroup$ – StevenWhite Sep 5 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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