Defining if a mixed rubik's cube is valid or not

[NvD]

Hello everyone,

Lately, I have been creating a rubik's cube solving software, but my problem is that if the user is entering an invalid scramble (some pieces have been twisted / swapped), the algorithm is simply not going to work.

Thus, I am looking for a solution to know, thanks to a mixed rubik's cube, if some pieces have been illegally moved.

I already know this challenge involve knowing :

If corners are well oriented

If edges are well oriented

If pieces have been swapped

Does anyone have an idea ?

 

[Hazel]

This video should give you some useful info

 

[xyzzy]

How to determine a piece's orientation when it's not permuted: http://kociemba.org/math/cubielevel.htm

How to compute permutation parity (counting inversions mod 2):

function permutation_parity(A)
{
	let n = A.length;
	let parity = 0;
	for (let i = 0; i < n-1; i++)
	{
		for (let j = i; j < n; j++)
		{
			if (A[i] > A[j]) parity ^= 1;
		}
	}
	return parity;	
}

The constraints for a cube state to be solvable:
- No duplicate pieces, no impossible pieces (e.g. a blue-green-white corner on the standard colour scheme), etc.
- Edge permutation parity = corner permutation parity.
- Sum of edge orientations mod 2 = 0.
- Sum of corner orientations mod 3 = 0.

If you already have your solving algorithm working (and you're sure you haven't missed any corner cases), you can also try plugging the cube state into your solver and see if the result is a solved cube.

(J Perm's video is fine but it doesn't give an effective algorithm for determining whether a state is solvable, I think.)