Я реализовал кубик Рубика, используя перестановки кортежей. Куб без изменений представлен как (0, 1, 2, ..., 45, 46, 47).
Чтобы применить «поворот» к кубу, числа перемешиваются. Я довольно полно проверил все свои ходы до такой степени, что уверен, что опечаток нет.
Я пытался реализовать метод, который проверяет, является ли куб действительным или нет, потому что только 1 из 12 случайных перестановок (1, 2, ... 47, 48) является допустимым кубом. Чтобы перестановка была действительным кубиком Рубика, он должен соответствовать 3 требованиям. Это было хорошо задокументировано в этой теме: https://math.stackexchange.com/questions/127577/how-to-tell-if-a-rubiks-cube-is-solvable
3 шага:
Ориентация кромки: количество сгибов кромок должно быть четным.
Ориентация угла: количество угловых поворотов должно делиться на 3.
Соотношение перестановок: вот где у меня проблемы. Четность перестановки должна быть четной, это означает, что четность угла должна соответствовать четности края.
Библиотека SymPy предоставляет мне отличный способ работы с рядом свойств группы перестановок, поэтому я включил ее в свою попытку вычисления четности перестановки.
Простейшим тестовым вводом, на котором он завершается неудачно, когда он должен быть успешным, является обратный поворот куба, представленный как B.
Вот код:
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
Используя кучу операторов печати, я обрисовал в общих чертах, что происходит во всем коде:
Это начальное состояние. Это перестановка куба B, которая выглядит как и ожидалось.
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)
Далее мы смотрим на углы и ребра. Помните, что у края есть 24 вычтенных из каждого. Это необходимо для возможного преобразования в перестановку SymPy.
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]
Затем мы извлекаем только каждые 3 угла и каждые 2 края. Это позволяет нам смотреть только на перестановку каждой части, потому что мы не заботимся об ориентации.
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)
Затем мы угадываем на 2 или 3, чтобы преобразовать в SymPy
normalized_corners, edges
[0, 1, 2, 3, 6, 4, 7, 5]
[0, 1, 3, 2, 4, 6, 5, 7, 8, 9, 10, 11]
После преобразования в SymPy углы выглядят так:
sympy corners
(4 6 7 5)
[(4, 5), (4, 7), (4, 6)]
[[0], [1], [2], [3], [4, 6, 7, 5]]
И края выглядят так:
sympy edges
(11)(2 3)(5 6)
[(2, 3), (5, 6)]
[[0], [1], [2, 3], [4], [5, 6], [7], [8], [9], [10], [11]]
Дает нам это соотношение, потому что углы состоят из 3 циклов, а ребра состоят из 2 циклов:
углы, ребра, пермское соотношение
1
0
Поскольку четности отличаются, функция возвращает false.
B: Ложь
Мы знаем, что паритеты должны совпадать, но я не могу добиться такого результата, и я вроде как заблудился, куда идти для дальнейшей отладки. Весь код можно найти на моем GitHub здесь: https://github.com/elliotmartin/RubikLite/blob/master/Rubik.py