I've implemented a Rubik's cube using permutations of Tuples. The cube with no changes is represented as (0, 1, 2, ... , 45, 46, 47).
To apply a 'turn' to the cube the numbers are shuffled around. I've pretty fully tested all of my turns to the point that I'm fairly sure that there is no typos.
I've been trying to implement a method that checks whether a cube is valid or not because only 1 in 12 random permutation of (1, 2, ... 47, 48) is a valid cube. For a permutation to be a valid Rubik's cube it must meet 3 requirements. This was well documented in this SO thread: https://math.stackexchange.com/questions/127577/how-to-tell-if-a-rubiks-cube-is-solvable
The 3 steps are: Edge orientation: Number of edges flips has to be even. Corner orientation: Number of corner twists has to be divisible by 3. Permutation parity: This is where I'm having troubles. The permutation parity must be even, meaning that the corner parity must match the edge parity.
The SymPy library provides a great way for me to work with a number of permutation group properties so I included it in my attempt at computing permutation parity.
The simplest test input that it fails on when it should succeed is back turn of the cube, represented as B.
Here's the code:
def check_permutation_parity(cube):
corners = cube[:24]
edges = cube[24:]
edges = [e - 24 for e in edges]
corner_perms = corner_perms_only(corners)
edge_perms = edge_perms_only(edges)
normalized_corners = [int(c/3) for c in corner_perms]
normalized_edges = [int(e/2) for e in edge_perms]
sympy_corners = Permutation(list(normalized_corners))
sympy_edges = Permutation(list(normalized_edges))
corners_perm_parity = Permutation(list(normalized_corners)).parity()
edges_perm_parity = Permutation(list(normalized_edges)).parity()
if corners_perm_parity != edges_perm_parity:
return False
return True
Using a bunch of print statements I've outlined what happens throughout the code:
This is the initial state. It's the B permutation of the cube and looks as expected.
cube:
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 12, 13, 14, 21, 22, 23, 15, 16, 17, 24, 25, 26, 27, 30, 31, 28, 29, 32, 33, 36, 37, 34, 35, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47)
Next we look at the corners and edges. Remember that the edge has 24 subtracted from every one. This is necessary for eventual conversion to a SymPy permutation.
corners, edges
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 12, 13, 14, 21, 22, 23, 15, 16, 17)
[0, 1, 2, 3, 6, 7, 4, 5, 8, 9, 12, 13, 10, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]
Then we extract just every 3 corner and every 2 edge. This lets us look at just the permutation of each piece because we don't care about orientation.
corner_perms_only, edges_perms_only
(0, 3, 6, 9, 18, 12, 21, 15)
(0, 2, 6, 4, 8, 12, 10, 14, 16, 18, 20, 22)
Then we divine by 2 or 3 to convert to SymPy
normalized_corners, edges
[0, 1, 2, 3, 6, 4, 7, 5]
[0, 1, 3, 2, 4, 6, 5, 7, 8, 9, 10, 11]
After converting to SymPy the corners look as such:
sympy corners
(4 6 7 5)
[(4, 5), (4, 7), (4, 6)]
[[0], [1], [2], [3], [4, 6, 7, 5]]
And the edges look as such:
sympy edges
(11)(2 3)(5 6)
[(2, 3), (5, 6)]
[[0], [1], [2, 3], [4], [5, 6], [7], [8], [9], [10], [11]]
Giving us this parity because the corners consists of a 3 cycle and the edges consist of a 2 cycle:
corners, edges perm parity
1
0
Because the parities differ the function returns false.
B: False
We know that the parities should match, but I can't get that result to happen and I'm kind of lost in where to go for further debugging. All of the code can be found on my GitHub here: https://github.com/elliotmartin/RubikLite/blob/master/Rubik.py
My issue had nothing to do with SymPy and the permutation parities. To check this I implemented my own algorithm for cyclic decomposition and then checked the parities. In the end the issue had to do with how I set up the permutations for each move.
I guess I've learned a lot about testing - if your tests don't test for the correct thing then they're not that useful.