How to determine if the cube is in the correct state?

[kmetic]

I am writing my own application which will be able to solve any given cube.

Now I am working on a functionality where the user can set initial state of the cube, it will look something like this: http://www.monster-legends.info/images/solve-rubik's-cube.jpg

But as you probably know, only 1/12 of all possible states are actually reachable. How can I check if the cube is in the correct state?

 

[aronpm]

But as you probably know, only 1/12 of all possible states are actually reachable. How can I check if the cube is in the correct state?

Sorry I can't help with the actual solution, but the number of solvable states will be a lot less than 1/12 for this, because you're allowing the user to place stickers rather than pieces.

If you check each sticker placement as they place the sticker, there are some things that should not be allowed:
placing opposite colours on the same piece
placing two colours on two edges (duplicate edges)
placing two colours on two corners in the same direction (duplicate corners) (eg there is a white-blue-red corner but there cannot be another white-blue-something corner; the other corner with white and blue is white-orange-blue)

If you have checked that all the pieces are legal, you could check edge and corner orientation fairly easily, but I don't know how to do permutation.

 

[kmetic]

Yes, I know about these checks. But even if these checks are all OK, you still have only 1/12 possibility that everything is OK. Actually - these checks just assure, that the cube contains the correct cubicles, just like someone would assemble the real cube out of cubicles.

 

[Hodari]

1. Check if all the pieces are legal
2. Choose a standard orientation for the centers such as yellow on top, orange in front
3. Check corner orientation by looking at the top or bottom color sticker on each. If it is on the top/bottom face, assign it a value of 0. If it is clockwise from the top/bottom face, the value is 1, counterclockwise = -1. The total for all corners must add up to 0.
4. Check edge orientation. For edges with a top/bottom color sticker, they are correctly oriented if those stickers are on the top/bottom face or if an L/R move can place them so that they are. Middle layer edges are correctly oriented if the L/R color sticker is adjacent to its center or to the opposite color center, or if a U/D move can place it that way. Or for a computer checking, just have a table for each position and piece indicating which orientation is correct. There must be an even number of correctly oriented edges.
5. Check corner and edge permutations. Not if this is the best way to do so is but you could try reducing it to a series of cycles. For example, using something similar to Old Pochman but without needing to worry about orientation of pieces or even using a fixed buffer, you could create a table for edges as follows:
Edge Position number(1-12) - number of piece currently in that position.
Start with position 1 and check what piece is currently in that location. Go to that position number and check which piece is there. Continue until you get to a piece which is already in its correct location. If the first piece you check is already correct, then just go to the next position instead and continue until all 12 edges are correct and keep track of how many swaps needed to be performed.
Do the same for corners and make sure the total for edges + corners is an even number.

 

[kmetic]

Thanks, I'm working on it!

A question about orientation of the corners (your number 3). Start with the solved cube (orientation of the centers: white up, blue front, orange right) and apply UFUF algorithm to it.
As I understand your algorithm, for the white color, the UpBackRight and DownLeftFront corners have value of 0, because they are on up/down face.
The UpRightFront corner has value of -1, because white color is anticlockwise from up face.
The DownFrontRight corner has the value of -1 also, because white color is anticlockwise from down face.
So the sum is -2, which is incorrect, did I miss something?

 

[Hodari]

Thanks, I'm working on it!

A question about orientation of the corners (your number 3). Start with the solved cube (orientation of the centers: white up, blue front, orange right) and apply UFUF algorithm to it.
As I understand your algorithm, for the white color, the UpBackRight and DownLeftFront corners have value of 0, because they are on up/down face.
The UpRightFront corner has value of -1, because white color is anticlockwise from up face.
The DownFrontRight corner has the value of -1 also, because white color is anticlockwise from down face.
So the sum is -2, which is incorrect, did I miss something?

You need to account for ALL the corners, not just the white ones. Also, I forgot to mention that you need to use modular arithmetic here, so if the sum ever reaches +/-3, you would reset it to 0.

So in your example, you are correct for the white corners but then also need to look at the yellow ones as well.
Three of those are correctly oriented = 0
The UpBackLeft corner is counterclockwise = -1
Which brings the sum to -3 which then needs to be reset to 0, so this is correct.

 

[kmetic]

Thanks, this works On to next checks...

PS - do you know any web sites with this topic?