Sign in to follow this  
kirkd

Rubik's Cube validity

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this