# Rubik's Cube validity

## Recommended Posts

kirkd    505
I've been working on a Rubik's Cube solver, and for the most part I've gotten that working nicely. Currently I do not have the ability for a user to input their scrambled cube - that's next on the plate. This creates a bit of a problem - how do I determine that the entered cube is valid? There are some obvious things that could be done - check to make sure colors on any cubie could actually occur, for example. The Rubik's Cube also has a parity issue such that I cannot rotate just one edge cubie without another being affected. I believe the corners follow the same type of rule. Any ideas how I can verify the validity of an arbitrarily scrambled cube?? -Kirk

##### Share on other sites
Rockoon1    104
If the solver cannot solve it...

ToohrVyk    1595

##### Share on other sites
kirkd    505
Hmmm...yeah, unsolvable is not likely an option. The expected maximum depth to search would be around 21 moves for an optimal solution of a 3x3x3 Rubik's Cube. Given that the branching factor is 18 for the first move and 15 for each subsequent move, I would have to search 18+15^20 states to guarantee that no solution exists within 21 moves.

As for ToohrVyk's link, I'm searching for optimal solutions not the standard top, middle, bottom solution.

Essentially I'm looking for a method to evaluate the validity of the cube from a randomly scrambled state to ensure that the parity has not been violated.

-Kirk

##### Share on other sites
ToohrVyk    1595
There is a deterministic algorithm for solving the rubik's cube (the one used by humans: top, middle bottom). This involves no exponential growth of the solution space and allows you to check very quickly if a solution exists.

Once you've determined this, you can start your search for the fastest solution using whatever algorithm you wish.

##### Share on other sites
kirkd    505
ToohrVyk - good point. I suppose a pre-processing step of that sort would be viable, albeit a bit slow for the validation step.