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

If the solver cannot solve it...

Unsolvable.

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

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.

ToohrVyk - good point. I suppose a pre-processing step of that sort would be viable, albeit a bit slow for the validation step.